一些组合函数

lilianjie1

8 U  j6 w" y' |
n:=12;n;
Factorial(n);求阶乘
# |3 w0 o" l( i7 T2 ]& [Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
6 j% c2 Q3 F' y5 ONumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
; B" ^; c* [) `6 |- ~- [Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
: W4 r2 k, t& \8 V+ P+ h( sBinomial(n, 3) ;
: p7 Q( J. C, K, y: F4 |3 EBinomial(n, 9) ;
3 y% g% g+ I* @0 F! o5 p" x! QBinomial(n, 10) ;
Binomial(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

Fibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
/ |! k& Y1 Z2 dGeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
: Q1 M8 a6 Y& ik:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
* w" N& y/ \. n+ g- d  K% O% v( T. [Catalan(1);
Catalan(2);
Catalan(3);Catalan(4);
Catalan(12);
8 v  k3 M& }' \: v
Lucas(n);卢卡斯数
12
479001600
831600
12
132
11880
479001600
# {8 L. L* M0 c; F: v* p12
66
* R) f/ |# \4 {220
- [+ K4 R; h; [1 A' J& A+ M220
66
12
5 c2 h" ]% _+ h& G/ y( ?' P7 F831600
144
89
233
233
( k' p& D% v7 _  X6 R0 I3 v. V610
) N7 a9 R$ ?+ s3 Y8 f' z$ w144
- ~! O( N4 Z2 f208012
- x  F* p+ \# U, @208012
5 I- x  e% g5 X) F4 g1
2
5
8 w4 r& ~. E- e$ [, l4 V0 s14
8 h9 }0 B' Y0 Z- e  x/ k208012
# @- Q9 S! _8 d: t1 E9 W322

5 q6 y% q3 A) F+ ?+ O% K
: m( R+ [: K! L) j. T卡特兰数=(2n)!/((n)!*(n+1)!))
- J3 X4 B5 d9 r& g0 b* wCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
8 @: P) w! K! x1 G4 k) S% s( a5 E将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
, H2 E6 f% z1 B% c( Q((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
* f" g# g; x) r5 H+ g
) x. t2 t2 ?" A: S% T( m$ m1 ]Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
- j( }7 F6 R6 q
9 c! g' k. ?" V) A4 E! P8 ~2 FCn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
# T6 J4 \. E' ~: g, K/ gCn表示集合{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.
% ^% G; B; U5 l; eCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

1 L: C) C" p; o

卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
$ k: H7 A2 N6 y: H2 q( P2 i
但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
+ V2 V! t  c4 X1 z7 b' e

0 v3 k3 y8 H: i- I9 u
n:=100;n;
a:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);

) |7 r$ R  [; D0 B8 T; ^100
792070839848372253127
792070839848372253127
1771124240896309575375
  d3 @" E# T# ?1 n1771124240896309575375

孤寂冷逍遥

lilianjie

! ^5 e6 B  l( t7 x' Q* I) w* p
. y9 h8 H2 p1 d/ {) a# P/ V反费波那西数列反费波那西数列的递归公式如下：

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

0 O1 A/ }9 O  G5 o/ h2 l即是F2n + 1 = G2n + 1,F2n = − G2n。

; j0 I& o  R3 [; rBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
) g3 S% v4 C: B$ LStirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
$ R8 x' }; T1 S9 ~" y+ PStirlingSecond(4, 3);
4 N8 l4 H) `$ x4 x; j. M2
52
; e/ m2 q* f/ v, f, j+ E5
15
" R) q$ Z) }( c6 m4 I-6
11
-6
9 u! i2 S1 n6 w1 A' `1
7
6

Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
: ?$ G- L3 ^: b4 {9 E
{{a}, {b}, {c}}
; ^7 b( U. \- S. o6 Q* |  g{{a}, {b, c}}
+ E0 O1 u  c8 P2 X. [- H{{b}, {a, c}}
{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
+ M' L6 \+ x' ]3 @6 A有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

; K7 o2 w7 _$ M. j: j{A,B},{C,D}
- S7 l& Z4 D$ U0 I/ t) S{A,C},{B,D}
{A,D},{B,C}
0 _2 W" e8 B$ l! g% _: z; \4 n* u{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
{C},{A,D,B}
{D},{A,B,C}
{D},{A,C,B}
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
( D, E7 a. K5 q8 V% H0 j给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
6 ^/ N9 J) ~9 f% kS(n,n − 1) = C(n,2) = n(n − 1) / 2
( e6 {8 |3 f4 K3 v" q; LS(n,2) = 2n − 1 − 1

- H; [! O$ P! F1 e$ _' R换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
* i9 |0 Z# Z2 z, H/ w/ e. `; k
2 k( W, v8 E7 \/ b% {. ?{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
4 u  n' L4 |' t8 G# O6 J{A},{B,C,D}
6 o- l+ p8 E% o{B},{A,C,D}
{C},{A,B,D}
{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

8 h4 d$ C  n6 K) ~+ w! v8 v
n:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式
; j/ F6 A! N1 H/ U6 k" O8 q4 ^1 h
: v6 p; J- [) K; o7 z7 m26
137/60
9 p9 w* {  s+ s5 S5 t: [8 M0
0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

* u4 `( _- X: h4 c

! u- L$ z, S/ `/ |4 l' ~4 e1 o9 ?
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
; o4 |6 n9 K# M0 y
8 P5 e5 R/ q# Q' s伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

拆分 。。。。强！

NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

+ Z! ], v# _5 P0 I& @7 \7
% o5 I5 d9 a1 X$ m0 K* Z190569292
+ s+ O; w* Z2 `, D' Y' o2 g[
    [ 10 ],
. g; b( j, o1 I8 d% Z% Y6 l: _    [ 9, 1 ],
    [ 8, 2 ],
( F, s& A6 ?6 T4 f4 J9 V    [ 8, 1, 1 ],
/ O, k  K' Q( I: R    [ 7, 3 ],
% L! j. l+ y. P6 z: ]* U    [ 7, 2, 1 ],
+ ^  v% Q+ e7 V/ Z$ X/ c    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
0 [  X( |0 \/ O/ ~) K    [ 6, 2, 1, 1 ],
& H2 D' A$ f- T  R$ r9 j9 @    [ 6, 1, 1, 1, 1 ],
& q  a# M6 V1 ^6 B$ Z) {    [ 5, 5 ],
- ^9 w" q7 D- H2 l* t- r    [ 5, 4, 1 ],
0 I* m# u9 z& p* ?    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
: c4 G" V( k& Z+ F! Y6 _* o    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
- d  ^4 a! U( e( @4 \& l8 g# }    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
) ~' C9 K, U& b. u1 M    [ 4, 3, 1, 1, 1 ],
& p  Y- v( G7 b6 b/ |9 b$ H    [ 4, 2, 2, 2 ],
7 f3 H# b7 s) f    [ 4, 2, 2, 1, 1 ],
    [ 4, 2, 1, 1, 1, 1 ],
( _! L4 M7 }' M8 h1 h+ f! Y    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
( W9 W! Q& x" l1 M) l2 y    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
    [ 3, 2, 2, 1, 1, 1 ],
* v2 _$ z7 q5 M# q1 @& s    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
4 f* a  c& W  B7 D, o! p& A( [2 f    [ 2, 2, 2, 2, 2 ],
3 q) n; ?+ Q4 U* E    [ 2, 2, 2, 2, 1, 1 ],
/ @0 r+ r8 _: ~  G' j5 f' K    [ 2, 2, 2, 1, 1, 1, 1 ],
0 n2 ]! O. H4 }, I4 @$ F    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
) F# U  K' D3 \2 m5 L) \  s* e( }    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
, _, _1 k+ t' a# Z* w  L]

xxgzftj