一些组合函数

lilianjie1

  d8 W) ?% a7 q
6 d% A5 h" I$ p% X, Bn:=12;n;
4 h! I# x' u2 k! P- T5 n: bFactorial(n);求阶乘
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
; `: D/ ?; E  h* ~( eNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
$ l8 p, b4 _' BNumberOfPermutations(n, 4);
NumberOfPermutations(n, 11);
* L9 |: W7 ?$ `: q% _Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
Binomial(n, 3) ;
) j; _+ m9 {; K- OBinomial(n, 9) ;
% n- Q- ~) M4 d/ C& p" Q- V' Z5 DBinomial(n, 10) ;
Binomial(n, 11) ;
4 _: `' K4 n  l, P. q6 {3 B) F3 HMultinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600
$ u) h. c: N7 B: P6 C6 a. ^
" |' W3 C( i) p% _4 o7 Q: a# n9 LFibonacci(n);斐波数Fibonacci(n-1);
Fibonacci(n+1);
3 \+ k6 W7 @0 H6 w; j9 y1 u: RGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
0 j: q. Z! W/ {GeneralizedFibonacciNumber(0, 1, n) ;
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
k:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
Catalan(1);
Catalan(2);
Catalan(3);Catalan(4);
# w5 c% a: {& `7 zCatalan(12);

