一些组合函数

lilianjie1

9 ?; H) X6 k( W, c. \
7 q- k! s/ F8 ]n:=12;n;
6 F' h5 R6 N" h! u% YFactorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
8 F! ^7 W* H0 E- KNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
NumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
Binomial(n, 9) ;
Binomial(n, 10) ;
  |4 ?- G/ \- P- M& f7 \2 `0 F5 fBinomial(n, 11) ;
  ^4 O2 g; `* x2 p6 k* d! [2 |7 {Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600
, b9 \! B( T  B" b2 S9 d
Fibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
8 e% K) M) f' g* J* J7 z; d6 u) DGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
* U4 J: h) e! j) S0 }GeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
' x, H, Q. @1 X- _; Tk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
Catalan(3);Catalan(4);
5 P, X  h: Q  ~4 q( e+ w  J$ V1 n4 VCatalan(12);

Lucas(n);卢卡斯数
3 z* F, P1 w, F  a5 J( U' u12
479001600
( M/ K* l( n  S/ ~* z% @831600
12
0 P* j; X/ x# K' j7 M132
11880
479001600
12
+ ^, g/ a8 t- y8 n, C% Q66
/ _" s* T8 t2 ]% R220
* h0 j6 G- M, \7 b% h+ m4 i220
! }5 {* D1 \8 L/ u4 c0 W66
. w  ^7 M- U& ~" ?( Q' G/ p2 v" S12
5 w  X3 N5 i; R: ^0 @/ V1 K831600
; v) T6 I$ n+ E- o/ l144
89
3 w" l: L3 Y) G4 B! e233
# ?( y0 h3 h3 e+ R; r233
610
( m4 [" v# K3 v/ X144
208012
208012
1
0 {3 l" c7 N( u# w. g9 l2 L0 Q$ U2
5
% F; Q, o7 E6 U# V9 D3 y/ N* j* w$ D14
208012
322
! F8 J7 m) ^1 a( L2 Z  M

0 r( Q6 i4 U; n9 Q" B卡特兰数=(2n)!/((n)!*(n+1)!))
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
' h7 B5 K  ^/ c& ^2 S**YYY XYXXYY XYXYXY XXYYXY XXYXYY
: n9 k0 _$ y/ P8 N; t将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
# W9 C, }% T- k5 v! k- `Cn表示有n+1个叶子的二叉树的个数。
& |; N# j5 [4 f$ t* h
  S% C" q3 p6 k% P- jCn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

- U8 E* r/ _) s8 c6 N+ X) sCn表示对{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.
6 l0 t' g$ l( [9 OCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

7 B' F, }! S8 N/ n+ i* J
( D2 ?* {2 f1 ]
; P0 V5 x( P* L卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。
& L9 @8 g+ q4 L7 \) [' b( t
但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
* f7 W3 b0 p: U% ?1 Q3 g


n:=100;n;
a:=Lucas(n);a;
8 Y$ a9 {$ {; U3 y* mb:=Fibonacci(n+1)+Fibonacci(n-1);b;
2 J8 R9 [: {# _. L2 J3 ZLucas(n+1)+Lucas(n-1);5*Fibonacci(n);

6 W: f( t& J4 @% @- _100
792070839848372253127
792070839848372253127
1771124240896309575375
1 P/ `3 U6 b0 J) }1771124240896309575375

孤寂冷逍遥

lilianjie

- Z/ o' O7 p8 F/ t+ b: l
反费波那西数列反费波那西数列的递归公式如下：

! Z  K) N1 X& \3 O2 PGn + 2 = Gn − Gn + 1
3 [0 |+ P6 @3 U$ o3 `% p( w  D) z; [如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

1 @- |- m" I- Y/ ?) ?7 ~即是F2n + 1 = G2n + 1,F2n = − G2n。
# G+ H' b# L& h- Y$ q3 d, P7 V
3 S5 ^2 o5 c3 sBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
2 f5 e2 O" \, ?StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
: Y- r6 ?- Y3 U! {3 ~+ fStirlingSecond(4, 3);
2
52
5
15
2 i+ H: N( p5 K( T-6
11
-6
, m2 j# i2 }/ x3 x1
3 l3 `: q/ h' s+ Q' O* H, m7
: R: V8 ?, K  p% y& p5 o, D; }1 P6
' D' g. O3 U# @+ }" P. T# u
* u# m2 j4 o, G" m  W  |5 f/ o& BBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
5 M+ }% l! M' E( g
% F2 _' ^& x3 d# ~1 {$ I* S{{a}, {b}, {c}}
6 d' p8 v3 E/ J' N{{a}, {b, c}}
9 ~2 P; @  T+ k, l* E& o: V; Z9 Z( j{{b}, {a, c}}
{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
/ b; k6 R, v5 as(n,k)是递降阶乘多项式的系数
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

  S; [* Z, M) n换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
9 P+ f: C8 P  F
! M# Z+ b/ i6 X{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
1 h. t+ l: ^: \5 T# s- T0 l5 p5 Z2 u{A},{B,D,C}
3 c+ T2 L: B: {, [! C% n7 ~3 F{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
{C},{A,D,B}
{D},{A,B,C}
3 m, ?& O; ?# ?' J4 `{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)
3 ]& X& H2 p; `6 o+ sS(n,n − 1) = C(n,2) = n(n − 1) / 2
  k! k9 F1 W+ g7 n# G6 ~8 Z% LS(n,2) = 2n − 1 − 1
6 M3 O( V$ U+ N! l) A+ Q+ H5 s
' e6 m* f1 Q( T* W换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：
( x; s  f& s  G+ s$ T% ]# n
{A,B},{C,D}
2 B5 h; H8 d# U( B) K: r8 g{A,C},{B,D}
! g( w2 K& k0 K: @+ Z/ a{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
* x& }5 M0 d5 Q( I  t/ J# u8 l7 I{C},{A,B,D}
{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

n:=5;r:=3;
* t8 G# i! \, q3 ~! T3 `3 ^EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
BernoulliPolynomial(n) ;伯努利多项式
, i# w8 U! w- w4 W1 K5 [) ?( H
7 v% i5 Y- Q1 Y# R9 Y- B26
137/60
0
) O9 N. P. K. O# S( o1 ~# N0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

3 ?! W# H) O0 v9 I! N1 g1 a
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
1 a/ d, A4 Q5 [7 \; s. }! X
伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关

lilianjie

) b+ ~  E# L0 D- n4 X拆分 。。。。强！

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

7
190569292
$ E) `7 Q; u" l! s[
    [ 10 ],
) h% K# z, ~4 F5 w. P$ I    [ 9, 1 ],
    [ 8, 2 ],
3 m- e0 h" C. `+ W    [ 8, 1, 1 ],
- U7 L# N1 S) T/ g1 E; c    [ 7, 3 ],
    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
6 x8 K$ g9 v/ L' x# u    [ 6, 4 ],
+ s1 [2 ]  V6 q! G    [ 6, 3, 1 ],
& L- n1 S& q5 s    [ 6, 2, 2 ],
    [ 6, 2, 1, 1 ],
    [ 6, 1, 1, 1, 1 ],
9 H+ w1 ~# k, G    [ 5, 5 ],
    [ 5, 4, 1 ],
    [ 5, 3, 2 ],
3 `1 b; ~: F: Y0 g& C    [ 5, 3, 1, 1 ],
, C# S% \9 |& H    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
, v2 p) q7 M& x    [ 4, 4, 2 ],
( R4 y" ^$ Z# t3 E$ Q    [ 4, 4, 1, 1 ],
) \# X3 i3 \9 X5 N' a7 |    [ 4, 3, 3 ],
  j5 B. m* F! B2 _2 L! Q. r& c. w) q% S9 ]    [ 4, 3, 2, 1 ],
8 Q# f1 W! l  @" U+ d& m    [ 4, 3, 1, 1, 1 ],
    [ 4, 2, 2, 2 ],
    [ 4, 2, 2, 1, 1 ],
    [ 4, 2, 1, 1, 1, 1 ],
8 Z1 I5 M8 i# M# x9 Y' i  y    [ 4, 1, 1, 1, 1, 1, 1 ],
2 V, j+ H- M) ~3 U4 W    [ 3, 3, 3, 1 ],
    [ 3, 3, 2, 2 ],
5 H, K3 M/ P& }9 R. y: u    [ 3, 3, 2, 1, 1 ],
( z- }1 Q0 |7 F  p3 {% P5 l    [ 3, 3, 1, 1, 1, 1 ],
    [ 3, 2, 2, 2, 1 ],
, Q) I0 L8 @* c0 I    [ 3, 2, 2, 1, 1, 1 ],
    [ 3, 2, 1, 1, 1, 1, 1 ],
# |  `) ~# A, a2 g2 V, t    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
. |/ }+ M& Z1 M. _3 _9 T1 d& R    [ 2, 2, 2, 2, 2 ],
& x& L5 `+ H( |7 ~8 B( t3 C" k# Y( d+ ~    [ 2, 2, 2, 2, 1, 1 ],
, e0 p# z6 G3 I3 H+ J0 B6 }* p; k    [ 2, 2, 2, 1, 1, 1, 1 ],
% V6 ^" d/ k3 B+ \    [ 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 ]
; F' U6 f' ?& C: c]

xxgzftj