一些组合函数

lilianjie1

. d' F) B4 v& i- [n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
2 k1 }. @) }# k) b9 z+ U3 \6 mNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
" f7 [0 I1 f# C3 @3 NNumberOfPermutations(n, 4);
% L' X3 Q. i8 }" c' I; k# F6 LNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
Binomial(n, 9) ;
+ q2 p1 j% T( ABinomial(n, 10) ;
Binomial(n, 11) ;
, V3 x3 k1 q/ ^+ _" ^" z5 {Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600
' f; j: n- j! a1 v# L3 A! G
/ E" b8 a) v4 ^, V, W/ o3 RFibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
. D2 s1 J2 ^# X; d- _& zGeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
+ C/ `+ p( ^% LCatalan(1);
  z9 J2 C, r+ Q4 g1 }" i5 oCatalan(2);
Catalan(3);Catalan(4);
$ }& b7 E2 W3 F0 m) B6 |Catalan(12);

, e3 T4 _' T7 ALucas(n);卢卡斯数
12
0 j( g$ R) J0 J1 o. P; t1 @479001600
$ X- d  W7 y2 h  V( C2 f831600
12
( d/ J6 l% Z$ ~+ ?132
11880
479001600
4 t! ]* s2 M: G/ s- ]7 M, T( d2 J12
$ M9 p/ b# e4 W3 F+ V2 _2 m66
220
+ i) K( m; h. a9 B/ E2 P220
66
12
831600
144
; a2 v0 }5 @  v4 e89
: q1 I( Q* x1 C- b; U$ x233
233
) l+ D1 T0 T6 g610
: h2 |$ _7 J* E( r! {5 b144
  N& i9 t/ f( U! u# b  ]: A208012
208012
6 S) R! T7 V: c4 L; S1
2 ?1 s# [8 V/ m6 N' p2 M' C2
7 F# L2 J, c! n8 d5
& D& k* K! x8 x$ x" {! D14
208012
) J& J- f: M! U+ v6 y, b: i322


, h: m; ?- B- ?+ Y' e/ k/ K卡特兰数=(2n)!/((n)!*(n+1)!))
6 d+ x/ |: F& S: L9 ECn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
, M' A% u4 S, t. @**YYY XYXXYY XYXYXY XXYYXY XXYXYY
" N3 e/ m2 R, j8 T" V, q% B6 E将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
* G. A- y2 C/ Y$ j6 z; H' RCn表示有n+1个叶子的二叉树的个数。

Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

: K8 {# f5 D% Q6 [) Y$ U6 ]Cn表示对{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的情况:


! ]9 ?0 l& `) I% X) @& s
0 Y: D; n$ q3 a6 c卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

! q# r+ G4 @$ v+ F  {但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同

