一些组合函数

lilianjie1

) o- G& ?6 i. P3 g9 \n:=12;n;
Factorial(n);求阶乘
% Z' z8 {6 R8 z4 T/ [& K4 c( _Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
$ E5 g1 @# X! P% H- O; j3 p4 VNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
NumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
& O1 M2 c2 K  v7 {- M$ eBinomial(n, 3) ;
( e# y" @% j4 V9 N) GBinomial(n, 9) ;
Binomial(n, 10) ;
) ]4 B7 n6 Y3 }7 P% Z/ W* `$ t/ U; RBinomial(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

$ J7 }/ y5 d% v- f8 J& E* LFibonacci(n);斐波数Fibonacci(n-1);
3 h1 ]9 K: m4 q' M. B4 N! B  _* ?Fibonacci(n+1);
! u/ c8 ^1 P' `5 I7 P# @& q) GGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
" k$ x! e/ P% w" i6 u6 Z! UGeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
Catalan(3);Catalan(4);
Catalan(12);
( y9 o6 \8 L0 |+ o
1 u! h- x- h) J3 }: f1 nLucas(n);卢卡斯数
12
479001600
831600
12
132
11880
2 q6 b! @* C4 E& Z2 I479001600
12
- x- f4 }; U' C" d' c8 }66
220
220
66
12
3 M. I, [* F* u831600
144
89
233
233
610
6 G6 h! a* t5 R. K4 \144
208012
$ g; ^7 T% X0 K1 E- C* S208012
1
2
5
4 D& L4 @7 i; C4 O7 q$ {14
3 ]5 B/ ?0 T0 f) l208012
322

