数学建模社区-数学中国

标题: 一些组合函数 [打印本页]
作者: lilianjie1    时间: 2012-1-12 15:56
标题: 一些组合函数
本帖最后由 lilianjie1 于 2012-1-12 18:09 编辑
5 Q9 T3 f1 {1 d0 R, r# y
6 t9 Q9 {4 K5 t% L! {n:=12;n;
4 ]+ n, |1 X, k; i$ Z. MFactorial(n);求阶乘  @; H1 c$ B  k- V0 n! f! b1 e8 P5 F
Factorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));
  ~/ G3 P9 {' V: g! }NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);1 A* ~  L* R+ o( a/ e
NumberOfPermutations(n, 4);. J, ?" ]" v# n! U0 x& M( \5 r. x$ N
NumberOfPermutations(n, 11);
- t1 R% v7 M/ \. j3 ]" WBinomial(n, 1) ;二项式系数Binomial(n, 2) ;0 j7 c5 x$ a9 \8 T
Binomial(n, 3) ;
, w8 D7 V  }% f9 |Binomial(n, 9) ;. Z; X: i' d+ X$ o
Binomial(n, 10) ;
. k8 V! z  _( y7 \Binomial(n, 11) ;* U( i& \2 J2 P7 N  p; C0 l4 y1 n  p4 \% y
Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12！/1！*2！*2！*3！*4！=831600! Y0 }1 v% x9 j' ~& o0 f$ h. n* S

! U4 J0 F+ h; }9 g& X4 ]Fibonacci(n);斐波数Fibonacci(n-1);
; }0 S8 N' P% N! RFibonacci(n+1);- L8 K5 O- }% V+ Z0 N) w
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;
  P- m. x. G. J9 yGeneralizedFibonacciNumber(0, 1, n) ;  v8 m8 P- b/ [
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
) m2 }/ m+ P, \4 l8 ?2 i- Ik:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
  q: M) x% k* e+ H" R' bCatalan(1);
