一些组合函数

lilianjie1

n:=12;n;
Factorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
NumberOfPermutations(n, 4);
" ?# r+ U3 C$ E, YNumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
5 b! B: h" V" l% A$ E, O) wBinomial(n, 9) ;
Binomial(n, 10) ;
Binomial(n, 11) ;
. g, W# a, q2 }8 Z! vMultinomial(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) ;
3 O. Y/ z2 _. h2 a. T2 o& S* QGeneralizedFibonacciNumber(0, 1, n) ;
5 e' N) [# ^/ i9 f  ^Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
' n7 f2 x3 B- w4 z8 m& N& UCatalan(3);Catalan(4);
Catalan(12);
- l) I3 H2 S3 V+ x
Lucas(n);卢卡斯数
+ [* O0 k1 J* x12
* ~5 j5 E# @) H+ ~479001600
& S$ {* ^3 A5 ^. \831600
3 }7 t5 U/ c/ L/ X* V) T12
' D  [* q% ^+ x1 F132
  M- S1 t& T- w3 Z1 O: U) ~7 ?' f11880
479001600
2 a# e* @: Q/ e: X. O2 W1 Q12
66
( j3 r8 H2 p1 |8 [+ \220
220
66
) C5 k( X" f7 t12
) o! a! {% u' h3 i831600
+ p& f; i( a$ \5 w, K144
: F# ^# v4 ]% ^! P6 w9 n% Y7 Z89
233
* q1 k% Z# W+ ^% y) t. B233
7 V% h1 v# Q8 [! H610
144
# @4 h: a/ ?% w$ z3 F) C208012
208012
1
' |# Z# ^( n; g" ^$ i5 S: l$ z8 X2
2 G4 D/ p# L: C# }3 u5 e  {0 }5
14
208012
* z9 O4 W. p" E0 T6 J4 }322


卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
( z4 u) L( f: M1 O  t. w& ?* k**YYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
Cn表示有n+1个叶子的二叉树的个数。
1 ~( @8 H. v  ~
) ]( E6 s0 e% A- J" z8 wCn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
+ g& L" N, _0 M0 l3 \9 UCn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

) `' d3 Z+ w' b% r5 J( q) S& JCn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
# V; f; e  C- A) N; E" w# \2 M7 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.
7 F! [3 a8 r# h) _5 ~& I) ^Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:



0 A& ]) }! }8 ]/ ~卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
- J6 f- F6 k# h% z* @- }
但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
) N& U9 h- {0 Z4 ^
# t, s- Z3 h1 F) j" }# s! e

. F7 z- c2 A' E5 s7 \5 T" ~n:=100;n;
a:=Lucas(n);a;
b:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
2 S5 _) d8 j% x
100
) Z% j5 p& q' V0 P/ `3 \792070839848372253127
792070839848372253127
1771124240896309575375
- o; L; G9 e. I; \4 ^' U1771124240896309575375

孤寂冷逍遥

lilianjie

" @. N6 g9 i' A+ a7 @' F. |# J3 `反费波那西数列反费波那西数列的递归公式如下：

. M' D! ?2 [' O* YGn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
1 H7 u! w* x2 R5 ^
( }8 }9 I( c, `3 S( m4 |即是F2n + 1 = G2n + 1,F2n = − G2n。
! v1 Z8 s! Q9 I1 l: \
Bell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
; _8 q7 D$ \" f1 dStirlingFirst(4,3);
: `1 j* ^6 ]' A0 r7 z; `7 @  FStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
& m# E. W7 _; a) [. }+ ]2 o2
  K( A% `/ w! p% p  ]1 R52
4 N& J4 O" Z7 R5
* h: p' x" I% M6 a15
-6
4 ^& V, a/ v2 O11
-6
1
7
6
$ U, p: H/ l8 h2 }
/ B! T. M; Q7 p$ v6 N% l2 j3 F" I& nBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：

; X. h! ^2 H* }% `& N/ e$ d{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
{{c}, {a, b}}
' j# s6 H0 n1 d{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
2 L" u0 O; P8 ?1 d% ]5 P有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)
7 W: Y  H" b! Q1 F4 H$ U
换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：

! C4 p/ G" ?2 r  L{A,B},{C,D}
; g+ ~# i% d8 \7 R2 @{A,C},{B,D}
{A,D},{B,C}
0 @, R' Z: C5 e, |9 H+ }{A},{B,C,D}
: \% g! i/ X7 I, r, [{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
9 i# v5 X) V7 f{C},{A,B,D}
{C},{A,D,B}
; s2 U2 |* \) h1 |3 b" J  ]' K$ i3 ]{D},{A,B,C}
; Z2 k3 P( J* j6 I6 V7 m* A% t7 C{D},{A,C,B}
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
- I. {- y( B# E, X  P给定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
+ _9 }' v8 H- n) t. ^+ P: t/ s; GS(n,2) = 2n − 1 − 1

5 H; ?6 _3 ?+ @0 @4 ]+ @换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
+ O" R! _$ w5 n& m: z  {' Z3 e, U2 R
; N/ ]) l7 ^6 ]0 E6 m: q# f- K& ?{A,B},{C,D}
: g* t5 d3 V/ _* v{A,C},{B,D}
9 c- i8 ]. T" J( u{A,D},{B,C}
{A},{B,C,D}
* C; C% L& W" t- F: ]{B},{A,C,D}
{C},{A,B,D}
{D},{A,B,C}
2 K/ r! q& N0 `0 {, R4 x因此S(4,2) = 7。

lilianjie1

# M) t$ B( W- r; L) [2 {n:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
4 u: J6 p8 n% ^BernoulliPolynomial(n) ;伯努利多项式
0 D9 M5 \1 c# c% H5 h
26
8 Z* V" x+ t- ^  Z$ c9 M137/60
0
8 B& Z! Q% O: x$ o7 M0 B0.000000000000000000000000000000
- ]& N) i- Q, `, j, H$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

( {4 ]7 X3 g# D( I
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
5 v/ L7 n. j% m9 z& a- H& B
伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

/ N5 r, h& ~) u2 Q' n9 D( |
拆分 。。。。强！
; d( ?+ L6 a/ W: [* O
* E7 W" Q0 C( z' n; V  ~! ]NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;
: t1 k/ A, j/ V) S& b! D
0 H& q/ m. d, O% |, {' a- T" i7
- ~: r  E; G7 m$ t, S190569292
9 V% c0 r* F& Y* @[
4 @, Y: Q" \/ Z; |$ J2 b  l    [ 10 ],
" j( f& E0 a3 ]3 U8 C; n5 ?4 L2 w    [ 9, 1 ],
) |& p: ~+ K& S/ g" T4 r% y/ v% Y    [ 8, 2 ],
1 m$ H: Q; \3 l& i2 G- e3 R    [ 8, 1, 1 ],
    [ 7, 3 ],
    [ 7, 2, 1 ],
' p+ V! M8 P9 c) v( B! l    [ 7, 1, 1, 1 ],
    [ 6, 4 ],
9 w- [$ r) ]; N1 a/ g. i' D    [ 6, 3, 1 ],
    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
/ A6 t+ P! ?4 ^1 h7 ^/ P# c    [ 5, 5 ],
    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
. P: }8 Q6 `5 U" V& M7 v8 M9 O" z    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
$ g: a6 d- ?, ~: Y    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
    [ 4, 3, 3 ],
8 Y' U( s+ V  a% C* Q) h    [ 4, 3, 2, 1 ],
: M8 d% ~0 u5 {# ?1 x    [ 4, 3, 1, 1, 1 ],
8 f3 q; }% }& B% Y+ d* o0 g    [ 4, 2, 2, 2 ],
    [ 4, 2, 2, 1, 1 ],
' S0 ^3 L3 M" Q4 _; s& q' c    [ 4, 2, 1, 1, 1, 1 ],
; C' ]6 v1 {  A    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
3 u$ C1 Q; a4 v) ]: d    [ 3, 2, 2, 2, 1 ],
+ u, {4 g" o. G7 F& ~: S9 O    [ 3, 2, 2, 1, 1, 1 ],
    [ 3, 2, 1, 1, 1, 1, 1 ],
! L* z4 H, H) y1 M    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
: {; X* O+ O8 _( p    [ 2, 2, 2, 2, 2 ],
3 m0 F# l7 ^8 p9 I3 X/ K; x    [ 2, 2, 2, 2, 1, 1 ],
3 w( \. ~$ @; F' t    [ 2, 2, 2, 1, 1, 1, 1 ],
! D! J2 M9 @# E8 z+ ]    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
0 {! _1 u6 w' a# x+ a- j    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
]

xxgzftj