一些组合函数

lilianjie1

$ W- V. J/ P: r
n:=12;n;
& _6 ~( P+ W+ x7 O* PFactorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
NumberOfPermutations(n, 4);
4 O5 J# O4 @6 o3 {- A% sNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
% I  c# r) f  \. W. \# c5 ~Binomial(n, 3) ;
Binomial(n, 9) ;
) _, L# [3 J4 ]$ QBinomial(n, 10) ;
! W& `$ V7 ~7 MBinomial(n, 11) ;
Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600

8 E+ {% n) i, ~% i4 b' }Fibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
# S- t6 ~# f' a, @1 z2 C7 JGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
GeneralizedFibonacciNumber(0, 1, n) ;
& I  A4 h4 ~8 _- k! Y/ DCatalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
+ B# X- N4 H$ R, ~, L/ b& _( c9 ak:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
2 a. ]: Q0 J. b$ N4 g) W" HCatalan(1);
8 U' D' Z1 O5 j0 _/ l) r/ OCatalan(2);
Catalan(3);Catalan(4);
Catalan(12);

Lucas(n);卢卡斯数
12
479001600
831600
1 e  C# `$ g& g, h& [& B5 y( S12
132
11880
479001600
' V2 @1 [& k; w1 Y" Q: r4 o6 ~/ o12
66
& r- m2 Y; K$ v, G* v4 Z220
220
66
12
7 r4 k$ `- h* g5 c( [  R831600
144
  i- V" R* @& R" g" ?$ V89
233
233
# ]0 Q+ W+ ]8 z; d. j; @! v610
3 ?( D& e, i  G) i$ z% k% ?144
" W( o/ X9 l% j2 u- n. |' [  _208012
5 J' X5 Y& ~7 Y3 D208012
1
, e& |$ |' q9 Y: B) G2
1 [; L- ]6 z& d# \# K2 ^5
/ n# C  r' ^( N( `# b14
) v/ u" [; u+ p208012
- _* F0 _6 y; a$ W7 ]2 ]  S" {5 I) m322


卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。

