一些组合函数

lilianjie1

n:=12;n;
) h6 G% ]9 M4 m* \7 ^8 xFactorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
) k/ K, Q# L3 p4 G/ U  s# C! Q7 ANumberOfPermutations(n, 4);
0 r3 n7 H8 @+ YNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
' q2 ], u  @; \Binomial(n, 3) ;
Binomial(n, 9) ;
! r9 L  i9 {* p) I) W8 Y9 Q4 ABinomial(n, 10) ;
1 A1 ~& q/ \  L0 ]; }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);
3 I- O# U- l7 r! D; Y7 IFibonacci(n+1);
( T6 @: u4 |! @$ r" w% ]9 r. }GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
GeneralizedFibonacciNumber(0, 1, n) ;
5 J+ s/ k6 w/ h) oCatalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
) t$ h% k& I- M8 WCatalan(1);
Catalan(2);
Catalan(3);Catalan(4);
$ @7 S. ]  U! \Catalan(12);
; ^/ e' \! {& ^
' c  [2 x2 ?; Q; d: F3 M2 s( fLucas(n);卢卡斯数
0 b' X" R9 [3 G12
( J& a! R9 z8 v5 ~2 m8 v/ B479001600
831600
12
132
11880
- [. P. A- h* b1 r, C  s6 j479001600
12
66
220
$ a, N* k8 _' p# w5 m6 C220
& o9 Y- F( _/ L- R3 z% ^3 O. m% S3 _% p66
( e) ^2 b& W* \12
831600
: F/ f+ g- t2 {0 O7 ~144
89
233
233
610
, w1 n. O' F% c1 w6 Q% Z0 [144
208012
208012
: Q/ a: k/ \8 m1 U0 ~1
2
  e! ~) x. E1 q) W0 E& W! H5
( }1 N/ [5 c  {0 y+ O" }* K: _7 ?2 i& e14
- e* H( i; x3 r9 A: |8 \2 ~' B208012
8 i; J' m  _# L/ l& u322


' e  c$ ]5 n7 j& E7 {5 y卡特兰数=(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个叶子的二叉树的个数。

Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：
! R2 t, N5 B; ?4 b( h' J
Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
8 T) d$ y+ |: s; z0 kCn表示集合{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.
7 U0 j- V6 c! @+ Z% k" UCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:
/ _/ l2 V9 E4 f( h

9 R! E" d& w$ E" s! t1 R* U
卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

0 t" V) R) k# G: F: M6 ^9 S但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同

1 z. R  E4 `0 ]: Q, O$ R8 K" i
5 k5 [. _& `9 Q* X0 u& o5 M
n:=100;n;
a:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
$ {" K2 @7 l5 uLucas(n+1)+Lucas(n-1);5*Fibonacci(n);
. J+ \- s5 ~, G
100
792070839848372253127
792070839848372253127
1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

" X$ a( t) A- W
2 K$ V" d+ b( p/ p- S- J  l/ A  n反费波那西数列反费波那西数列的递归公式如下：
" p0 j2 m" G/ X& Y$ D% V
Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
( W  `. n4 w$ e4 C
7 o3 A# x# Z0 ^0 \! y( L2 t9 {即是F2n + 1 = G2n + 1,F2n = − G2n。
8 R$ D5 U3 R/ w# A* R6 {& a1 J
+ K# X  a: ^8 R5 D6 O8 R2 p' aBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
7 s$ K3 y. b9 t! B4 gStirlingFirst(4,3);
, C, _7 w" G6 S% i6 x" U% p+ T. B( {StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
5 X; d) |0 b7 v+ J/ NStirlingSecond(4, 3);
4 y$ L/ p- ?2 O1 E# U# l% ]- S, ~- K& t2
52
5
15
-6
11
-6
/ @& L/ O- r, r( G" F1
7
* }# {, _2 g  _6

% X9 L3 d/ q! R* tBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
9 r6 H7 [' m' F1 O2 }) F
{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
9 W- d, C+ T* T3 M/ N% Ps(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

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

{A,B},{C,D}
{A,C},{B,D}
! s8 r# m+ M" c0 f7 m{A,D},{B,C}
& B, L- U2 {8 S6 U{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
- n, r1 x, o1 ~& O7 n. ~{B},{A,D,C}
1 J9 Z% H( _7 A+ M, u1 x( O' X{C},{A,B,D}
{C},{A,D,B}
{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)
/ y* Q3 ?& e7 Y3 U0 z* Y% oS(n,n − 1) = C(n,2) = n(n − 1) / 2
S(n,2) = 2n − 1 − 1

' A+ I/ \% V! o) ~: J9 ^$ O" G换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
1 r; c! ~& N/ {+ }9 P# x
{A,B},{C,D}
% I% f, \8 a  x- }" K7 Z2 b{A,C},{B,D}
{A,D},{B,C}
9 `1 n5 M  ~0 E) z9 b{A},{B,C,D}
4 p3 P1 D2 z/ A8 v{B},{A,C,D}
. H8 l* @) S+ A' v, w0 j% K3 Q{C},{A,B,D}
+ K1 C' p7 z& C- w. ]+ x{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

5 t; R) I2 L8 X+ V  r2 A; cn:=5;r:=3;
* M+ w* h+ J! e# ~8 MEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式

26
0 r; I7 t8 l& {; E2 _1 ?137/60
2 L5 x' o; S1 X! x: y  ]0
0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

8 L3 \9 c' F+ j
0 f7 x" a* O. D+ f) s伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。

: E: a, U, E, M* S/ v# C伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

) h; r+ g7 s2 N; R* m拆分 。。。。强！

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

% w: S# d* H1 u3 P1 T, k7
( j$ Y% Q$ v& D190569292
[
5 z. i5 i/ n$ C8 r# W5 ]! F    [ 10 ],
/ H" u2 _  B5 m5 ^# o* O- X    [ 9, 1 ],
    [ 8, 2 ],
    [ 8, 1, 1 ],
; m/ ^) c4 A# s/ x    [ 7, 3 ],
2 I% k0 Z6 Y% L+ F% u/ g+ x$ n    [ 7, 2, 1 ],
( S9 r0 T/ c" z9 V: R$ X% m    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
    [ 6, 3, 1 ],
# ]! R. x$ d+ s% y    [ 6, 2, 2 ],
. O" O! s% H# [1 t+ s    [ 6, 2, 1, 1 ],
! z) s5 Q  x6 s) m6 S3 ]+ u# s) W    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
    [ 5, 4, 1 ],
5 A+ E: N. q1 O1 ^8 R5 J    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
4 B0 H+ D$ G( D7 C    [ 4, 4, 2 ],
" ]  o$ Q0 S" c    [ 4, 4, 1, 1 ],
2 Q# ~. }% J& j' X! t: w& z9 b    [ 4, 3, 3 ],
% v2 p6 w1 Q$ j0 i    [ 4, 3, 2, 1 ],
) j9 e8 g# s1 j# A( ?9 {4 z9 y  v    [ 4, 3, 1, 1, 1 ],
0 {+ b7 @- w2 G' [  C  N5 Z/ a6 O    [ 4, 2, 2, 2 ],
) U+ W3 Z8 z3 N' m) S, G% ~    [ 4, 2, 2, 1, 1 ],
, |$ o5 F6 k& Y- Z    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
1 }; [) i  D7 l/ d    [ 3, 3, 2, 2 ],
) O$ T9 F6 U9 _2 v    [ 3, 3, 2, 1, 1 ],
& z4 z) t; X2 v, m' @8 I    [ 3, 3, 1, 1, 1, 1 ],
& m' J0 g2 e0 e. v6 v/ J# Y) M    [ 3, 2, 2, 2, 1 ],
    [ 3, 2, 2, 1, 1, 1 ],
  t! v0 @; M" d& C    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
    [ 2, 2, 2, 2, 2 ],
/ s5 n/ \+ \3 O- s: K, s7 E- E) m% c    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
3 R: d  b! G7 m, Y    [ 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 ]
) L; n5 X5 h% C$ A]

xxgzftj