一些组合函数

lilianjie1

n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
, I& g9 a0 N1 |& V0 _, ZNumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
6 @. C' d, }1 cBinomial(n, 9) ;
& ?* E! R! ], o- QBinomial(n, 10) ;
% H5 Q" f+ T% S# LBinomial(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

6 F1 B% v: v! l% y. L7 A5 dFibonacci(n);斐波数Fibonacci(n-1);
: I; ?5 Z( g2 W6 R( Y% oFibonacci(n+1);
8 e$ |" F' d& V3 k' pGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
GeneralizedFibonacciNumber(0, 1, n) ;
3 q# y$ t- ]2 o6 X' L" qCatalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
* P6 M( Z( j. G1 h6 o# m8 Q4 pCatalan(2);
5 ~; ]8 z  E. [8 d9 GCatalan(3);Catalan(4);
$ D  M3 p5 ^7 f7 u, oCatalan(12);
- f# U1 o( r+ ?/ A2 b
Lucas(n);卢卡斯数
12
479001600
  L' Z9 Z8 u; C+ Y4 w831600
12
- n. W& o. K+ A  T- B! v+ G132
11880
; g9 R3 ^* G$ X8 ^+ v  I2 a: g1 O% ]: U479001600
% ~3 Y) n+ A; M# ~& v' d12
- ^( X) p7 F! o66
# l$ t; F$ B" B( }& V! N9 g* q220
220
66
12
831600
7 `1 n- q& C/ }1 j+ o% X144
$ Q! b; h8 D  W. p; b) V: I9 s( a89
/ n( l& {7 X; [+ Z233
$ |& \. Q+ [% S* ~1 \233
610
144
208012
208012
1
2
7 ?5 C3 ^! G! P8 Q; ^2 q( y& j! _& ]5
3 C4 j: n8 Z9 G5 C# u; U14
208012
0 Q. f6 A$ M* l2 U" c0 K322
8 Q# f# Q4 E" F) w2 Z5 s  Y

% ]) }- `1 S+ a  r/ N' a卡特兰数=(2n)!/((n)!*(n+1)!))
! K8 X+ G# K  T2 P# A# I! ~" {0 ^Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
6 V6 l% d. E% D$ a0 l/ g6 D7 s将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
0 K! Q) {4 t& N6 e; R8 k- w((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
+ o7 V" S" B1 h( b
Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

8 v2 A+ J0 W* C' ^4 SCn表示对{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.
# o% x8 N- ^, {Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

8 V6 |2 m7 I) a

卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
3 C- H. i- @9 C: \4 `
" N1 g5 h8 }  U2 P3 S# O但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同


* o1 y7 ~. u! s/ T6 s
+ b- p- s, D0 a. Bn:=100;n;
+ S6 j! ^- P& V4 b( [/ T, fa:=Lucas(n);a;
6 j2 a; M* F# S: zb:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
8 n5 W, D3 `  ^0 q, A
  S* Y' \! @# `& ?0 r  V100
+ \. p8 n  J; C, A6 m792070839848372253127
6 j5 r! i' ?& d9 T0 f) V792070839848372253127
1771124240896309575375
: \2 N6 J. T# X9 t: M( Q1771124240896309575375

xxgzftj

lilianjie

( G- N+ ~/ R# H8 }
拆分 。。。。强！
& Q; j/ a$ F$ p6 ^* t3 t5 w
1 w% [' A5 Z% }# CNumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

4 n2 O& J( z: I! K. S2 E, e8 ?& h7
5 I- Z9 v0 D% ^6 m2 e& C190569292
[
, w8 F& B; E/ G; ]& _    [ 10 ],
) b/ m3 r& s9 s9 l% o& T    [ 9, 1 ],
    [ 8, 2 ],
    [ 8, 1, 1 ],
    [ 7, 3 ],
8 q3 Z# ]3 O/ w5 y& A    [ 7, 2, 1 ],
7 I$ s- W- y7 {1 z2 F- P    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
3 a  E' m% G6 B! `4 _- e    [ 6, 3, 1 ],
. S+ n2 p5 q/ A" z- `) c5 |2 B    [ 6, 2, 2 ],
2 M/ a; i5 A0 N; d    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
' i8 ]. U6 k, j1 w# J  \    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
% @% m$ A6 M' }$ [' Y    [ 5, 3, 1, 1 ],
; e, S( z& b# z0 e    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
7 l9 w/ R. a+ M8 N& e    [ 5, 1, 1, 1, 1, 1 ],
/ ]( w1 i% `) p9 x( v    [ 4, 4, 2 ],
( c1 u3 G: T! Z" B' X. R8 J  B    [ 4, 4, 1, 1 ],
9 K/ b9 s% V0 G3 P8 J# K2 x2 a    [ 4, 3, 3 ],
" R  l2 Z& {3 }* [    [ 4, 3, 2, 1 ],
! ~6 l: d6 G# F- v  X: l    [ 4, 3, 1, 1, 1 ],
5 h& i$ V& ~! p9 T    [ 4, 2, 2, 2 ],
& y  V) f$ w3 g    [ 4, 2, 2, 1, 1 ],
0 X4 D/ J5 o+ W3 V    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
, z' K% ^. x  `# s! S3 J2 q    [ 3, 3, 2, 2 ],
7 `8 V6 m: P! ^! {0 }  J3 D* u$ ~7 U    [ 3, 3, 2, 1, 1 ],
- Z+ ~# |4 j5 t    [ 3, 3, 1, 1, 1, 1 ],
& L3 J) J- O4 T+ v3 l4 s$ R0 L    [ 3, 2, 2, 2, 1 ],
    [ 3, 2, 2, 1, 1, 1 ],
    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
8 T4 j* F0 L2 Y8 B! s2 v- j& n    [ 2, 2, 2, 2, 2 ],
    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
, i, g! r1 L1 C! g& U/ F    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
. G  u2 ]0 Q/ a    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
]

lilianjie

6 m  c/ Y# k5 o* u1 g3 U

; n" }* k/ j4 C  E( w
) s9 k2 u& u2 F) X伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
. a8 D; \- I: w; P
* `- K9 I1 l" z. W( I6 p伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
* j7 P* `4 x6 c$ t9 H6 l9 [

lilianjie1

3 C5 w+ {4 R9 @& a$ Gn:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式
- ~, F1 W9 l; X+ t( r" E% J% f( I
0 k- u2 B3 ]+ `# N0 D' A3 u26
+ T1 q, |/ N) `/ `8 D137/60
0
0.000000000000000000000000000000
2 s$ @. B  O4 B* {7 f, Q7 b7 Y$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

: A/ a0 _. [+ q) M* i
反费波那西数列反费波那西数列的递归公式如下：

Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

4 v* x# N. w5 R( H3 ]) e即是F2n + 1 = G2n + 1,F2n = − G2n。
5 Q" ?( F: e3 Z" `$ J9 A( f
Bell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
' G7 X/ G, a# a& x% P+ IStirlingFirst(4,3);
2 h. ^5 \  _: }$ ?$ eStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
! w0 U' g3 p  [" p, E5 k8 {  YStirlingSecond(4, 3);
2
: Q+ F5 S- w5 H. ^52
5
7 m. [- a. C6 o$ _0 r* _  V15
) j1 [& Q' U6 m5 F% g-6
- P: ]5 P7 j( _0 I* V11
& U7 u# `) t& ?* }-6
& T1 _# Z  r) _9 s# m% X3 M0 Q1
7
' S) \4 i; _; b/ t' d0 w1 {! y2 b6

Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
; H# K5 V( d2 a0 J1 W; Z
* t: Q/ w9 v) j/ H% w" @{{a}, {b}, {c}}
{{a}, {b, c}}
1 j- z6 f6 z. S$ |: G6 k{{b}, {a, c}}
{{c}, {a, b}}
+ b* K2 }2 w+ K9 `  T{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
/ x% y1 y6 [" [s(n,k)是递降阶乘多项式的系数
; }0 B1 l2 l) _2 f6 P: q) M有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)
& U7 k( R* X, I  a9 C1 M
换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
0 z+ P9 y3 f/ k4 _/ K) x' r{A},{B,C,D}
{A},{B,D,C}
% }# S( k( b) A! D6 V{B},{A,C,D}
, c7 a; w& C* r: ^{B},{A,D,C}
( b. a" h! R- E3 j{C},{A,B,D}
. D* D+ H# P% W1 y{C},{A,D,B}
  g+ p( U' L( N8 {; o% o2 ~{D},{A,B,C}
{D},{A,C,B}
- X6 |3 `0 t/ z- L/ G3 e6 x- O+ D第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
* h3 x& ]- l+ S给定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
S(n,2) = 2n − 1 − 1

换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
$ ^" k1 T- U, I
! N! L4 m* O5 E$ U2 w/ W{A,B},{C,D}
{A,C},{B,D}
1 Y1 W6 O. ?) m7 w{A,D},{B,C}
{A},{B,C,D}
6 Q- @$ F) K8 k% ?: G, T{B},{A,C,D}
{C},{A,B,D}
5 x/ z9 r- j- r+ e{D},{A,B,C}
因此S(4,2) = 7。

孤寂冷逍遥