9 r& P0 m* j- uCn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
: ~5 k0 {2 p3 F" {6 O7 S
& X) I% C3 p6 }) y/ e& LCn表示对{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.
8 {( v) T7 [$ N: bCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:



卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

! ?8 y( i$ V, Y但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同

/ n6 N# y2 p2 w" `3 A' w7 K

n:=100;n;
a:=Lucas(n);a;
2 f0 b3 s4 z% `b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
7 f; v# l  h! Q7 z% H
100
0 G' K# p1 O5 }5 ^% z792070839848372253127
792070839848372253127
1771124240896309575375
1771124240896309575375

xxgzftj

lilianjie

$ _; s5 x$ v, @4 x8 |
; L+ Y" {: G9 o) H拆分 。。。。强！
% Q  a7 j4 H3 i9 H/ t
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

& E2 a: _7 M  t2 ~/ U- h2 h7
190569292
[
    [ 10 ],
    [ 9, 1 ],
    [ 8, 2 ],
1 y0 _/ x+ L  W9 f$ k( u, K    [ 8, 1, 1 ],
) E/ f, [7 l+ h# x9 i    [ 7, 3 ],
' Z+ Y( q# Y( Q2 l+ P# x& C    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
; _$ b' h: r0 e/ |4 q9 p* O, R    [ 6, 4 ],
2 h) @: `0 o8 k: v    [ 6, 3, 1 ],
" Z1 T1 C: A; X    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
; l& B# s+ c0 W    [ 6, 1, 1, 1, 1 ],
9 i# c4 S+ M7 S% R* \1 r    [ 5, 5 ],
& r3 r0 ^; g1 Q1 ^2 \, J6 [; K    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
. i+ d3 Z# y& L9 l- R    [ 5, 3, 1, 1 ],
% e, b- R& O4 f    [ 5, 2, 2, 1 ],
2 A7 \; g3 Z8 E6 C    [ 5, 2, 1, 1, 1 ],
. D$ |, W) l* z/ P0 }' ~3 {    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
0 X/ M; L5 k- T  `+ [    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
/ ]; g; j" I8 k    [ 4, 2, 2, 2 ],
    [ 4, 2, 2, 1, 1 ],
# {( B2 G8 H: s: z    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
/ p: Y6 C1 U% }8 y    [ 3, 3, 3, 1 ],
4 _" E5 E2 W; E- a! k9 C    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
  a+ w3 _+ x& n1 h/ L    [ 3, 3, 1, 1, 1, 1 ],
' |: {3 i7 m6 n0 `    [ 3, 2, 2, 2, 1 ],
$ `- O" D; Z( B: U4 w$ Q. R8 }    [ 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 ],
, a. y1 [& `% W. s0 }7 ?' S    [ 2, 2, 2, 1, 1, 1, 1 ],
% Z8 l( f- `1 X1 G3 J+ a+ y    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
: ]7 W& F. {" `! l    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
+ c0 Z/ ~: p, u( Y5 J* v: b3 ~]

lilianjie

伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。

伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
. M" T2 T/ F1 h8 m" A

lilianjie1

5 N5 Q+ Z( R5 v& h# D
n:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
- K/ b& ?) h$ O; bBernoulliPolynomial(n) ;伯努利多项式
, |  p6 U8 c% I4 r
26
137/60
/ o' ~) R3 d4 ]& Y. D! x- E- L  u0
0.000000000000000000000000000000
5 b; R" q, y4 R; X/ r$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

. ^$ G$ q: T$ J2 C; m反费波那西数列反费波那西数列的递归公式如下：

Gn + 2 = Gn − Gn + 1
3 F; s. Y2 `  q) S如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

  ^$ t/ w( v5 C5 K8 s, E& J* L即是F2n + 1 = G2n + 1,F2n = − G2n。

2 c( K' }; D" l; i9 ^# ?Bell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
4 O' M8 H  y7 B. E, iStirlingSecond(4, 3);
- A) Q" R9 f$ r  \2
" U0 e6 L. a$ t8 R; l  `, A52
5
15
/ D- s# {; e: d4 i-6
11
2 c  C/ j1 W( H0 E-6
* S( u$ Y7 E8 i0 h# _3 J( _1
7
$ F" ]0 d7 v. r% m8 M6

Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
; Z& z6 f  i8 B# G) A" e* v
# }' Q+ ]( W* V- w; ]- e{{a}, {b}, {c}}
' \+ A+ Q+ N; r  B7 I  `{{a}, {b, c}}
- G* R  n7 h4 M6 t5 ^{{b}, {a, c}}
" p3 I; h7 b  a{{c}, {a, b}}
& `9 x* Z4 L# Q4 C8 N{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
! g( o0 r6 P5 Y; q有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

6 g% O, t6 G6 K3 h{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
2 L9 {+ X7 a, H, a# W6 g{A},{B,C,D}
% z1 C5 R2 Z/ l{A},{B,D,C}
- F( c, z5 t  h: y. l{B},{A,C,D}
{B},{A,D,C}
! Z  ^* C% V  c  l{C},{A,B,D}
) E$ g. q( T$ J) i' `: R  I$ C{C},{A,D,B}
{D},{A,B,C}
, L$ R; k  a: H. i8 ~5 r2 C2 O{D},{A,C,B}
( z1 T8 q* L5 ?6 ^第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
% M8 s1 w, u: C3 p, U2 ^/ B给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
S(n,n − 1) = C(n,2) = n(n − 1) / 2
0 c$ L4 y6 y: XS(n,2) = 2n − 1 − 1
5 d$ O: k' g; L) L1 c, I) }/ G
6 }+ F% J0 e) A* U5 s换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
! E) x; u; O& }+ @4 \7 k) K- G
{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
% y3 L" I# t% B9 G; y  i) `{B},{A,C,D}
. \% }2 O" c/ O4 \3 E; {( j{C},{A,B,D}
{D},{A,B,C}
- P; e, }, }2 @( N! L8 v1 U因此S(4,2) = 7。

孤寂冷逍遥