一些组合函数

lilianjie1

( k6 I0 F8 v% |5 M$ }" B3 C, b' N$ t
n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
7 s) {0 _/ g8 ^. ANumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
1 \8 V- ]% {& c- uNumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
Binomial(n, 9) ;
# ~# _( {5 A) Q4 R( T9 n. \4 y3 XBinomial(n, 10) ;
( k; H+ w, h, w2 S, l) F7 W% EBinomial(n, 11) ;
% N% Y8 E9 g+ N- G6 fMultinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600

: N. |# X, R) k; bFibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
GeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
& ]9 j4 V9 z, E1 h/ |! M9 G& xCatalan(1);
- D# R' O& I1 J5 Y- ]6 j$ H: qCatalan(2);
4 {- f5 }+ Y( c0 P* uCatalan(3);Catalan(4);
Catalan(12);

) Y) l7 u! V, K$ b) S5 ?9 YLucas(n);卢卡斯数
) E; Z' E. W3 I12
479001600
) x( n1 N6 [2 j; s# F  |8 y831600
12
) X7 q! M2 p% `. }* P132
3 q) V' z: w. }, Y9 |  o& l# ~2 \! ~11880
479001600
: B# Q0 `* y, c0 W5 E12
2 c; N* j; x) T, e. A" D8 Q: Z0 E( E66
220
- C& m8 X; `: J" Y220
# h) w8 r9 Q( I" n. ~66
12
# t, ~, M; V6 x+ x- j& ?5 r831600
144
/ r, E4 y0 A6 l4 U7 U; G89
233
233
610
144
/ L. Z3 x: L0 m208012
208012
1
2
5
( W* R; |6 ~" k- g' K: H8 i3 r14
" x% m) H* f0 Q! K$ i2 ]208012
! u% v, \  n6 q# q& e% H322
. S4 N" ?1 W( V

卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
; r! }! C+ M% f) z/ m9 ?, O
" ?3 Q- f% L0 j8 p7 E; yCn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

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.
- U5 x( D* x1 c, Y% e$ ~; R, cCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:


6 t& n, X% e' i* G4 Y1 [6 N% X9 V
卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

) E  T, y4 E2 ?% m4 _$ J! l但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
0 V1 p& M5 |4 `! O. v! B
# `+ M  r; l3 T' w4 `
5 W  i3 [( {' s  ^
n:=100;n;
( G/ _6 t2 d# D. e+ oa:=Lucas(n);a;
. W* t9 W7 s, Wb:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
! {1 z( e" a# |- @1 B; x4 O
100
  Q6 @) j6 c4 _5 n# [/ G" X1 n792070839848372253127
792070839848372253127
1771124240896309575375
+ e; Q8 Q* L$ t0 @7 L" r1771124240896309575375

孤寂冷逍遥

lilianjie

4 \% U2 V$ s- T
& r0 }- y) d+ D+ W反费波那西数列反费波那西数列的递归公式如下：
' I, Y, Q6 w  V: i- P( l
. U: L1 Q/ @4 C: n+ Y: e. ?Gn + 2 = Gn − Gn + 1
, }5 a/ h. I8 v如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
& P* q/ z3 u! F& r1 J
即是F2n + 1 = G2n + 1,F2n = − G2n。
1 _* t6 v0 y( F; K% i8 K& c0 D9 |% C
. ~# M# x9 N; ^) b% KBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
9 c4 C+ g1 G7 F8 q& |1 WStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
2
52
5
15
-6
11
; K3 u9 z% G/ c* [% X2 N/ t-6
1
2 [" L% W1 P' z* M% H7
6

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

{{a}, {b}, {c}}
9 ]. A! M0 B' Y2 W5 L! ~" a" S{{a}, {b, c}}
1 [9 d% Y4 c2 U- [7 |{{b}, {a, c}}
9 ?/ U+ E' [0 L! A2 t9 _* v7 v{{c}, {a, b}}
, A8 d+ ?1 N* ]) \2 p- h- @6 D- b{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
% t* i/ R, L+ rs(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

) g# J+ l. j4 x换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
2 }) C0 ~' T3 u! C
{A,B},{C,D}
" Z2 }; H, L& Z: ?- ~) K{A,C},{B,D}
; q) r4 T& @2 Z  x: }9 _{A,D},{B,C}
9 v8 d2 l- O: p{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
: j  a$ _& e- ^{C},{A,D,B}
0 ?: \- [4 L. b* h{D},{A,B,C}
{D},{A,C,B}
/ w& ~8 s5 ]+ c第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
; Y( x5 I, z* j  ^5 k: [4 E给定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
$ e1 h; u7 l6 R* Y# k. S, \S(n,2) = 2n − 1 − 1
, z$ l2 A4 p1 P. v# u
: ^' ^# K/ t; d6 }2 j换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
3 h  \% p: n3 b2 F+ e8 G
{A,B},{C,D}
{A,C},{B,D}
% n) H4 |8 [( A+ G9 Y{A,D},{B,C}
5 `4 ~8 g* Z2 u2 q3 e0 |8 d{A},{B,C,D}
& I2 M2 U  p- z  I/ a{B},{A,C,D}
  i. N( Q6 k+ n: k$ s1 D{C},{A,B,D}
0 L) x9 `7 ?5 C{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

+ N! v; K$ V. j, u9 n# kn:=5;r:=3;
) ~% V( T0 F7 g0 I; e: |EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
8 b: s) _% `+ t! n' r4 A0 f) lBernoulliPolynomial(n) ;伯努利多项式
1 A: t8 C3 O: a! a4 C. p4 b% u7 U
6 B" v  X& a7 I3 b2 R26
137/60
/ c) w* d' Y" T1 A0
0 K, S8 P2 G. @& a0 D$ [0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

% \! S$ g1 C- y$ M9 Y7 ^. V/ c5 Y; E

! @; p; N7 R; P9 @1 G/ K
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
3 ~0 Z, b9 h8 `3 B) O2 j7 i2 [' E
8 L" o, i* U$ U2 B$ k伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

拆分 。。。。强！
2 O+ T5 m( U3 }/ a
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

4 F6 |" g" R( s1 q+ @+ f$ E7
190569292
& U0 y6 F$ U" @) _& D. Y[
' c  g7 x& d3 U# C) N, s    [ 10 ],
    [ 9, 1 ],
    [ 8, 2 ],
    [ 8, 1, 1 ],
0 Q8 e, D+ N  J    [ 7, 3 ],
    [ 7, 2, 1 ],
- a; {# r9 E- g, e" Q! w    [ 7, 1, 1, 1 ],
* c# q3 k9 X5 g- \% b    [ 6, 4 ],
- q+ G9 s" M6 d6 W- @8 x# B    [ 6, 3, 1 ],
6 }7 P* `, k  m! m3 ^    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
% |4 ]" s& l( _+ [' [0 z    [ 6, 1, 1, 1, 1 ],
/ q( L# r1 ]/ I: y0 E% {4 N    [ 5, 5 ],
) R# M  q$ w, n0 o; _9 n    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
+ J; B2 Q# B7 V    [ 5, 3, 1, 1 ],
7 f9 }) Z' Q! J0 u) p    [ 5, 2, 2, 1 ],
( H# X$ p  ^# q( X' r    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
7 \$ }' ?0 N" o. u% W3 o, S! N    [ 4, 4, 1, 1 ],
    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
, P: b8 i6 d3 r/ T* z8 N3 C    [ 4, 2, 2, 2 ],
' @4 H. q3 \7 ?+ _! o+ X    [ 4, 2, 2, 1, 1 ],
# Q/ T3 o# x, {$ j    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
" t' x4 z7 S# W' H$ U# V    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
9 J  N6 t, C0 ]- c! f) j& y3 l    [ 3, 3, 1, 1, 1, 1 ],
    [ 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 ],
    [ 2, 2, 2, 2, 2 ],
    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
  g6 X. k  G. F    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
1 Y) f5 Z) d# o  E    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
! N- S5 x. r1 x' b% x]

xxgzftj