+ [* T/ i- V  `' l# s1 d
8 {1 `# Y  H: m# t' q
5 e% r& [/ [' H- Gn:=100;n;
& q9 c! g- j% ^1 Q0 aa:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);

" u6 f; n$ J9 F1 `2 [. {' }100
; U8 J* N1 e5 S1 k. }+ C* j792070839848372253127
; i7 K9 h# `" L792070839848372253127
1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

% ]4 e' A; }' R3 k; W+ X+ y
3 U6 s9 ~3 c" R- u, _! Y反费波那西数列反费波那西数列的递归公式如下：
- L: S" B" ]$ \# g
Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
) R( n+ A3 g7 Q) {
8 @4 T1 w% r+ h6 Y; J1 r即是F2n + 1 = G2n + 1,F2n = − G2n。

8 g- O# o4 x) B) p& R* ]& _. _3 jBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
- Z0 g6 S+ [4 a- y2 v% sStirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
2
7 i- k) d. B* ]8 }52
5
3 Y  I% }/ n0 [' Z& ^, m# w15
* ^2 C$ v/ M! S* Y9 Q/ ]8 J$ R& @-6
* Y- `9 Y9 c. W4 u4 N+ x11
) u; [+ o+ H& Y0 K8 u6 P-6
1
2 W3 _- Q% S+ L" Y3 F! }* w7
$ I% S1 j9 X9 X. z2 N! M6

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

( Z" G" m4 `& F{{a}, {b}, {c}}
5 p  \! D5 S7 [; J" W' K! j{{a}, {b, c}}
% t$ M3 p' C- F* ?4 g9 o" t{{b}, {a, c}}
& Z2 j7 G2 N3 h2 E2 P{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
+ C* D# _" Y$ M9 ?; w1 vs(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)
9 I8 k* t  u8 `
换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

' E! C4 s1 o8 _{A,B},{C,D}
6 R! c' i: ~; W" m$ d8 M' [" O6 u{A,C},{B,D}
{A,D},{B,C}
0 O8 n+ D3 ?+ I* f: Y9 Y0 J{A},{B,C,D}
{A},{B,D,C}
5 N; @! t0 d# T# W) `5 t{B},{A,C,D}
3 W8 C7 e1 h) U; P8 @! ]* U* Y{B},{A,D,C}
, P) i4 \" F9 Q8 s0 `$ r{C},{A,B,D}
{C},{A,D,B}
9 d" A7 c2 k2 e  R5 C. C{D},{A,B,C}
{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)
: v& N3 B* K) Q+ D. B: iS(n,n − 1) = C(n,2) = n(n − 1) / 2
S(n,2) = 2n − 1 − 1
( g, p5 f  i* }  l/ w! }9 {
& x8 _, E6 G$ v- C( f换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

1 @$ G! t0 g) s9 x, |{A,B},{C,D}
{A,C},{B,D}
; P# n0 b) I" s0 T/ Z9 k2 d, a/ p* `{A,D},{B,C}
{A},{B,C,D}
6 a9 b0 |9 n% Q" H1 T- c. f( h{B},{A,C,D}
{C},{A,B,D}
; g* Z( H# P# Q3 `8 g  T* E: L{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

- s- l  Z1 |! f* U3 r
9 q, u6 C( a* u7 N' S5 Y# K% ln:=5;r:=3;
1 T7 A; x0 u: p' pEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式
/ E& n, r1 J1 ^# p3 T& s  D
! \$ ^$ B; [' i6 r, ]1 K( ]7 {26
( V; z6 S& b% M137/60
0
  U  h( [. I/ {) W' M0.000000000000000000000000000000
, Y2 E; t8 k( |# P% a, U$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
" e5 `- E9 {- I1 S) w( Z+ M
5 j5 A+ b# h/ G9 s" I伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

  A2 k( W% ?9 t拆分 。。。。强！
7 v# v% ~/ t5 t/ A! D5 z. N
+ z8 _/ A2 o4 U6 i. e7 iNumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;
/ v* a- N; G& `0 D# m1 s
7
- X8 Z' A) {7 k/ e) L6 y. Q+ A190569292
) i2 d! n) q9 k2 c1 x8 W9 X( P[
    [ 10 ],
    [ 9, 1 ],
    [ 8, 2 ],
+ R7 o& r, E, O# C    [ 8, 1, 1 ],
3 ~7 H1 }& Q- P/ ?1 v: I3 x% C    [ 7, 3 ],
4 w9 n8 l. [  x! ]+ ^% T    [ 7, 2, 1 ],
" T7 S  j/ E2 C, y" e    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
- q- R4 J( m0 b7 w3 Y    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
1 F/ B6 ?3 o  Q    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
1 ^4 \  k3 |$ ~8 f0 B& K% P    [ 5, 4, 1 ],
! A; B5 U) `' d# D+ }& x' _* `    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
6 j' v( S5 _, G9 G) R: M+ i    [ 4, 4, 2 ],
. b7 V. I+ T# J1 l$ W$ i" _    [ 4, 4, 1, 1 ],
' u' t0 X3 v. C* w, F    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
2 G# t. A4 P) I) O    [ 4, 3, 1, 1, 1 ],
+ R. v4 j, E$ {" k+ \    [ 4, 2, 2, 2 ],
    [ 4, 2, 2, 1, 1 ],
    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
1 w0 N) X0 M4 a# J( ?% |8 ~    [ 3, 3, 2, 2 ],
7 ?4 z! ]! }" o8 H    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
$ u8 B5 y6 q) v" e    [ 3, 2, 2, 1, 1, 1 ],
8 o' C7 c8 L% R! U+ F    [ 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 ],
! _4 W, C% k" I0 R* Q% Q, s. z    [ 2, 2, 2, 1, 1, 1, 1 ],
    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
+ E0 t2 }4 U3 x9 p+ A]

xxgzftj