标题: 一些组合函数 [打印本页] 作者: lilianjie1 时间: 2012-1-12 15:56 标题: 一些组合函数 本帖最后由 lilianjie1 于 2012-1-12 18:09 编辑 " U7 [% r. U/ C ) Z$ L3 y m( C! Sn:=12;n; 8 ]+ V/ O$ Q( r, h; oFactorial(n);求阶乘 0 h( }! t2 ]2 J) @/ |- rFactorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4)); 3 ?1 H- D* h ]( b }; `" v1 tNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);+ O. B; O% ] i1 Q
NumberOfPermutations(n, 4); v' P9 _6 z8 m$ t( v
NumberOfPermutations(n, 11);/ o+ }& q4 o2 I+ ?+ e
Binomial(n, 1) ;二项式系数Binomial(n, 2) ; . R9 @+ h; u. e; e" cBinomial(n, 3) ; * A+ U) D& ?' L7 [ v1 F6 bBinomial(n, 9) ;! J2 | ]3 k& C* t
Binomial(n, 10) ; " L4 B/ s5 ^, lBinomial(n, 11) ; H* n* H+ a( @4 C! t
Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12!/1!*2!*2!*3!*4!=8316000 i6 G- I/ q, R _
& w4 p4 K* i/ X0 ^- S
Fibonacci(n);斐波数Fibonacci(n-1); " A/ A, m: G) O2 a% ~Fibonacci(n+1); 9 d8 P' O6 ]4 x/ N- d; ]1 IGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ; , I# b+ n/ u; n& GGeneralizedFibonacciNumber(0, 1, n) ;* W( k( p" M( Z- O/ b- O& ~3 b
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!)) 0 F- M, s4 I% [2 ~ y+ g- n4 lk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m; ! d( x7 y% Q: @ W1 [! PCatalan(1); , |! G, j) {% T! w& S& UCatalan(2);2 ^9 P4 D$ \( Z1 p7 c
Catalan(3);Catalan(4);5 [; M8 q7 N% a: D
Catalan(12); . o {; I1 w9 u9 ?1 p7 c5 h ! T9 Y* F6 H( Y* g7 pLucas(n);卢卡斯数 5 j) K! Z+ H- J( U- h5 Q9 z* F/ X126 }/ k2 X- H" n: P8 s6 D6 e1 Y
479001600 & t3 e% ^3 S5 e7 M# h; I831600 1 f7 n* I2 k( i3 Y; K4 B0 [12 C) i- A3 x k ?9 f1324 r$ M5 s9 q% ^. S
118804 A( P* S, U! \! B: \" }; a! u
4790016009 j3 ?9 V4 ~7 t! p; B% w _
12 8 ]1 k" ?, Z! j7 ]* [66/ e7 r, ^- g& D
220 : b3 t/ S. F, c7 R. ~! b220 , p" o* @6 O7 {# t% X66% D. {7 d8 e$ z z. t1 ~
12. A/ J# r& `2 K2 ~/ ^7 D. z
831600 8 o! m2 j$ H6 l# u6 B144 }2 W& p0 Z0 y/ j; T" m- Y
89 ^ s6 Q p4 [/ p
233+ Y% n" o' e u6 h1 Q* |2 ]
233 ; `! D: e. X% M" p4 K2 D610- l$ j# H9 M# R8 I
144% K3 P& y* t7 G. w5 `4 g
208012 ; f- c# p! q6 O s208012 2 d L) i0 r4 n! Q$ W1 ' g3 p8 k- @) y- ?0 j2" Z9 I3 g, d( z2 u( c
5+ t: U C4 j" z. y
14 ; Z. p0 a# J) h7 S, u' Q208012$ n) ]7 L. o. ^' `" w) }
322 : F: [7 L9 a+ L$ _# m5 @7 N 8 X6 t8 C% p7 H. E B 7 \* ~% P0 I0 k5 d1 j* Z. O卡特兰数=(2n)!/((n)!*(n+1)!)) " s- V+ ^8 |. tCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words: 7 M) J8 o3 }8 R X( l" E% c* {* _**YYY XYXXYY XYXYXY XXYYXY XXYXYY ; M! t8 w; f, B6 @将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数: 8 h6 K0 O: l$ [, ]: j! p
((())) ()(()) ()()() (())() (()()) ( E' p m; R6 m) F" fCn表示有n+1个叶子的二叉树的个数。 ) l4 r" Z9 ?( e$ P. x
& ]) ~' b: X/ N# ]& x) N
Cn表示所有不同构的含n个分枝结点的满二叉树的个数。(一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。) + b2 F4 \6 u8 K4 U: d/ n
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况: 5 K3 i: b" t, G; h5 N, T
# g$ w' O: r6 G4 x1 K% `- _Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下:令w = unv,其中n为w的最大元素,u和v为更短的数列;再令S(w) = S(u)S(v)n,其中S为所有含一个元素的数列的单位元。 1 F6 Y3 F& X+ c6 G) m2 l
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. $ A7 }3 \) s4 I1 K7 D8 TCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况: ' m( e* I0 y0 g' B & R, N$ [/ a7 Y, d5 B4 X1 p7 Q! A: g$ y0 B6 @. [2 ~
8 _% |4 b- g/ r 卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列,他既研究了这个数列,也研究了有密切关系的斐波那契数(两个数列都是卢卡斯数列)。与斐波那契数一样,每一个卢卡斯数都定义为前两项之和,也就是说,它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。) [; l3 j6 E$ A! q$ |4 X5 x" h! C" h