一些组合函数

lilianjie1

n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
* W+ j. F% z  pNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
NumberOfPermutations(n, 4);
& t  _) x9 ^+ F; @NumberOfPermutations(n, 11);
" y- G/ N, a: W  h2 F# oBinomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
Binomial(n, 9) ;
- n; y) z; e; G# L* `# F8 v+ XBinomial(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
) ~! P  s- h! ^& ?6 a! _
Fibonacci(n);斐波数Fibonacci(n-1);
# ?4 B8 q/ f. m' Z+ }6 a  L% XFibonacci(n+1);
1 V- t  [7 ^: M% j/ N" kGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
GeneralizedFibonacciNumber(0, 1, n) ;
3 B. n9 d. _" c! XCatalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
. A1 J/ J7 @- |k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
; f) q2 D+ j, WCatalan(3);Catalan(4);
Catalan(12);

) n5 c8 p7 J* i, @Lucas(n);卢卡斯数
2 b# U9 E0 q4 z7 C& g5 e: t12
+ }; T1 ]- `, @479001600
0 S0 D3 O/ ^! h/ v( G831600
8 X/ ~; E0 }! q0 {8 f12
132
& c! S1 a  U7 V/ {" b11880
479001600
12
) _( {* d7 p& J, _8 `3 j1 l+ K+ a! O$ g9 h66
/ r  o" \$ l8 t. z4 q. m( I" B220
220
0 F: b3 {" d, J+ `3 t6 ~8 V/ d66
% A* E1 E' O$ Z: m! ~. b12
831600
4 A9 P% E! ~5 R. A$ q144
% u: t" \9 g2 s, O' t* J89
0 _# r5 H3 b. Y& i% e233
, A8 I4 G' w! M7 b6 t; q233
( z. ^8 Q' ?/ c' f5 \8 t3 i2 \2 D610
& k: a: E9 g6 _  r8 l144
208012
" t" s! u$ Y! H208012
/ ]+ E' m& u. C( K) B$ N, ^" q1
4 G* h: @( B0 A8 z2
8 V* Q5 e. O: x5
14
208012
322
0 O1 G" X' F/ R8 h% s2 o3 s
1 K  k8 k0 w( s$ A' L
. D% V7 r8 T! v% t; N% }. T卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
1 B6 \" F  G' z6 c**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
& ~( g/ m# b5 d. b- X
Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
% a: E; y- u4 \; ?Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

/ g; A7 q4 ?/ t+ P% V6 xCn表示对{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的情况:
% U2 s# w3 d- A0 ^+ \) A( J% H

. h: N2 {/ ]$ X* D% {
2 J1 i0 N6 ~  Q( L; x卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同


0 Y. ~# |2 w5 P- u
4 h% w! k, `8 U" L% \3 h2 P$ Cn:=100;n;
$ F! q1 l) J8 l, ua:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
, ?: v- C: L2 b% _9 \7 g6 m+ YLucas(n+1)+Lucas(n-1);5*Fibonacci(n);
; s3 Q2 j% n* b5 E! ~
100
792070839848372253127
792070839848372253127
) A: e* }, q6 r8 g1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

4 w# \1 F0 Y4 g1 T
反费波那西数列反费波那西数列的递归公式如下：

Gn + 2 = Gn − Gn + 1
1 A. ~/ S$ C7 o) l7 V9 @$ x) n如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

即是F2n + 1 = G2n + 1,F2n = − G2n。
- e; V, a3 l) N; F0 A4 [
$ U( y7 J" ?0 I$ X4 c" eBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
2
" e2 P" `# p+ g* e; E* I/ r& O52
9 [0 C3 m# o$ `* D  F$ V8 O6 `% U# y5
15
-6
11
; x- T7 U/ V+ N" j-6
1
7
6
- Y6 J5 A! t4 t2 z6 r
Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
* m3 `7 s0 w( |) `# [+ M- [
{{a}, {b}, {c}}
{{a}, {b, c}}
8 @) T, a; s* M$ A{{b}, {a, c}}
{{c}, {a, b}}
  _/ z  I, Y: K! q, L  l6 k+ ~{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

* F0 |2 D1 l: G) @' g换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
6 }3 F" A$ U& f' x
{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
7 t/ K: M" d3 Y9 T: h5 ^+ ]) y{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
; |' A7 |# j7 Y! i# }. S, [* }{B},{A,D,C}
{C},{A,B,D}
, d0 \% U& P! I{C},{A,D,B}
1 r- t/ B3 W2 n$ [0 ?% r{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)
! W' D/ n# x" u* VS(n,n − 1) = C(n,2) = n(n − 1) / 2
3 V' e/ e/ C/ H/ Q2 Y) C' d3 hS(n,2) = 2n − 1 − 1

换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
" z. u& _2 j+ R. \; {" B
. O+ G! p+ X$ s; c{A,B},{C,D}
{A,C},{B,D}
1 J' n  U5 g8 W# ~# ]! L5 d# j8 G{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
6 ^& ~  @/ V. n1 N  s" M{C},{A,B,D}
9 Y7 h" }2 r' K+ H7 r{D},{A,B,C}
6 `- y" Q/ U3 g! Z; O# b因此S(4,2) = 7。

lilianjie1

$ d. C7 |, g/ `) |) v: O% ]; qn:=5;r:=3;
5 j& f( ?+ ~! GEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
# T8 D: e* u# P' JBernoulliPolynomial(n) ;伯努利多项式

3 C0 h: N. ]/ u0 x26
137/60
0
0.000000000000000000000000000000
7 _. G0 D0 r5 ^  _9 ?$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

6 L) s- Z* ]1 Z* o0 E( G5 p0 m

% q+ ]" B; a. g
( H9 @; Z5 i0 {3 g3 `8 t( E* C& \伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
: e5 F( I# o3 K) @3 F
( z5 d. v7 z) m& Y. Z! {伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
; f8 `8 I! d$ T) h. ?

lilianjie

6 `3 @3 A0 x) X, V" E
拆分 。。。。强！
" g% u" q2 s3 G) l: F: K& o4 |
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

7
& g6 r) J( n; ?2 T/ J. M4 t  j9 q190569292
[
    [ 10 ],
    [ 9, 1 ],
    [ 8, 2 ],
    [ 8, 1, 1 ],
! m/ }7 l7 Y. Y$ n/ `. o    [ 7, 3 ],
    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
* O+ ?* d2 K8 \    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
5 h- W$ Q( r5 y: |: Y: e3 \    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
% W( C% l' b) x    [ 5, 5 ],
    [ 5, 4, 1 ],
% s2 x9 S& u$ X+ ^+ b    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
+ @/ u( K/ s3 B% B5 P& l, }. r    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
  v' l- M5 v& J+ m+ Z5 S) P# g    [ 4, 3, 3 ],
+ ^5 S6 Z) U. n    [ 4, 3, 2, 1 ],
    [ 4, 3, 1, 1, 1 ],
2 t) |- F; l' F( H) T7 i1 E# @    [ 4, 2, 2, 2 ],
  s, t6 X( d; C. s    [ 4, 2, 2, 1, 1 ],
& T% `' p* m+ \  K    [ 4, 2, 1, 1, 1, 1 ],
* D. O  y1 t1 b* q+ d/ \5 Y! C    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
- ]  f% G. D( d- N; r$ |3 u    [ 3, 3, 2, 2 ],
# o- B( {! W1 ^9 b) ~+ S1 I: i    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
' u. |' D, t9 C/ d! k    [ 3, 2, 2, 1, 1, 1 ],
2 p- ~0 s& I1 B% S    [ 3, 2, 1, 1, 1, 1, 1 ],
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
0 y0 _8 x) C: t" Y  T9 Y    [ 2, 2, 2, 2, 2 ],
, H( A& z0 l" Z+ D1 O    [ 2, 2, 2, 2, 1, 1 ],
    [ 2, 2, 2, 1, 1, 1, 1 ],
2 m5 |8 E7 z" @4 T- F! P* j1 d    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
! ~9 S2 y. W& j# {( W6 [# u    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
. y5 T7 |5 j9 {, N( j]

xxgzftj