6 ?- O  J! n/ j, wCatalan(2);
7 G& Z" p' A( ]. }" pCatalan(3);Catalan(4);
# F( X/ x+ C4 K; O% U; }6 E" dCatalan(12);
( @: Q' ~, i, }7 z) O' N2 L7 w: L1 d, A7 w# w
Lucas(n);卢卡斯数
, D% f6 ]. `2 z' E12& @9 R6 Z1 U. f5 O
479001600' r. u7 x4 s' [2 H- H+ r/ c
831600! n# B  N- o8 |- B1 `  W
12
) \3 g0 \0 F: {' r1322 ^' s; J2 u; V5 q
11880
' t0 Z, k- C- n. t% K479001600# I! H' N4 n. G3 K$ Q5 [$ o3 P2 x. \
12
/ ~4 U# k# v! \4 Q7 @5 `7 h( e66
" n: d" T+ h, E  ^7 h220
- h; Y" p& ^" Q# b8 R220
3 u1 h3 L* Z! n* R661 U) ^. f5 Z' n
123 C! u. h# }1 {' w0 w4 Z
8316000 a- w; Y' b! W% V6 N" f
1448 H! R2 T( u  B0 U- I/ P; r
89
: E& _/ f1 E6 y- M! \; q& H* d2331 B, V! k3 `1 [+ n! N
233
! T0 p# C: C' y' Q. p610
* E' @$ A$ c* G. o& }* C" C144
8 U2 O6 q( [* K: J6 ]) {* G2080121 z$ H# e+ V  y% j  x; G
2080120 s9 L. P3 T  t- C
1( |/ H; Z" N: u# m) m0 \
2
& h  S3 s) T+ E4 c, }' u5
) ~+ d6 P; ]5 L; ]4 r14
2 m# {  n6 u3 X( Z- e208012; K2 @7 R( T* V/ E. ]  H% ^
3225 i# y3 i' H4 Y1 t. E1 K- w$ p: H2 a
/ n$ u3 i/ Y9 {3 W% }+ Y

, e+ q1 _$ t. \9 @5 ^2 v9 T卡特兰数=(2n)!/((n)!*(n+1)!))7 j  M/ s* D6 X; L  C
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
: b: A2 g1 r4 J4 F/ z4 e**YYY XYXXYY XYXYXY XXYYXY XXYXYY
. V! @/ `, V5 j# q" j$ k2 c1 E" o% i将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数: , \, ^+ l$ s0 o/ J. }' L- o: F, u- }
((())) ()(()) ()()() (())() (()())
6 b0 ?3 [$ t6 K7 l1 lCn表示有n+1个叶子的二叉树的个数。
& Y0 d6 z- F& t% I  @( D) t0 M" I
( J. `# ]! ~# x% T' nCn表示所有不同构的含n个分枝结点的满二叉树的个数。（一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。） ( x3 m/ i9 i* Z6 k7 b6 V# ~
Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况： 8 p! K4 U0 e! Z+ C" b& K. r
8 m$ f$ _8 _7 [% J& l
Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
: P/ C' l9 A& {. yCn表示集合{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. " t- o- Y$ a  B% v; @4 m
Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况: - ^. h2 g2 M- S! ]' c4 n
' c, a# E0 t& R( }8 e  w

9 E; T( d$ z6 x& J3 H
  o5 K# {1 x) f) T# e# z/ t卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）。与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。! N/ D+ Y/ u2 v

! v" \, {/ j* Z' j+ j, a但是，最初两个卢卡斯数是L0 = 2和L1 = 1，而不是0和1。所以，卢卡斯数的性质与斐波那契数的性质有些不同
& S* `1 A0 Y9 ]9 g& P+ w+ U# M
" S: H) k  ^# l. n8 Y2 l" {
. r3 k( g& ]7 P# }8 Y' [8 S1 R
$ z5 f5 ^, K0 [# Bn:=100;n;! `8 A8 W# T* P, U; A% F/ V
a:=Lucas(n);a;' U) G1 L! e8 C! }( {) O3 h9 ]
b:=Fibonacci(n+1)+Fibonacci(n-1);b;$ h- t6 c: c( d) P, M
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);
9 i; P  L) ~2 }/ r9 U  [. V" Q+ o
2 F* l( l$ H; b9 a100
' }  n4 f$ ]3 t  T" L! F/ K792070839848372253127
' B9 _' g$ k' Q792070839848372253127, o9 u' P' @6 w  ~4 p
1771124240896309575375' [# F# [) A6 r7 Y, X
1771124240896309575375

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

12.JPG

作者: 孤寂冷逍遥    时间: 2012-1-12 17:02
作者: lilianjie    时间: 2012-1-12 18:44
本帖最后由 lilianjie 于 2012-1-12 18:44 编辑
) y- ?/ G/ b2 w; z4 T
" T9 k" v  b/ A( M7 s/ M反费波那西数列反费波那西数列的递归公式如下：) w& @& D6 [5 A2 D  U: D1 j
" G! M0 L+ v! M6 X7 D7 ?3 x
Gn + 2 = Gn − Gn + 1
! r* K1 Q1 X# d3 A+ K$ j% {如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ..., F, Z: u( C' G' M; m2 L) ]
1 e% q2 ^& |7 E) |9 i3 D
即是F2n + 1 = G2n + 1,F2n = − G2n。( f; F0 n6 a) [" e  O

  r6 |6 `0 f+ PBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);7 e1 B% Q+ P9 m
StirlingFirst(4,3);6 X6 Y( |5 c( g/ }9 A
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);
4 O7 d  l2 u7 |( hStirlingSecond(4, 3);$ O; q3 Y& a! A, |" p
24 D9 U4 F' x* a
52; n1 x4 `" |$ Z) ?) z+ w
5
# ]3 _* [7 q! X+ l15
& Y5 E- c6 }# ^% i, r) e3 L2 Y-6
9 F' ~% p# o) R; y% R11
( Q9 b( s8 q- X* |: @-62 H5 D1 Y% h; w$ D" I
1
4 `0 T% u: X# F4 t3 O1 ^5 P) T* e! P: ?78 E, O  `* ^3 a4 _
6- h8 t0 d% o, B' V3 z

" ?; k- p/ j4 wBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法：
: S$ z, V3 s3 ]8 K0 X+ q% o9 `! q2 G+ K9 v+ |
{{a}, {b}, {c}} ) ^0 v- T: a$ D: T0 {9 E' b6 M/ n; Z
{{a}, {b, c}} % _4 Z, m5 N" a# F0 a
{{b}, {a, c}}
4 A4 ~. Z* J# E3 }) L{{c}, {a, b}} ; a, q; g5 B" v$ M' Q
{{''a'', ''b'', ''c''}}; 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目用小写s7 B* Y* T3 H) n# u4 ]* [
s(n,k)是递降阶乘多项式的系数
& K! y. l  r9 ^8 K: o  ]有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k)! q" \: ^* G' `& N" F( Q- }

" N3 ~. H4 A. G7 f" t% D3 P换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。例如s(4,2)：
* v% t( ?- R, B! U2 z! K& n3 F
' o; @3 `$ a0 }{A,B},{C,D} 1 t4 `* R$ I8 R+ E; ?
{A,C},{B,D} 2 ?! J; R0 B- I: ^# ]7 N) U
{A,D},{B,C} 4 K2 s/ H; o# ^5 L8 F7 `$ ]
{A},{B,C,D}
: E/ [9 E% X2 m  V* r# X{A},{B,D,C}
; Q" v8 X- i4 k3 V- t0 g& D{B},{A,C,D}
/ P* J5 P$ e$ ~* \5 v{B},{A,D,C} 3 B0 r4 N# [' A
{C},{A,B,D} + P; @  M3 O5 ?5 |! ~8 S
{C},{A,D,B}
& O5 x5 ]! t! J# n( [{D},{A,B,C}
; c9 b2 N" H6 X% Y. H) H! }+ M$ X{D},{A,C,B} ( F  U6 f5 x+ ~+ o
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S+ H2 J0 _5 ?& a
给定S(n,n) = S(n,1) = 1，有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k) ; Y  V! Q0 C4 i7 C
S(n,n − 1) = C(n,2) = n(n − 1) / 2 . j1 P: b8 K# p
S(n,2) = 2n − 1 − 1
0 a! v3 |% C* i
8 t* H" O( t% p1 b" O0 `换个较生活化的说法，就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成4组，只可以人人独立一组，因此S(4,4) = 1；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：5 M* B% v# P9 Q" R7 D

% {& f  e9 H& ?: V6 M5 X{A,B},{C,D}
& s9 A: N! l1 K6 g# p2 c{A,C},{B,D}
3 `5 O8 m# b9 T- L{A,D},{B,C} 9 W3 k4 \$ y" F* ~/ a4 J
{A},{B,C,D} ) o2 Q' a; H7 L; _, Z: z
{B},{A,C,D}
) z  ]9 {2 d/ i{C},{A,B,D} ) S* ]' @- M6 t
{D},{A,B,C}
, H- S2 l- n- V2 ^: u7 K9 ~- X因此S(4,2) = 7。
作者: lilianjie1    时间: 2012-1-12 19:50
本帖最后由 lilianjie1 于 2012-1-12 20:06 编辑 ) a$ {' ~  g( _6 }. X3 p: Y6 _6 a

# h& M( ^1 T, A5 t1 g! wn:=5;r:=3;
& h9 b' v. m5 i) G! D0 dEulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn，以便与贝尔数分别开。BernoulliApproximation(n) ;
' I/ O5 `" M1 @6 JBernoulliPolynomial(n) ;伯努利多项式
7 Y4 _) v; ~: G! G
$ T) [  k4 x- b+ g26
6 G( {$ F; X& T4 }137/60) v, q) s2 j$ f- @
0
# v8 {7 f& O6 T- _0 S  [0.000000000000000000000000000000
# k* s6 A& Y% a7 ~$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

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