, n6 P$ k% B3 M7 E+ ?* D/ g+ dLucas(n);卢卡斯数
12
479001600
831600
  U$ X  ?4 b& x+ M( C4 L12
. c* B. v4 z4 \3 J132
4 e- s/ z# {9 D# G( m* ?11880
479001600
12
66
  e2 {! {4 R! I8 C$ w! _! ~220
220
66
4 }+ W' ]0 c! x8 D# I12
7 a# ?6 D( t& V. C* e831600
144
3 s: P9 \+ y) z2 p) x89
233
233
610
144
208012
208012
1
2
5
$ a/ J1 C- q. b, D6 ?14
% C+ E% Z3 E( b208012
% X: O( {2 Q3 r* e# y. F322
; \5 p% h5 T1 {9 K: D! D

* i# H1 M+ @3 G, x/ b7 K5 [) V# w6 O7 d卡特兰数=(2n)!/((n)!*(n+1)!))
7 z7 H/ h# W2 j5 `. M/ h5 Z) E3 K- uCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
' P, H) `- B% T* u6 \' ~! Y**YYY XYXXYY XYXYXY XXYYXY XXYXYY
: E  e$ W1 s4 h% {0 f' U将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
2 Y& E+ ~9 ~* H((())) ()(()) ()()() (())() (()())
7 g+ C2 Q' J8 {( d3 b$ R" T+ vCn表示有n+1个叶子的二叉树的个数。
, p5 x5 r1 j. m+ P; g9 W7 h) I
Cn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。）
7 y% d7 C/ L: A0 \! HCn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

8 q; r4 M  G9 m$ D3 zCn表示对{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的情况:


* U' Q2 ?; {% {2 ~. X
# H9 D4 }) z0 G) \2 q) W% ]卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。

+ h1 c: z! R- a3 z2 N但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同

8 u" b7 ^/ W( P4 F' t6 ]6 U
. O* X2 C) r  g4 y) x" Y. j: A
n:=100;n;
" D$ r3 I6 {) @  p3 na:=Lucas(n);a;
0 K/ C8 z" R- p! J1 s: Jb:=Fibonacci(n+1)+Fibonacci(n-1);b;
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);

3 d9 v, [* P) c& z" ?# Z100
792070839848372253127
792070839848372253127
/ }' V- P; M4 W/ _$ r: w' d% Y1771124240896309575375
1771124240896309575375

孤寂冷逍遥

lilianjie

4 j' M& X! p- {. e3 `4 H
反费波那西数列反费波那西数列的递归公式如下：

5 K  q& f2 j* {0 d% T" TGn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
, e( }6 W% i$ [+ c( D2 J
即是F2n + 1 = G2n + 1,F2n = − G2n。

0 }: s! x+ z( y) h7 N: S/ J; Q! GBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
StirlingFirst(4,3);
! ?) P6 T4 D; K) r; d1 k* gStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
StirlingSecond(4, 3);
2 H  L- E7 c- c7 r2
% B. R% X$ E: x1 Y52
/ J  C& x$ p9 L9 X( b5
: ~  u9 w# w8 T6 w# K) X; ]15
/ c, b) M  N$ b3 Q$ o+ f-6
% y( Q; i5 F. h: b0 S( j11
-6
1
7
6

Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
7 X' s  k" I3 x
# K- Z5 [$ H( p  L4 O  q. t3 _; C{{a}, {b}, {c}}
# o, }- Z8 c$ L1 r{{a}, {b, c}}
) Q- n& n0 v: m{{b}, {a, c}}
7 D- e  e( O/ f- k$ B0 |{{c}, {a, b}}
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
s(n,k)是递降阶乘多项式的系数
5 j! Z# z- D8 R, t- w$ s有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)

换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
; t; t/ \; [) C8 y7 M
{A,B},{C,D}
{A,C},{B,D}
2 D$ D/ Z  m* c$ W0 P{A,D},{B,C}
' {: |7 M9 F, @3 @$ T+ Q& d{A},{B,C,D}
; r0 E" r9 I0 ?+ t% @' I{A},{B,D,C}
$ p# S8 M- Y& B{B},{A,C,D}
{B},{A,D,C}
/ o$ M% ]9 {, M2 m% S* z0 r4 B, u{C},{A,B,D}
{C},{A,D,B}
{D},{A,B,C}
{D},{A,C,B}
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
) e3 c+ s$ y1 }& g# W给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
7 Z7 G# A/ u* v. C7 Q! KS(n,n − 1) = C(n,2) = n(n − 1) / 2
( `5 C' O) s) XS(n,2) = 2n − 1 − 1

7 N9 N- {3 B! ?  M% q换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

{A,B},{C,D}
{A,C},{B,D}
1 y1 C8 l9 A* M4 ]{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
{C},{A,B,D}
( c- y( P7 {4 \{D},{A,B,C}
因此S(4,2) = 7。

lilianjie1

n:=5;r:=3;
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
; h) b) \6 Q! ?: y: m3 ^BernoulliPolynomial(n) ;伯努利多项式

8 S# @/ U/ V+ a) h26
137/60
0
0 _0 B7 M) W$ [2 f0 o7 q+ N0.000000000000000000000000000000
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

lilianjie

& C% M4 f0 \$ K
6 ], _! M* M4 [5 @+ y% o& \" m
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。

  F  L2 S. W* V% }6 \# s8 z伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
" `* \$ H$ w, \7 }0 s

lilianjie

4 ^, O$ b4 u$ P& {: l% l/ Q拆分 。。。。强！
! ^/ j# _  Q' T! e, N
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;

7
7 v+ B  i, I: W+ Y190569292
[
    [ 10 ],
/ F) n: j5 O( M" c    [ 9, 1 ],
6 U5 W& G& V9 t" w# Y+ c) }    [ 8, 2 ],
9 W0 g4 i) P4 Y+ O4 s) @8 L! j    [ 8, 1, 1 ],
3 X4 w4 G) ^* Y( y. c. b6 z  m    [ 7, 3 ],
    [ 7, 2, 1 ],
    [ 7, 1, 1, 1 ],
+ D3 j& K  {3 y' a    [ 6, 4 ],
5 H7 }& _) b+ |# A7 S$ B$ @    [ 6, 3, 1 ],
. x9 `& L4 S: u- O2 {    [ 6, 2, 2 ],
5 H3 r2 B! p, H' @2 ?    [ 6, 2, 1, 1 ],
0 N5 {5 o- W/ A$ k    [ 6, 1, 1, 1, 1 ],
    [ 5, 5 ],
    [ 5, 4, 1 ],
% U4 U. b4 O& e$ x    [ 5, 3, 2 ],
    [ 5, 3, 1, 1 ],
    [ 5, 2, 2, 1 ],
    [ 5, 2, 1, 1, 1 ],
    [ 5, 1, 1, 1, 1, 1 ],
" O7 d. Z. I; U5 T% f4 h    [ 4, 4, 2 ],
    [ 4, 4, 1, 1 ],
    [ 4, 3, 3 ],
    [ 4, 3, 2, 1 ],
+ Q; F% I# Z$ m7 y+ o    [ 4, 3, 1, 1, 1 ],
  h' ~3 [1 F! }    [ 4, 2, 2, 2 ],
    [ 4, 2, 2, 1, 1 ],
    [ 4, 2, 1, 1, 1, 1 ],
    [ 4, 1, 1, 1, 1, 1, 1 ],
    [ 3, 3, 3, 1 ],
6 f1 b" p% W) K( a    [ 3, 3, 2, 2 ],
    [ 3, 3, 2, 1, 1 ],
    [ 3, 3, 1, 1, 1, 1 ],
- ?9 h" I3 N- a$ B% i* i' K    [ 3, 2, 2, 2, 1 ],
# {* |# b# R. A& ]0 Y: X3 V    [ 3, 2, 2, 1, 1, 1 ],
5 e$ B+ e4 o6 D2 f' s0 d9 A% R, A    [ 3, 2, 1, 1, 1, 1, 1 ],
+ L  f( O5 Z2 Y7 q1 @" X    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
& {9 c, d$ R# O8 j3 t6 @  [3 O9 L    [ 2, 2, 2, 2, 2 ],
' {8 t' n4 z' l$ w3 x0 x/ j    [ 2, 2, 2, 2, 1, 1 ],
; |& h  E$ S% g, H2 [$ z    [ 2, 2, 2, 1, 1, 1, 1 ],
+ b% i, O6 g: K) }' {    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
" _3 j6 C8 i1 Y! R; P8 }6 [, V    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
+ N5 G1 ~1 P( V+ Y4 T# C( P2 ]]

xxgzftj