一些组合函数

lilianjie1

n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
0 r0 l9 W: _) o" S0 sNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
: h' K- I1 ?. V$ N$ l0 }. d1 qNumberOfPermutations(n, 4);
0 G& S% S" n% c' [0 LNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
7 n" r$ M; @/ c1 n- z$ Q% X4 i7 @, i2 XBinomial(n, 9) ;
( z; }* E7 P" F7 h; f. d) JBinomial(n, 10) ;
Binomial(n, 11) ;
2 \3 g3 f' }4 \0 W# |! QMultinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600
# v& l2 c0 r( K! X
3 Z$ _* v. E+ E* I3 ]Fibonacci(n);斐波数Fibonacci(n-1);
* y$ {/ n* A& `7 f% W  _Fibonacci(n+1);
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
$ c- V3 j' R1 f4 AGeneralizedFibonacciNumber(0, 1, n) ;
' y) ~1 N) _* C  m4 J9 KCatalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
- f7 l/ Q( c* X. W4 u* [7 jk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
( m! s6 u8 a2 }7 C% Y3 fCatalan(1);
" R/ h" z& M2 E2 f: LCatalan(2);
2 `5 D$ g% J1 pCatalan(3);Catalan(4);
2 K4 K8 u3 _. [! n6 }; q" sCatalan(12);

, o* ?3 a* p: k) o/ N7 L; y1 Z) mLucas(n);卢卡斯数
12
6 X. a$ |; r. B, {2 n) X479001600
0 _. r' u: I" ]4 M831600
12
+ @" k! m) X2 J% H4 X8 S8 T132
11880
) p9 ~: Y- ~0 P$ Z6 r- J& s479001600
0 s3 v5 K2 s# y, V) s" `. H12
; T9 _5 }: z+ ^) P2 \$ m66
5 S$ \. }8 C; H8 R220
220
: D1 r7 [' E. S: a2 W' {) @66
9 g, w: E( _+ o1 v4 H12
831600
. ]  p' h$ d6 b144
89
/ M- Z* j7 R7 W: i- N0 `, y/ ?# r233
233
$ H$ [* H# @) \610
  ~' y; L/ c5 \+ v* ?& e2 n144
208012
208012
( {$ Z9 B2 {0 k  P3 R1
) C% Q- c5 m* _) ?* ]0 L2
5
14
208012
322
3 R% N- v/ F  k" S  y

卡特兰数=(2n)!/((n)!*(n+1)!))
4 G& U/ p- G" x5 n9 q0 f+ ICn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
, j1 D7 g) x6 G$ r**YYY XYXXYY XYXYXY XXYYXY XXYXYY
& C, ~- U( T6 Y3 ~7 o( o( n将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
, Y1 [- p7 J4 M((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
/ G- w, d* g, |1 _4 B9 \) Q# ]0 p
7 L  U( A, ^; C8 ~Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

0 d+ J/ {6 F2 m) 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.
Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:
( h% a2 I+ v& M, o6 j- e1 f

8 o) [* k& O: c8 D9 A7 K, ~  N; p
% ^' x0 z0 g: I7 r1 j/ d' Q; l卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

- h3 k- m" h# E1 }) A, ^* e. e# ~但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同

- X% b3 u! w9 T# f
! r3 H/ B. t% l( e- a7 ~
n:=100;n;
a:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
- w4 v8 n; y2 @5 \/ R# F. [: ?Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);

8 Y+ `6 n$ T) j6 Z& p100
792070839848372253127
792070839848372253127
% Q9 [9 T3 |8 ^6 u1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

2 L8 e5 A! K2 J, A# ]
) }' e3 }1 {3 o0 b% E- N反费波那西数列反费波那西数列的递归公式如下：
2 `  s9 N" F9 T
Gn + 2 = Gn − Gn + 1
" `' x1 k8 Y: W6 _如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

1 @4 H$ S2 N! k3 S即是F2n + 1 = G2n + 1,F2n = − G2n。

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);
; l& T9 }  m+ n" ?( M1 hStirlingSecond(4, 3);
2
8 m% k5 s0 J% j7 r1 m& U  }4 y52
" O* ~$ d  n! F8 p5 A8 B5 \% m5
$ K/ y$ H. C, v1 k3 o' n. B( s6 G7 q15
9 }, a6 I) m7 Z1 y& y  V-6
11
-6
1
7
6

. Y2 k% W1 b$ G$ g% m4 ~3 eBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：