22.JPG

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

33.JPG

作者: lilianjie    时间: 2012-1-12 19:55
本帖最后由 lilianjie 于 2012-1-12 19:56 编辑
& C7 Q8 g( ]. Y. ]0 P# ~& V# m8 o- Q0 C- S" s
8 M% v; ?9 N5 ~1 w- y( K
* s" _$ p! r3 c& }; g) R
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n)，也就说明它们本质上是这函数在负整数的值。因此，可推测它们有深刻的算术性质，事实也的确如此，这是库默尔(Kummer)研究费马最后定理时发现的。
* h' M/ r7 M5 p7 o1 I& |$ l
2 L! W: {0 P& z1 U5 `4 C3 o' h伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关
& A* Z3 o( d6 }/ _% x
作者: lilianjie    时间: 2012-1-12 20:38
本帖最后由 lilianjie 于 2012-1-12 20:38 编辑
& o- I- [3 L8 C( `$ ?' ]$ x# {& F$ h! J+ U9 k  O
拆分 。。。。强！
$ a5 [! i" ~4 W! M$ h- h! Y) A* o; @! I. A5 Q* |" c0 @+ N* J
NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;
9 J$ k2 ~/ W1 v7 q& I: \! Z  S3 Q, U
9 ?- X/ Y  t9 l7. ?4 K% Z1 k" B' F1 H
190569292' f9 y$ ?, o3 c2 {; m/ [% B
[
$ F0 N2 r* O2 R0 M) G    [ 10 ],
% J5 ?* J" X' Z# @5 W/ `+ N    [ 9, 1 ],
" h( s5 M' x) U3 z+ m    [ 8, 2 ],
; i& D: b0 n* E9 s/ Y- _# b1 q4 C    [ 8, 1, 1 ],
# W7 ^2 T9 J' r& t- t, `( _7 i8 T    [ 7, 3 ],
: C; |1 v$ J: `4 I0 z* j: d- C    [ 7, 2, 1 ],( I* y: U" ], e/ r% I; Q- G. R
    [ 7, 1, 1, 1 ],
/ c/ M1 Y6 r0 f2 ~9 A5 [    [ 6, 4 ],2 p4 _- P! w, @$ g8 h6 ]! k
    [ 6, 3, 1 ],
3 t2 Z3 U* }! n; S' f7 u    [ 6, 2, 2 ],* a, t& |3 d& l- c8 U. i* _
    [ 6, 2, 1, 1 ],
6 N2 l. }% M, W8 J; U; s9 p    [ 6, 1, 1, 1, 1 ]," ?; ]4 y  r0 [5 X# ]* t
    [ 5, 5 ]," C8 u5 ~9 ^$ x: B& z
    [ 5, 4, 1 ],9 v' S. {- E. x  Y0 V' G
    [ 5, 3, 2 ],' k: k2 K" i2 f& M
    [ 5, 3, 1, 1 ],& t" Q: t9 X& i( S
    [ 5, 2, 2, 1 ],  L7 ^) V/ Y1 D$ O
    [ 5, 2, 1, 1, 1 ],
: |7 r; O/ w1 m    [ 5, 1, 1, 1, 1, 1 ],
+ m  _/ \6 q$ w7 R' C. G6 ]    [ 4, 4, 2 ],8 N! G+ A/ [0 H' R# v
    [ 4, 4, 1, 1 ],
7 C/ e3 S: h# k    [ 4, 3, 3 ],
( C3 K1 k) d4 c: X1 L0 K    [ 4, 3, 2, 1 ],
* M& C, z8 r& p( n' s' a1 N    [ 4, 3, 1, 1, 1 ],
8 R  h% a: |$ j" Z5 I4 N    [ 4, 2, 2, 2 ],
+ _, K  O7 ~( m0 S    [ 4, 2, 2, 1, 1 ],
4 |3 {" z% W! l    [ 4, 2, 1, 1, 1, 1 ],) R, C: o7 T: e. J8 S
    [ 4, 1, 1, 1, 1, 1, 1 ],7 p* r9 T7 Y; x
    [ 3, 3, 3, 1 ],4 {. x. q( H2 N- v( [4 P* s
    [ 3, 3, 2, 2 ],6 J' Y( V$ C( L4 J  L( R
    [ 3, 3, 2, 1, 1 ],* I, i3 i! N( B4 q$ ~- m
    [ 3, 3, 1, 1, 1, 1 ],
' w5 S" ]2 f& I) c    [ 3, 2, 2, 2, 1 ],+ y+ Z. B6 z8 C" L  r5 A
    [ 3, 2, 2, 1, 1, 1 ],
0 ?% ?0 w" U4 N/ R    [ 3, 2, 1, 1, 1, 1, 1 ],' j2 |( Q" c& z& E
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],
7 |* y. X9 Y+ {* M8 u$ ?3 R/ l    [ 2, 2, 2, 2, 2 ],8 O( `/ s" t% ^6 m
    [ 2, 2, 2, 2, 1, 1 ],; J( t7 _- Z- E
    [ 2, 2, 2, 1, 1, 1, 1 ],) z$ Q7 z' ?+ J# d
    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
$ |9 a$ d3 n) ^6 h    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],
$ N4 F0 }) ?, Q! n, A6 X! U    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
" J0 ]" `: C5 |; x" O]
作者: xxgzftj    时间: 2012-1-16 17:07




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