数学建模社区-数学中国

标题: 一些组合函数 [打印本页]

作者: lilianjie1    时间: 2012-1-12 15:56
标题: 一些组合函数
本帖最后由 lilianjie1 于 2012-1-12 18:09 编辑
" U7 [% r. U/ C
) Z$ L3 y  m( C! Sn:=12;n;
8 ]+ V/ O$ Q( r, h; oFactorial(n);求阶乘
0 h( }! t2 ]2 J) @/ |- rFactorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
3 ?1 H- D* h  ]( b  }; `" v1 tNumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);+ O. B; O% ]  i1 Q
NumberOfPermutations(n, 4);  v' P9 _6 z8 m$ t( v
NumberOfPermutations(n, 11);/ o+ }& q4 o2 I+ ?+ e
Binomial(n, 1) ;二项式系数Binomial(n, 2) ;
. R9 @+ h; u. e; e" cBinomial(n, 3) ;
* A+ U) D& ?' L7 [  v1 F6 bBinomial(n, 9) ;! J2 |  ]3 k& C* t
Binomial(n, 10) ;
" L4 B/ s5 ^, lBinomial(n, 11) ;  H* n* H+ a( @4 C! t
Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12!/1!*2!*2!*3!*4!=8316000 i6 G- I/ q, R  _
& w4 p4 K* i/ X0 ^- S
Fibonacci(n);斐波数Fibonacci(n-1);
" A/ A, m: G) O2 a% ~Fibonacci(n+1);
9 d8 P' O6 ]4 x/ N- d; ]1 IGeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
, I# b+ n/ u; n& GGeneralizedFibonacciNumber(0, 1, n) ;* W( k( p" M( Z- O/ b- O& ~3 b
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
0 F- M, s4 I% [2 ~  y+ g- n4 lk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
! d( x7 y% Q: @  W1 [! PCatalan(1);
, |! G, j) {% T! w& S& UCatalan(2);2 ^9 P4 D$ \( Z1 p7 c
Catalan(3);Catalan(4);5 [; M8 q7 N% a: D
Catalan(12);
. o  {; I1 w9 u9 ?1 p7 c5 h
! T9 Y* F6 H( Y* g7 pLucas(n);卢卡斯数
5 j) K! Z+ H- J( U- h5 Q9 z* F/ X126 }/ k2 X- H" n: P8 s6 D6 e1 Y
479001600
& t3 e% ^3 S5 e7 M# h; I831600
1 f7 n* I2 k( i3 Y; K4 B0 [12
  C) i- A3 x  k  ?9 f1324 r$ M5 s9 q% ^. S
118804 A( P* S, U! \! B: \" }; a! u
4790016009 j3 ?9 V4 ~7 t! p; B% w  _
12
8 ]1 k" ?, Z! j7 ]* [66/ e7 r, ^- g& D
220
: b3 t/ S. F, c7 R. ~! b220
, p" o* @6 O7 {# t% X66% D. {7 d8 e$ z  z. t1 ~
12. A/ J# r& `2 K2 ~/ ^7 D. z
831600
8 o! m2 j$ H6 l# u6 B144  }2 W& p0 Z0 y/ j; T" m- Y
89  ^  s6 Q  p4 [/ p
233+ Y% n" o' e  u6 h1 Q* |2 ]
233
; `! D: e. X% M" p4 K2 D610- l$ j# H9 M# R8 I
144% K3 P& y* t7 G. w5 `4 g
208012
; f- c# p! q6 O  s208012
2 d  L) i0 r4 n! Q$ W1
' g3 p8 k- @) y- ?0 j2" Z9 I3 g, d( z2 u( c
5+ t: U  C4 j" z. y
14
; Z. p0 a# J) h7 S, u' Q208012$ n) ]7 L. o. ^' `" w) }
322
: F: [7 L9 a+ L$ _# m5 @7 N
8 X6 t8 C% p7 H. E  B
7 \* ~% P0 I0 k5 d1 j* Z. O卡特兰数=(2n)!/((n)!*(n+1)!))
" s- V+ ^8 |. tCn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
7 M) J8 o3 }8 R  X( l" E% c* {* _**YYY XYXXYY XYXYXY XXYYXY XXYXYY
; M! t8 w; f, B6 @将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数: 8 h6 K0 O: l$ [, ]: j! p
((())) ()(()) ()()() (())() (()())
( E' p  m; R6 m) F" fCn表示有n+1个叶子的二叉树的个数。 ) l4 r" Z9 ?( e$ P. x
& ]) ~' b: X/ N# ]& x) N
Cn表示所有不同构的含n个分枝结点的满二叉树的个数。(一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。) + b2 F4 \6 u8 K4 U: d/ n
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况: 5 K3 i: b" t, G; h5 N, T

