一些组合函数

lilianjie1

# N0 M+ s! N; \
' \8 X* I& K* V4 o/ Nn:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
" \2 y1 o8 j* j7 N( W8 ^* _: HNumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
) W1 `1 N! D9 U% SBinomial(n, 3) ;
Binomial(n, 9) ;
9 V- s& G" L9 e! cBinomial(n, 10) ;
Binomial(n, 11) ;
2 T4 Q9 w% X8 y. E# o9 C, r  Q! OMultinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600

Fibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
& l0 C, y; M- P; _& v8 Y& _$ g! gGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
+ g& ]* e8 i% E( V4 }GeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
, f/ h/ l& v% _Catalan(3);Catalan(4);
Catalan(12);

Lucas(n);卢卡斯数
9 J) S7 W/ z  `12
479001600
( y  B' u8 n* _, M1 T* a831600
12
132
11880
479001600
12
66
220
9 b( x5 i0 c, T- g% j220
8 n: B5 y8 O# v- u+ R# u9 r66
12
! o* p( R) K# X: m" }831600
7 S3 I5 W: r) I144
89
233
233
610
  {  g; |/ K5 ?144
  L0 {/ d7 z% m0 W- I7 |3 s208012
5 J; J. B+ y" E4 e: f6 c" t2 O208012
; X4 W5 ]* t) X9 q1
5 V+ n8 U" E0 D: G  k2
# A" I5 ^6 g/ s; f0 p% @8 c* W5
14
208012
322


卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
& f, d$ L  ]0 J* l9 m**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
( I7 e. L7 U* }! ?; X((())) ()(()) ()()() (())() (()())
1 P, \+ A/ B# b2 G& a) iCn表示有n+1个叶子的二叉树的个数。
; t& K+ e% I: Q' j* ^5 C
) i; D1 k$ h: w! k$ i7 G) k) |Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
2 L' ~& A: e1 ^. Y( ~+ \Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
8 |; V. b/ L- `; G* r
Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
9 @9 e3 d0 h* C# _  QCn表示集合{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.
Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

2 B: [+ M) }% E9 G9 {. {

, C9 x0 h! ~) _- ~+ C) _+ `卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
2 Q0 G0 j, ~  o! n/ {% o
* X% L/ l2 o+ |2 P/ M8 X但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
" b5 a! z, c8 Y  Z. ]3 Q7 O. G/ `, \


( ~, w) l6 }4 D5 g1 Dn:=100;n;
3 ?3 V5 o, O0 b* Ua:=Lucas(n);a;
+ v4 L/ z. x1 k2 A, Pb:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);

# j; }# m4 b. [+ S9 e6 A100
/ s8 d2 q9 i$ b8 A/ z4 Q) g, o792070839848372253127
792070839848372253127
. h& n* Y$ v" U/ l2 X4 V2 o: P1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

反费波那西数列反费波那西数列的递归公式如下：

Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
  q% k. B! X. X! n3 N; d) X
即是F2n + 1 = G2n + 1,F2n = − G2n。
' D& Y% x% h2 C. _% n1 `
, U2 T. f. v* l$ x8 p4 [+ qBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
8 p* x- H- x! @3 @2 @( e/ A$ n2
: h  y" \# J" |) {  I* O: Z52
8 k  s5 w" z& m- M9 t5
5 U* a. {' c# z& j4 G" p15
-6
11
2 L! J6 p* [4 w9 y-6
1
7
1 q3 y' I0 P9 h! D6
$ L( |/ }% y, _( \
Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
4 M# [* ^# F- y$ q# A! [+ B
{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
{{c}, {a, b}}
! X) o6 i* F+ a7 r, d{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)
2 S/ a1 P# P  H
换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

{A,B},{C,D}
  ~1 \0 o  b% b4 g% ~8 f) W{A,C},{B,D}
{A,D},{B,C}
# ~" k- b# \) M9 W+ |$ R# D$ ~5 J% Y{A},{B,C,D}
{A},{B,D,C}
6 g% @4 B2 [1 c  P1 b0 G8 h2 w{B},{A,C,D}
; i7 m% E( }( \& X' ~, u2 i{B},{A,D,C}
{C},{A,B,D}
8 j. W+ f) G% }- f{C},{A,D,B}
{D},{A,B,C}
9 u; M" G" T. I6 m{D},{A,C,B}
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
+ j2 Q# h& d& TS(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组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

- z1 u# A- a; t% u9 K; `- t) @{A,B},{C,D}
2 k  D9 c5 s3 S2 w% s; e{A,C},{B,D}
! X# [3 `1 ~/ H: L{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
{C},{A,B,D}
% a/ |+ ]' Y, {! @/ R$ r4 n{D},{A,B,C}
% ]8 P4 f0 R* D: H) K因此S(4,2) = 7。

lilianjie1

/ e3 a) Y/ l7 s( Nn:=5;r:=3;
% o8 t% Z4 T8 Y. A/ p% oEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
6 `  K3 c- l5 k  l6 V6 _BernoulliPolynomial(n) ;伯努利多项式

26
& }& d/ V' g1 X, ?  d0 W- ~137/60
0
0.000000000000000000000000000000
6 T& F: ^; X9 A/ ]7 ^# h$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

+ F. v3 R5 R, `' Y8 L8 {% C
* h/ s; L* J. [
' F* p4 k7 n  Z* I7 x( X
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。

伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
& P  e9 L6 m$ S9 p2 U; b! l2 [

lilianjie

; V2 T. Y1 e1 ^& v
& B: B3 v3 R4 G; o/ J5 _拆分 。。。。强！

NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

7
190569292
- ]; K& z+ n3 _, G, B( l, k" K6 ][
9 ?' P$ p2 j0 ^5 E3 l$ y/ ~) @7 M: J4 B9 ]    [ 10 ],
# l7 e) A* t  d% u2 W( A    [ 9, 1 ],
5 n% M, M; C- s! U! n0 _+ _    [ 8, 2 ],
    [ 8, 1, 1 ],
    [ 7, 3 ],
    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
6 x% g8 l- w0 G# q* g    [ 6, 3, 1 ],
# b9 m0 N" s8 N/ R. n; ^, S    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
: E2 G, [3 ^, C0 m6 i' _" {    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
' V$ R$ J& u# \& y) c' K: _    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
. `# d+ X8 y' `    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
( T  A( l; I  Y6 e% ?8 b% `3 C    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
+ w* G. I( P1 j( x# G    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
    [ 4, 2, 2, 2 ],
8 i% E: w5 w- ?; b/ n+ K# L) z! D    [ 4, 2, 2, 1, 1 ],
    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
$ j- U, m: v( O  o) W& m    [ 3, 3, 3, 1 ],
# p2 M1 g, B7 [8 Y) K3 ^9 h    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
/ |6 X+ I0 m8 S    [ 3, 2, 2, 1, 1, 1 ],
, x. F/ o3 G1 i' ]" ^) \" [) p    [ 3, 2, 1, 1, 1, 1, 1 ],
5 f6 Q0 E; \0 n5 p5 L. p( g; f$ I    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
+ S/ D4 T2 l& _: H4 M5 V    [ 2, 2, 2, 2, 2 ],
& f+ w- `3 [6 W5 b    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
( y9 y- N  P) K1 \1 v+ n    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
0 X$ T8 h2 G* }$ E3 {" a; P& J1 q    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
4 i' v$ Z: m5 b5 ?  y    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
]

xxgzftj