! Q) o# C9 b5 h! N' V. _* C
卡特兰数=(2n)!/((n)!*(n+1)!))
9 G' w, i% u& U9 H# O8 x# @' WCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
  j; C6 E7 c( M- n8 v5 q; S& a& e将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
5 f) a) D9 W' I5 {: f0 i0 V# M, WCn表示有n+1个叶子的二叉树的个数。

Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
9 p7 Y6 a& O  a  f+ S
2 h, q2 h7 F/ K2 N3 j% ^2 DCn表示对{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的情况:
8 b" R- t9 v* e2 n


卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
7 t, K2 ~6 v* @6 P5 z2 w. Z
但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
2 X( S- P8 i/ T6 Q& I6 }

+ p0 V' r+ s& k6 h5 w
2 |/ a' e4 Y5 k6 C/ F: on:=100;n;
6 U& h* Q" q+ ^; w0 Ha:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
7 P0 z0 m1 D: |( q* k% Q
100
2 U$ R5 A2 V6 K# G) c8 ^792070839848372253127
+ r( B& f( O5 k1 I792070839848372253127
. r, G: _- z, R2 n0 Y- W. i7 n1771124240896309575375
8 T& i4 ~5 T; o0 o5 P7 ]1771124240896309575375

孤寂冷逍遥

lilianjie

  N- p* [  o" [
反费波那西数列反费波那西数列的递归公式如下：

6 I! P& @" O: _4 D+ P8 L0 VGn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
2 T5 H& [3 y% n) A0 C) ~2 ?6 i
即是F2n + 1 = G2n + 1,F2n = − G2n。

/ y3 ]$ U2 w$ |7 `0 oBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
  ?2 u: q# _2 Z" F0 UStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
! C4 f1 i0 v5 @  ?& yStirlingSecond(4, 3);
0 P, }8 F5 ?- M* G2 T$ z# _0 Z2
2 |3 ?+ }% h" B52
5
. J. e& g! m: }$ s7 ]$ g$ @" s15
-6
5 l8 g% _# ^5 @  ]11
6 R! n- K7 E( k3 |3 q-6
9 s1 l5 O  w3 l$ v) y1
4 b6 x3 r; g9 u. r; I3 N7
. d/ \2 f* O+ q) v( ~6
; B6 M' N1 ]" H# q/ X1 @
$ h; ?* v( Q) Q: `' E5 X& NBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
( B9 @$ W5 H' r6 `% I+ e& j
{{a}, {b}, {c}}
, O: c. R) V5 u1 l. O& F4 p{{a}, {b, c}}
& G+ t# [7 ^6 i# \. w{{b}, {a, c}}
" u5 N9 ?  K6 Q" A) X2 T! Y{{c}, {a, b}}
( T; {/ K4 v8 W# h( Z{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
# {9 J$ z6 b6 E( M  j) w1 k有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

* q, ~8 f# q% t" Y6 k1 J换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
0 A: M& o/ t  T/ I
, b5 I* f5 q. J* L8 h+ D{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
! s0 J5 o' U. l' q9 ?2 B* F{A},{B,C,D}
, g' o7 q2 |6 Z1 I. B2 }% J& N6 k) X{A},{B,D,C}
  p1 y1 M& n( v5 I{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
5 ~9 a# a* n% E& ]- t{C},{A,D,B}
{D},{A,B,C}
{D},{A,C,B}
7 f$ }5 D7 e. y, Z2 I, j2 d$ x第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
, k3 J0 O5 ]7 n$ K& `; xS(n,n − 1) = C(n,2) = n(n − 1) / 2
/ ]# J4 r# V- s' p6 P! j9 v4 eS(n,2) = 2n − 1 − 1

换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

) k9 P% ], U0 f) ^% d{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
5 G9 z) J4 g2 B3 W5 L{A},{B,C,D}
7 a- i9 t$ ?  W8 h% o- v{B},{A,C,D}
* @0 l; @6 n; L: C4 K7 R{C},{A,B,D}
% n; C& B1 e0 M- d% Z  j& {$ f{D},{A,B,C}
" @% ?/ K) j) E+ D) j8 o: J. ^$ W因此S(4,2) = 7。

lilianjie1

n:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式

! t& N( x' `0 m26
137/60
$ t6 y/ a" d  R4 k. ~& y7 W0
0.000000000000000000000000000000
1 Y* z) Y+ \+ I5 x' `0 ^# b4 d( r$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

4 V! X0 l) Z( J  O- A

伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
, \2 m8 m2 v+ a# t
/ A2 v; R: R/ {9 o9 N) h& p伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

  J  |4 c2 e' P* R  f2 H' G
8 O% |- y8 ^9 m% R, r$ j6 g拆分 。。。。强！
$ _% i. g: e) z8 G3 H
7 l$ c% m7 S- K# W6 TNumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;
3 D2 h/ ^8 m+ i. d
# ^+ R0 c. U1 N$ b; @1 u! I7
190569292
$ ?. p8 x* w' R& ], q7 x[
    [ 10 ],
; D3 k+ f- |4 C0 U3 h7 z3 x% G( A! v' Z    [ 9, 1 ],
. b$ v  ?+ q7 d7 G    [ 8, 2 ],
3 \1 b3 s( H- v    [ 8, 1, 1 ],
2 y" a0 U( N' K* J% ~6 x    [ 7, 3 ],
    [ 7, 2, 1 ],
, R; }2 t1 ?, w& P    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
7 e; n' d2 G" M0 q! t    [ 5, 5 ],
    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
% n9 m: B; y6 O$ s' P, S    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
    [ 4, 2, 2, 2 ],
5 w7 H8 j+ k/ o7 |- }    [ 4, 2, 2, 1, 1 ],
' V4 {: U# g. y7 U) T: W* ^    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
. ^& A& v$ w; e  ~! _! w/ Z    [ 3, 3, 3, 1 ],
    [ 3, 3, 2, 2 ],
  F6 s8 }6 c6 s, Y5 u    [ 3, 3, 2, 1, 1 ],
6 h7 I9 Y( l# _/ L* P& y: Q    [ 3, 3, 1, 1, 1, 1 ],
. M9 y% ?) H& c% b    [ 3, 2, 2, 2, 1 ],
- m2 j2 l+ A, o' Y$ P- F9 [* I    [ 3, 2, 2, 1, 1, 1 ],
. s4 o  w0 |/ h  L$ k! n    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
% ~4 N: W* I* {, P- `2 r) D9 Z    [ 2, 2, 2, 2, 2 ],
1 d+ A. N. O! q- s- D, W% `    [ 2, 2, 2, 2, 1, 1 ],
3 ?' f( b- O( E5 e, H    [ 2, 2, 2, 1, 1, 1, 1 ],
4 S0 N7 B$ Z: z! u* {- @# D2 x1 d    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
1 W$ @1 H9 ], ]2 D/ h% [    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
$ u6 y1 e* I8 Z/ [7 f6 \2 \    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
* {) W1 h' \0 q5 e9 N# N+ k]

xxgzftj