# g$ w' O: r6 G4 x1 K% `- _Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下:令w = unv,其中n为w的最大元素,u和v为更短的数列;再令S(w) = S(u)S(v)n,其中S为所有含一个元素的数列的单位元。 1 F6 Y3 F& X+ c6 G) m2 l
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.
$ A7 }3 \) s4 I1 K7 D8 TCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

' m( e* I0 y0 g' B
& R, N$ [/ a7 Y, d5 B4 X1 p7 Q! A: g$ y0 B6 @. [2 ~
8 _% |4 b- g/ r
卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列,他既研究了这个数列,也研究了有密切关系的斐波那契数(两个数列都是卢卡斯数列)。与斐波那契数一样,每一个卢卡斯数都定义为前两项之和,也就是说,它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。) [; l3 j6 E$ A! q$ |4 X5 x" h! C" h

' q6 r. Z& v* D5 H3 ?但是,最初两个卢卡斯数是L0 = 2和L1 = 1,而不是0和1。所以,卢卡斯数的性质与斐波那契数的性质有些不同

* L( ]/ K* H2 t8 q3 q/ h) v% i7 @3 w) `/ f

. {) N7 @; b& V- P& v& ^' v. @" T7 n/ T( v; a4 j
n:=100;n;
' u  y4 Z3 U' H/ X+ ea:=Lucas(n);a;
* }+ P' `; y! e& Cb:=Fibonacci(n+1)+Fibonacci(n-1);b;
- Z% ~/ R: |6 Z' m+ E, B% ^Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
- r& k6 ^, Q2 f$ \- G$ T, ~8 O& [4 S" A9 m2 T( S
100
$ y8 j5 l: A6 t: _$ V  s9 `7920708398483722531275 D+ [' P; K7 f" Q4 k" D
792070839848372253127
! @, a5 T. G" c; Y3 i2 e1771124240896309575375# a- Z5 d- e% p& w
1771124240896309575375

12.JPG (43 KB, 下载次数: 383)

12.JPG


作者: 孤寂冷逍遥    时间: 2012-1-12 17:02

作者: lilianjie    时间: 2012-1-12 18:44
本帖最后由 lilianjie 于 2012-1-12 18:44 编辑
# [+ Q8 @4 e6 b, Y4 }7 L( _, o; D+ }6 @" v/ e) c! r
反费波那西数列反费波那西数列的递归公式如下:
! C4 |0 a" K8 K5 Q) ?
3 Y# s/ y% s5 E( v) l8 [' [) OGn + 2 = Gn − Gn + 1
0 u! m% {- y6 Z* I8 w如果它以1,-1,之后的数是:1,-1,2,-3,5,-8, ...
) E1 L4 V9 B' H2 B+ ?/ e
" o; b% m3 e$ ?' C+ i+ i即是F2n + 1 = G2n + 1,F2n = − G2n。* I8 x* ^; E' Q1 z
* l% ?1 {+ R& A$ \& c
Bell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);
9 ]; k- W4 B; w& w6 O. i# GStirlingFirst(4,3);
; C' y1 m$ I( ?, ^4 H/ S4 r7 C8 kStirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
2 V: I4 B/ l  s- m5 I( C9 r& ^5 r3 ZStirlingSecond(4, 3);' I2 c, E8 @4 B: \  A
2
2 m$ v8 Z/ v4 j4 u! q" p' w* z) X/ G528 _: \5 j, F: B- S' P
55 |6 D4 G, P" q% D6 ?4 j
15
: c) _  A; m  X/ v5 P-6
. o! A7 e% R4 x( {  A, \111 g4 P( [) d0 A# d1 a5 e3 M4 p
-64 z# `; _6 ?# r- m2 o/ _) i
1
3 n8 d6 C& A1 x5 y3 {73 i/ }3 [# R8 t
6$ e, m" T. w: @7 b& g
! W% Z- k, u3 g( o# D
Bn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法:' N# {: l" ]7 s) f, f

) Y' z, @% D  x! G{{a}, {b}, {c}}
$ T6 W6 O# [$ v9 J( R6 m/ q{{a}, {b, c}} - u$ x9 F. g8 d
{{b}, {a, c}} ' A4 O# e$ v/ Z; M1 C; \
{{c}, {a, b}}
2 f  M! @# b9 ~$ R  D& S/ `( s{{''a'', ''b'', ''c''}};
第一类Stirling数是有正负的,其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
) A3 _! q2 {+ f, ys(n,k)是递降阶乘多项式的系数
/ r) S/ i. g  ^$ }3 k% B( ^有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)% v: m6 T% K1 E) {8 w$ U1 L( d9 v$ g

/ b9 l0 K6 ^7 n: L$ f; u) ]/ v换个较生活化的说法,就是有n个人分成k组,每组内再按特定顺序围圈的分组方法的数目。例如s(4,2):0 R7 f6 |1 q' S0 L9 H( A! l" {7 g4 w, p
$ C' Z4 W% s0 s0 r% X! n; S4 c
{A,B},{C,D} % S6 S+ \, `; l- X" l
{A,C},{B,D} 5 w3 ]& Z. ~; ^
{A,D},{B,C}
5 c0 t8 J6 x# I, h* P6 H! o{A},{B,C,D}
6 |3 b5 I7 b: s  X+ M5 A% q8 u{A},{B,D,C} 4 ?& |2 T; S. q, N+ \! G+ K  ~& `
{B},{A,C,D} ' u7 [, Z" L1 f  N" ~) C5 b
{B},{A,D,C}
5 m; j0 \  ^( F0 S{C},{A,B,D}
  E9 Q$ b7 a( V8 ^& n# }{C},{A,D,B}
% W& c: n2 e' W2 o# P{D},{A,B,C}
9 l* b" n1 f- ?4 G( `, I{D},{A,C,B}
+ @1 N3 u* e8 l
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S' B$ H, N1 a' N/ ]
给定S(n,n) = S(n,1) = 1,有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k) $ V+ f0 R  N, A- P. ^1 n! F3 S% z
S(n,n − 1) = C(n,2) = n(n − 1) / 2
! b2 M* ^6 E/ R$ MS(n,2) = 2n − 1 − 1
3 K; z( H! h3 Y# w7 x! ], b9 l: i% g, s1 p* \
换个较生活化的说法,就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人,若所有人分成1组,只有所有人在同一组这个方法,因此S(4,1) = 1;若所有人分成4组,只可以人人独立一组,因此S(4,4) = 1;若分成2组,可以是甲乙一组、丙丁一组,或甲丙一组、乙丁一组,或甲丁一组、乙丙一组,或其中三人同一组另一人独立一组,即是:
8 Z+ K) @( p7 [+ `$ z! Y) r% t, \* c0 y
2 v& x* @* [6 J% @" M1 z7 B{A,B},{C,D}
( T8 R/ [7 U- h3 z' c/ i4 N. T{A,C},{B,D} 2 F) s& n" n* ^0 N5 {1 ^
{A,D},{B,C} 8 c" E+ K) h1 W$ ^
{A},{B,C,D} 5 T3 \# ?5 P  l5 X" ^* F# v8 A
{B},{A,C,D} ! Q3 j* E" M2 r8 i! q
{C},{A,B,D} ! r* y$ V5 g$ F
{D},{A,B,C} ; P! ^1 h$ D( j
因此S(4,2) = 7。

作者: lilianjie1    时间: 2012-1-12 19:50
本帖最后由 lilianjie1 于 2012-1-12 20:06 编辑
7 `6 i( Q9 i0 D( s$ D  c7 e- d" t" \! S! d" {% `; I2 v! Z
n:=5;r:=3;2 X* z! h1 m5 G6 Y- j3 H
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn,以便与贝尔数分别开。BernoulliApproximation(n) ;
+ j$ i+ {8 \* ^$ T. N3 G" |0 |BernoulliPolynomial(n) ;伯努利多项式8 w. r1 g' l6 w: E+ L/ L
! _; x+ C1 P9 O$ \
26
+ H. K- X) v. L+ [137/60# u  |2 ?3 K0 m! h) U
04 H  d0 J$ V* S0 s* y2 [7 m* Z
0.0000000000000000000000000000005 D) Y* c1 X. {4 _- l7 P
$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

22.JPG (56.17 KB, 下载次数: 341)

22.JPG

33.JPG (50.55 KB, 下载次数: 370)

33.JPG


作者: lilianjie    时间: 2012-1-12 19:55
本帖最后由 lilianjie 于 2012-1-12 19:56 编辑 1 c& m  Q1 g0 @& H" H6 d- Y0 ?( R& M
6 l! I8 p9 `' o. }

. c# n& ~8 O  j* N# b
6 n- M, a, @  S( e6 p伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n),也就说明它们本质上是这函数在负整数的值。因此,可推测它们有深刻的算术性质,事实也的确如此,这是库默尔(Kummer)研究费马最后定理时发现的。
/ b0 m. S2 m( X
; g, X& N- X. \伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关6 z3 f, p* W& }+ N" P% _

作者: lilianjie    时间: 2012-1-12 20:38
本帖最后由 lilianjie 于 2012-1-12 20:38 编辑
7 V/ t6 q& z. h+ ^6 X+ r2 d0 F6 G% e! ~8 _$ Z( |2 @. v
拆分 。。。。强!. g2 E4 A8 y) \# Z, j; T6 u2 L
' c5 I, M5 j5 w6 X
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;
1 I; ?1 L# a* K  p8 z" Q9 ~& x- u# K# Z. Z
7
8 u; l  ?! G# R4 e190569292
; H+ t6 B9 P  w& d) w[
# S, O. B- P# ^+ r/ @9 O$ L    [ 10 ],& P5 ]9 t* ^+ ]
    [ 9, 1 ],
8 E& n! \8 C0 e    [ 8, 2 ],
- ?( W5 L/ f9 J    [ 8, 1, 1 ]," p4 M0 {. @8 ~# ^" b% v
    [ 7, 3 ],
- A- c1 o5 l  P, y. d4 ~" l    [ 7, 2, 1 ],
% Z3 X" u* C  X; D4 z    [ 7, 1, 1, 1 ],6 s9 I, P6 `! j7 E* b
    [ 6, 4 ],
6 o2 t( r! r, R5 a! k! q    [ 6, 3, 1 ],+ b, z2 z: m! ]0 V
    [ 6, 2, 2 ],( s3 c# Q9 l  _2 s
    [ 6, 2, 1, 1 ],
) @  `. Z* k3 c    [ 6, 1, 1, 1, 1 ],
0 w& I4 W0 Q, I    [ 5, 5 ],3 c3 q9 P8 F- j- X
    [ 5, 4, 1 ],* D- [0 y0 Z8 k( T6 v! D/ z( D/ z" P
    [ 5, 3, 2 ],
8 b  J4 X) x& L. h0 ^+ D' v    [ 5, 3, 1, 1 ],; A9 t+ ?3 _$ t* r. U, N
    [ 5, 2, 2, 1 ],
- e" \& w, b- k    [ 5, 2, 1, 1, 1 ],
: {( p) N9 H9 \  t) w' U    [ 5, 1, 1, 1, 1, 1 ],
6 n2 Q! i+ W( Z9 l2 W    [ 4, 4, 2 ],' x4 H& Z( w. h& v' `0 b
    [ 4, 4, 1, 1 ],1 F0 K, O$ s3 a( X
    [ 4, 3, 3 ],( n3 C1 u3 G* }; X
    [ 4, 3, 2, 1 ],; {8 n6 W% n( V( w' g
    [ 4, 3, 1, 1, 1 ],) |" q- Y5 |8 K3 v6 @
    [ 4, 2, 2, 2 ],& T' ^9 _4 ]/ M: `7 E
    [ 4, 2, 2, 1, 1 ],
1 |) h& b6 M" ], l  e2 w& w    [ 4, 2, 1, 1, 1, 1 ],) `4 @7 q  w4 C
    [ 4, 1, 1, 1, 1, 1, 1 ],& ~0 b2 E6 ]3 x/ C
    [ 3, 3, 3, 1 ],
( X! L/ P+ B0 Z    [ 3, 3, 2, 2 ],: k1 D6 t) z2 ~: V7 ]
    [ 3, 3, 2, 1, 1 ],
- J5 [2 h) D5 g7 y! d; p7 I    [ 3, 3, 1, 1, 1, 1 ],& i: i9 z+ t6 T2 @" F
    [ 3, 2, 2, 2, 1 ],
9 h7 `- J7 r' H' H2 _    [ 3, 2, 2, 1, 1, 1 ],
' V" |) `9 u" `/ L+ m: U( U% |% p    [ 3, 2, 1, 1, 1, 1, 1 ],
& |0 R' i* Z' q% {: X3 |$ X    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
3 ~7 S/ b' A: x$ p& {4 h) V0 E5 y    [ 2, 2, 2, 2, 2 ],
" K. J* f1 L3 h- ~  W. ?- P    [ 2, 2, 2, 2, 1, 1 ],3 J$ k& o3 I: w7 \# L  H
    [ 2, 2, 2, 1, 1, 1, 1 ],
, l" o6 G  L' V& m9 v    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
/ _" K" Y/ p* ^8 o- Q: d6 ?    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],+ @5 A; N. q; h1 _; |9 g2 F+ D
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
) o% C7 L8 f5 Y' X) u]
作者: xxgzftj    时间: 2012-1-16 17:07





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5