, q7 e' _0 |% t8 a! `{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
3 i3 u5 x# b1 X. r- s{{c}, {a, b}}
{{''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)
) d0 I" B6 Y6 z; Q2 J9 f0 w
; ]% T- o5 }& ~% W0 T换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

- A# o0 `+ I9 j/ W9 K{A,B},{C,D}
  Y( O9 |' u0 W& Q7 V% z: h{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
{C},{A,D,B}
" {0 @9 i! G. H4 a{D},{A,B,C}
{D},{A,C,B}
+ q& Y; x" j- p$ H第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
0 m4 t6 \* M2 t+ |S(n,n − 1) = C(n,2) = n(n − 1) / 2
  N" {9 ?% L8 T0 o0 ~9 F* aS(n,2) = 2n − 1 − 1
. y) z  J2 ^9 g1 m
换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

* ^# X2 O; G! v6 v2 ^- o- r{A,B},{C,D}
& K+ k4 ^' l- g4 J1 L{A,C},{B,D}
. \' M' S% Q7 \' W8 D7 `0 W{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
, l/ p7 b$ J6 O" \& A9 K{C},{A,B,D}
) M% h! E) e+ Q; P{D},{A,B,C}
( \2 m5 B# ]7 }/ X% f因此S(4,2) = 7。

lilianjie1

- i6 m: A6 a$ |
; H% S, t* o* l' A2 Vn:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式
% L; l: {' l- C3 n. T" L% [9 b$ N
7 ]) i6 D) p$ @- ?4 ^0 Z26
$ A& i0 o7 h- G* N, c1 r) b( q1 T0 z137/60
0
0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

- G: g6 T, R; @0 I
; Q' w( F0 _) A5 @1 R
6 R9 u4 {$ @5 {伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
& B0 |1 W0 A8 l3 @
9 z) d! v/ i' ?/ E3 G伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

5 D/ g! h2 D) o. J  O拆分 。。。。强！
. X0 _( V5 R& _5 a* w/ @: W
8 J" m+ L0 q0 c) sNumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

' [: H% Z3 [7 x* K) T( w& C% K3 o- E; ?7
0 K" {- D' v! i/ S4 Z* t+ }# \4 l( H190569292
[
    [ 10 ],
1 A6 b, i, {2 t! h    [ 9, 1 ],
* _6 [, B9 z% R, ]! d1 \; R    [ 8, 2 ],
; A$ W, }. e; f, D  N    [ 8, 1, 1 ],
    [ 7, 3 ],
    [ 7, 2, 1 ],
$ }( \8 }4 ^- S4 ^" I    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
% l0 |- Y) A' M    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
; G/ L5 P9 c; o' o2 w/ v    [ 5, 5 ],
5 A8 _3 a: L& C: b8 ~6 W    [ 5, 4, 1 ],
% \+ J4 d" R- v/ |& D* P    [ 5, 3, 2 ],
* r& [! |2 ~+ j5 a3 n    [ 5, 3, 1, 1 ],
) y9 z2 u9 j6 B) T( E. X    [ 5, 2, 2, 1 ],
5 l/ n4 B% t" _2 z3 j    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
1 g7 P' t" l. x' k3 J* C% U: W1 P    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
( I6 L7 y. j7 l    [ 4, 2, 2, 2 ],
/ u/ t/ F- x$ M, B# P) o    [ 4, 2, 2, 1, 1 ],
0 [( {3 t0 R( K9 W  e9 ?. O' [    [ 4, 2, 1, 1, 1, 1 ],
$ q) h% ?, U  L5 g" ~( w    [ 4, 1, 1, 1, 1, 1, 1 ],
$ z3 k2 k6 L* `    [ 3, 3, 3, 1 ],
    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
# a  d* ?- v9 l2 s    [ 3, 2, 2, 2, 1 ],
3 Y; M$ p9 ?/ W9 s/ v3 L    [ 3, 2, 2, 1, 1, 1 ],
4 I: |( i+ C- t* ?; L    [ 3, 2, 1, 1, 1, 1, 1 ],
5 u- ]) M; s( B) z9 N- p7 f    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
$ h$ W1 @, _6 ~8 ~1 ^    [ 2, 2, 2, 2, 2 ],
4 g: I3 I. F9 e    [ 2, 2, 2, 2, 1, 1 ],
. W9 G5 N0 a3 J    [ 2, 2, 2, 1, 1, 1, 1 ],
$ {4 a* p" ^( x6 Y, e    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
' ~6 u% n8 P. d% i    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
]

xxgzftj