一些组合函数

lilianjie1

n:=12;n;
Factorial(n);求阶乘
/ W; `" J0 K! E) IFactorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
7 N4 C8 B: k' f4 y0 VNumberOfPermutations(n, 4);
& \" k4 g" C! J0 P0 l/ mNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
5 k4 n6 |  L. E, u" MBinomial(n, 3) ;
Binomial(n, 9) ;
5 v! f) m8 D; R2 XBinomial(n, 10) ;
Binomial(n, 11) ;
1 U* W# \$ i" s6 t5 s  w" P8 [Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600

( z0 B. a# b& @/ A3 {* ]Fibonacci(n);斐波数Fibonacci(n-1);
; R& w4 @4 G6 T9 O2 ~7 D0 eFibonacci(n+1);
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
2 |/ c, K, f1 G$ E, `8 RGeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
1 ^4 r6 b# `* j. |) g+ Vk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
7 |: ]- s5 C7 DCatalan(1);
6 t! K: U% \$ }5 `! X' S# VCatalan(2);
0 m  H& g" z$ j/ u& Y2 LCatalan(3);Catalan(4);
5 y, R( N' Z, @0 a8 K3 UCatalan(12);
" ?" v7 R2 n9 h
Lucas(n);卢卡斯数
! s* O8 V) k* x  _6 [- G12
479001600
831600
12
' x* k, T/ o  R$ {132
, ~4 v8 Q$ ^; V4 C  Q/ {3 l11880
' L2 |" {6 d% L479001600
12
66
9 V% J0 V: x2 s/ x- F220
) E$ ]7 n# p' P8 g2 e  F220
' g" O2 Y' V  a0 m& X0 `% a66
/ w% s: k" v+ z  ~! s12
831600
& V! r+ j" C' ~' P. ?144
' {4 g7 k: K- h0 ^% N* ~89
233
233
4 e6 q; d( g( m2 h2 S610
144
+ `" O, b" c8 A3 O$ \208012
  T7 n1 G2 Y; q; E* n4 y9 D208012
3 C$ g% V" Z- U& t( v7 [9 w. o1
! I% K9 T7 [" e# A. i2
5
14
208012
% w, ?; B) k' i5 D$ p8 w) R* k322
( s- @( N% p$ u
$ \0 ^8 ]$ z' J5 {$ ?
' @- ?9 }; d) ^- z卡特兰数=(2n)!/((n)!*(n+1)!))
& `  Z5 _! Y" R& ]) A, Z1 FCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
, j- q; F6 ~, L. A8 y* b((())) ()(()) ()()() (())() (()())
4 g6 h9 o! Z3 K* {; ICn表示有n+1个叶子的二叉树的个数。

Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
; Z) H/ n. v5 C% z5 D' [1 b+ LCn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
* ?+ Y- H  ~: e+ o! g
# z" Y( A  S+ T. t* d4 rCn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
Cn表示集合{1, ..., n}的不交叉划分的个数. 那么, Cn 永远不大于第n项贝尔数. Cn也表示集合{1, ..., 2n}的不交叉划分的个数，其中每个段落的长度为2。综合这两个结论，可以用数学归纳法证明 that all of the free cumulants of degree more than 2 of the Wigner semicircle law are zero. This law is important in free probability theory and the theory of random matrices.
& C' ~- o" h. o7 h7 Z' n0 a$ RCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:



卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
! k9 K& V' p: t' D
但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
3 K# ~3 a  Y& }. p# E* {

) c, @& W. t1 E' r/ q* g3 y0 S
) |  }0 r" i  o) ~n:=100;n;
a:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
! [. Z. e. m) c- U( E1 `
100
% w7 a+ Y8 X5 B7 u( B9 g792070839848372253127
792070839848372253127
8 N- B- O, R' g$ z1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

9 w1 t( c) g- I! W7 v8 \8 _- M! O反费波那西数列反费波那西数列的递归公式如下：
3 C8 w, C4 H% y+ K; V
Gn + 2 = Gn − Gn + 1
/ n) G( I, C/ n* e7 ?如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

即是F2n + 1 = G2n + 1,F2n = − G2n。

6 ^& v/ p( C  K" A" ]% TBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
( k  @5 s0 D) U9 g  AStirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
- g/ B0 f$ E* q. eStirlingSecond(4, 3);
9 ?1 n; T+ e) |- B2
: \% P9 I1 m2 \1 Q. S- B- z52
5
) V. v" i/ c# Z$ ]3 S15
: a! r: b% K- y3 ]" q* J7 l4 P) j-6
: g0 C  u* e" I11
$ t6 a* C, r# n-6
( z% m" \" }5 Y/ o  M, L1
8 a9 f! p) Y8 E. D0 ?, M! X7
2 g* ?" `- l2 y6

Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
: F; R! @$ B, w7 h( a
" @& a7 ?% l2 T  i- |/ b& c{{a}, {b}, {c}}
1 [. C) k" e: _2 L7 o, J5 f{{a}, {b, c}}
& e; t' ?; w  p- I! ?$ N{{b}, {a, c}}
6 u" n5 n* y) a/ e{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
, I  m# I; ~( K9 F6 {! W" O& S$ M有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)
! T7 q+ K: V7 I0 ^2 l" _
换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

" u) H# p" u4 {) _: A9 O/ f! ?  m{A,B},{C,D}
$ [; [8 g9 `. w( c7 r4 |1 X0 }& ^) t{A,C},{B,D}
+ o) s6 W3 |4 b6 s2 h6 c0 d9 q/ f{A,D},{B,C}
& z% C2 E, r, T* U, r8 |- K! ]{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
9 H6 U2 i1 R7 i7 O. e7 q{B},{A,D,C}
1 C( A1 T4 d% m- H{C},{A,B,D}
2 Y" }9 D: J$ k: l& w3 i{C},{A,D,B}
; E0 R0 u6 ^! i+ u* c- F{D},{A,B,C}
( [  G( r( U; i# p- W: @5 w9 B{D},{A,C,B}
/ K5 t$ w* o: i: a, E7 m第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
& K; q/ `4 w) e3 t- {S(n,n − 1) = C(n,2) = n(n − 1) / 2
S(n,2) = 2n − 1 − 1

换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
% A2 o9 Z+ a$ B) }* a1 M
{A,B},{C,D}
( _0 X5 V2 {/ O{A,C},{B,D}
3 j, r0 T3 V1 C0 t7 a/ }1 s{A,D},{B,C}
9 M8 Y6 K) V) a3 i3 X# ~{A},{B,C,D}
{B},{A,C,D}
. C! v0 K- Q' Z$ d. Z* ?{C},{A,B,D}
& M$ _2 K# g6 ?& Y0 T1 m{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

! b* P) W) U- y4 e
n:=5;r:=3;
2 g5 C4 A, A/ M+ `; gEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式

) m$ `* R3 \4 @0 G9 e- v4 k* `2 W26
2 d  J( @* O& ^; O2 q% l4 d/ i137/60
6 I, W/ N. ?! c& C0
0 V$ {8 Z  a$ N) p# P: E8 e0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

3 j: ]1 z  k. b/ r
* Q) s0 \; c/ g7 \; Q
- h; D6 ?% ^- ~5 [% R伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
3 t7 m% p# Y3 `4 H6 P
, u, d7 B# W0 e  w8 B伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
2 d; u) B( a' G. s

lilianjie

拆分 。。。。强！
7 c# A6 X" C8 d
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

& z; A5 Y  D! r# u7
190569292
5 A$ K" x3 b# D  d  m[
    [ 10 ],
    [ 9, 1 ],
    [ 8, 2 ],
    [ 8, 1, 1 ],
2 g/ P/ w5 W3 a" F% P( `    [ 7, 3 ],
    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
! H: w" T' o& I' r. G    [ 6, 4 ],
* \; Z2 [& b9 [/ Y    [ 6, 3, 1 ],
  \* Y) B9 z1 T2 v    [ 6, 2, 2 ],
. O! R7 B0 ^+ O    [ 6, 2, 1, 1 ],
/ J; u7 }: v2 D. ~5 }9 N' _, n. R1 [    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
# m3 ?8 z& f% w( `/ _3 \3 {: c1 Z    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
$ A  |7 `7 k# L3 G5 y: \0 |6 r    [ 4, 4, 2 ],
- F1 {: |; h5 \4 l- x' a  O    [ 4, 4, 1, 1 ],
    [ 4, 3, 3 ],
- O2 f  X5 d& y: i0 I& r9 H    [ 4, 3, 2, 1 ],
6 U5 }# o, ~4 }3 B    [ 4, 3, 1, 1, 1 ],
    [ 4, 2, 2, 2 ],
% Q0 J# h9 }- a( r  E6 u    [ 4, 2, 2, 1, 1 ],
( a, V. f& \1 n8 a" v: x: r    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
6 ^2 z  h# V6 B9 k$ \, N8 ~$ E+ ]    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
0 c- U+ J) Y! R5 L: F8 s0 t    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
    [ 3, 2, 2, 1, 1, 1 ],
    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
    [ 2, 2, 2, 2, 2 ],
    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
9 g9 C2 B+ ]5 J9 C8 M8 V, \* c    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
$ E( ^" x! u5 j; L$ m]

xxgzftj