数学建模社区-数学中国

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

作者: lilianjie1    时间: 2012-1-12 15:56
标题: 一些组合函数
本帖最后由 lilianjie1 于 2012-1-12 18:09 编辑 $ J( S$ b2 y# @/ N5 M: r0 W
& F; q. n  N4 O% V3 V
n:=12;n;
# X  H3 j& D6 RFactorial(n);求阶乘
) r. S' J' g% ?5 o2 _" jFactorial(n)/(Factorial(2)*Factorial(2)*Factorial(3)*Factorial(4));: _7 z. G# W9 \8 M3 }
NumberOfPermutations(n, 1);组合数NumberOfPermutations(n, 2);
+ M$ N$ p2 W' d  cNumberOfPermutations(n, 4);
' e# l9 F4 [1 l* kNumberOfPermutations(n, 11);
( A9 x: S8 f1 @, c; k$ wBinomial(n, 1) ;二项式系数Binomial(n, 2) ;
5 l1 j# k2 Q: p: }5 JBinomial(n, 3) ;
  U! H4 L" E- t( DBinomial(n, 9) ;
1 Z4 I9 u, `- g( vBinomial(n, 10) ;- x8 B$ J; @$ D; |; w
Binomial(n, 11) ;3 D; T$ D0 U/ o! a; U
Multinomial(n, [1,2,2,3,4]) ;x*y^2*z^2*t^3*k^4系数=12!/1!*2!*2!*3!*4!=831600* C( f  j5 G8 p# e

$ j: u' t! Y- r6 ?Fibonacci(n);斐波数Fibonacci(n-1);
. C$ c8 g' b0 [) c7 W6 P+ |Fibonacci(n+1);9 u4 ^4 |, C; L: q2 q
GeneralizedFibonacciNumber(1, 1, n) ;斐波位数加数GeneralizedFibonacciNumber(2, 3, n) ;* c0 Z0 e; A& w1 z9 T
GeneralizedFibonacciNumber(0, 1, n) ;0 @  S3 u% P) [' r4 Q; K
Catalan(n);卡特兰数=(2n)!/((n)!*(n+1)!))
3 U- _4 Q" Q+ e( f3 i& m+ qk:=Factorial(24)/Factorial(12);k;m:=k/Factorial(13);m;
; t% H( Y$ {2 UCatalan(1);
: }$ X3 x/ Y& y; a* p" UCatalan(2);
) I7 E! f$ t9 Q$ fCatalan(3);Catalan(4);4 t4 R5 ?6 M8 ^+ }( b8 u8 }3 m
Catalan(12);
1 o8 }6 K; p: @# v! h" C( X, z  X. C, ]4 n6 H
Lucas(n);卢卡斯数# W2 J) B5 L1 u0 B
12
1 \2 E0 o  V& K4790016002 ]- r' H! @) ^+ u! I, b3 H
831600
5 A0 N! V' K2 S0 ~/ S12# u' F' }1 U" R: |( B$ }# j5 q
132. h& P* N1 {, E) D5 W
11880
6 ^$ s" ^* m0 J9 N$ f& K, f( V+ ?479001600
4 h- G7 z6 ~6 P" I: A3 B4 O12) U7 y& b+ ]! `; V5 r1 ?
66
4 K+ A( L% F% N# T- m2 a2206 x! p0 I: }6 C& H( [/ ~! G% N
220, @2 q( ?5 o( C. u
662 H+ ]; s' B  h1 Q+ ?! F7 k" K
12
, g6 V: J9 Q% y% }$ Y5 T" ]; V% V831600) @4 B! U4 U. C8 X0 u0 R+ m7 q& s
144
; g. Y5 r0 g* V  v% `# f& C& r  T" y89
, X: |7 b/ p1 Q# g5 U9 k( ], y7 Y233
- u; a6 V: N" _) E# K; V+ U0 P% v233
! m, j+ M, @5 j( i610
  F$ h! a6 B0 x: ~# |144
8 T( n: ?- B- G, {; A2080122 ^7 @/ g: f; J- o7 _$ K1 i
208012
; e! t, N) o) p1' g  _, ^1 ^" G" T" E2 [) d
2
, n' q. F9 k! S& C5
: q% ?) h# |' H* C; m4 b9 d14
; ]% t3 Q/ K5 G. O% p/ W) W% [208012
; ^" [- }* t0 [322$ v0 ?( T6 P  b

, _' \' |2 u) e7 w" F: `) E% w
% C5 Z. ?6 }9 i! F卡特兰数=(2n)!/((n)!*(n+1)!))/ W  ]; e2 L' D2 ]2 b$ r- R
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words: 2 D: g7 K$ T. W
**YYY XYXXYY XYXYXY XXYYXY XXYXYY
% I! O4 E3 T; [9 K9 A/ `0 q9 x将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数: / S. m3 [' `: s; B9 ^
((())) ()(()) ()()() (())() (()())
) @/ E+ r7 K$ S+ J: M. aCn表示有n+1个叶子的二叉树的个数。 % E+ ^" f- Q, a, Q+ [8 c: b- ?

7 C! R' e7 h( r4 v9 V) ZCn表示所有不同构的含n个分枝结点的满二叉树的个数。(一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树。)
" r7 O/ W9 X; W% @Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况: 8 R( p$ ^# \5 z. V& c7 \9 K! _* v

9 Z2 G% t3 q% ]6 }' b) u  FCn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下:令w = unv,其中n为w的最大元素,u和v为更短的数列;再令S(w) = S(u)S(v)n,其中S为所有含一个元素的数列的单位元。 7 d2 L9 Q, b" Y! }$ z8 V4 ]! y
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.
! N0 s$ L0 C" L' qCn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:
8 G  J2 U/ [6 a$ T; Z
7 S* X% s; d4 _

" l6 l( ]1 D, t. ]; ^9 y1 V) U" t8 z
. o. e3 e" b: v7 @9 o7 @卢卡斯数是一个以数学家爱德华·卢卡斯命名的整数序列,他既研究了这个数列,也研究了有密切关系的斐波那契数(两个数列都是卢卡斯数列)。与斐波那契数一样,每一个卢卡斯数都定义为前两项之和,也就是说,它是一个斐波那契整数序列。两个相邻的卢卡斯数之比收敛于黄金分割比。- W  w" B/ A# w

" _7 r2 t3 \- h8 v2 ]6 g6 U: L6 C6 t  s但是,最初两个卢卡斯数是L0 = 2和L1 = 1,而不是0和1。所以,卢卡斯数的性质与斐波那契数的性质有些不同

8 Y+ H( G. @7 O
0 i6 O9 H( C* M3 [0 ~4 p3 u2 V2 {/ u( D4 r% h
+ i4 B# v8 }  P. e" B
n:=100;n;
/ A( ^/ \/ H# r* xa:=Lucas(n);a;
: C; h" N  i" l. X* u# w7 nb:=Fibonacci(n+1)+Fibonacci(n-1);b;8 F" i! J) B+ N5 e- l! P
Lucas(n+1)+Lucas(n-1);5*Fibonacci(n);& l6 P* A3 y) u" e# q( W
- T4 X5 o7 k/ k" z/ U5 I3 {
100
) e) |+ T6 N6 v792070839848372253127
: _) k: o& g" _4 B/ u792070839848372253127: s0 a; s+ V5 W- m
17711242408963095753752 O5 a1 [9 h$ v
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 编辑   @+ N9 i' M1 Q; d) y. U9 r7 p
4 O* X* B5 Q* m( q' e, g  W1 e) j
反费波那西数列反费波那西数列的递归公式如下:" c  z% B6 K2 T8 I  Z" N  L

5 v8 F9 E2 B; D! kGn + 2 = Gn − Gn + 1
' g8 R7 T0 _& q6 E如果它以1,-1,之后的数是:1,-1,2,-3,5,-8, ...2 f/ k; [. e. R4 D6 p( V
2 Y2 k+ \/ D/ u1 o! x' o5 ?8 c
即是F2n + 1 = G2n + 1,F2n = − G2n。0 L' V1 G! d* l8 H

. C. j4 c1 [6 J$ f8 CBell(2);Bell(5);Bell(3);Bell(4);贝尔数StirlingFirst(4,1);第一Stirling数StirlingFirst(4,2);) Q! S2 z3 t2 w3 C3 F- M) t
StirlingFirst(4,3);0 x4 ^5 l+ ?0 r( |
StirlingSecond(4, 1);第二Stirling数StirlingSecond(4, 2);# |/ E$ Y" ?# X3 y5 [) A( L0 B
StirlingSecond(4, 3);- I2 A1 W7 y; e' q3 S# v$ N/ }" V% J
2
' w/ [' S$ l4 h3 {( x. G52
$ @( Z5 f+ j3 s9 l$ u52 C& G7 Z4 {, c5 j
15
# S% u$ C! [! k* y-6% p) J# j) G+ z& e
111 a; P# p3 }* d- h9 T( s
-6% g5 a3 F' q2 [6 f/ P0 j! T
1
% Y' h! b  N% p  D- Z7
0 h8 f' c' J6 ~6. \4 ~% Y; h4 m1 s( H) M8 g

2 k/ W: ?/ \% VBn是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S。例如B3 = 5因为3个元素的集合{a, b, c}有5种不同的划分方法:
" M) H- J! x6 _1 g$ Z2 p8 w! {+ w9 m
{{a}, {b}, {c}}
/ ?0 G. n9 e  E3 {' I{{a}, {b, c}} + y6 X- z/ N. n6 i: G+ R: \
{{b}, {a, c}} $ v. o* R' ]- L3 S
{{c}, {a, b}} 2 P1 Q- `( g  @. C( b
{{''a'', ''b'', ''c''}};
第一类Stirling数是有正负的,其绝对值是n个元素的项目分作k个环排列的方法数目用小写s
3 q0 L( ]/ G! R$ b6 @* U% ks(n,k)是递降阶乘多项式的系数$ h- w9 `; T1 R  W* k! C) y( h
有递归关系S(n,k) = S(n +1,k) + S(n ,k-1) -n*s(n.k); `/ \! r# ?% a$ J7 f% z

( k' r8 s; e* o# K* t8 t  i换个较生活化的说法,就是有n个人分成k组,每组内再按特定顺序围圈的分组方法的数目。例如s(4,2):4 l* f; s# E9 g) p* L9 e

+ u4 i" [, i9 o* V# `{A,B},{C,D}
6 a5 X0 G$ ^# Y' y7 a{A,C},{B,D} " p$ _2 z# A- f
{A,D},{B,C} 4 p4 h8 S& z4 t6 f* [
{A},{B,C,D} ; S6 O' @7 a0 |, w9 ]. x/ s; T& u' K) f
{A},{B,D,C}
' u' k3 `" H4 s! u# G! q: D{B},{A,C,D} , T8 V' m: g7 Y$ f2 {: L+ S
{B},{A,D,C}
- d* @, X: t) \4 i  W3 B/ Q! \{C},{A,B,D} 4 @6 B5 @/ x' L; S7 w$ k
{C},{A,D,B} % [2 A) r: S/ t5 ^% R- d" U$ E
{D},{A,B,C}
$ w, x* j6 ^& }: I8 f  m1 A{D},{A,C,B}
  Z- v3 v2 e6 T: v6 j" z  l4 `9 s3 o0 \
第二类Stirling数是n个元素的集定义k个等价类的方法数目。用大写S
. J- q2 m+ c2 I, I4 u! m  @* Y2 P& u给定S(n,n) = S(n,1) = 1,有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
: A: u$ R7 ~+ y% x8 D$ XS(n,n − 1) = C(n,2) = n(n − 1) / 2
1 ~7 M: C5 z; z9 r5 WS(n,2) = 2n − 1 − 1
8 J0 r7 F& f) A2 c$ y
; e, a6 o! H5 V/ Q3 S换个较生活化的说法,就是有n个人分成k组的分组方法的数目。例如有甲、乙、丙、丁四人,若所有人分成1组,只有所有人在同一组这个方法,因此S(4,1) = 1;若所有人分成4组,只可以人人独立一组,因此S(4,4) = 1;若分成2组,可以是甲乙一组、丙丁一组,或甲丙一组、乙丁一组,或甲丁一组、乙丙一组,或其中三人同一组另一人独立一组,即是:" d8 b& w! `* O
% p7 x, @8 Z1 p( e% F7 A
{A,B},{C,D}
7 ~  `/ e7 m/ {/ j5 Y* r5 D7 b. m  ^{A,C},{B,D} - z7 a. c1 v, e0 L2 w9 }9 A, F/ f% F" l
{A,D},{B,C} 2 Q7 I$ o1 D  I5 P  u6 N5 t
{A},{B,C,D}
- y# Z4 T" W0 N+ h* ~( b; m{B},{A,C,D} , p9 \8 [, N! t: k" h/ f' R
{C},{A,B,D} 7 n- u: [( Y4 g7 j% `/ g- d$ w* F
{D},{A,B,C}
$ Y  w9 c; x5 U! `6 {因此S(4,2) = 7。

作者: lilianjie1    时间: 2012-1-12 19:50
本帖最后由 lilianjie1 于 2012-1-12 20:06 编辑 & d: s9 e- R: s" d/ a; n
2 I2 E3 b( O$ `. v% H+ a! L
n:=5;r:=3;3 _. E. ]/ f/ p5 F! k
EulerianNumber(n, r) ;欧拉数HarmonicNumber(n) ;调和数列和BernoulliNumber(n) ;伯努利数有时会写成小写bn,以便与贝尔数分别开。BernoulliApproximation(n) ;
8 V- f5 B1 ?% k7 [BernoulliPolynomial(n) ;伯努利多项式* y8 }4 J2 O2 a& C* n2 S* E4 s
, D4 H. u  G/ U
26$ T: N& X5 F& l
137/60+ f( M1 R1 q1 X+ {4 g' [. h
04 G) d. E, [3 q/ Y" N! B$ u& @
0.000000000000000000000000000000
6 l! D6 `6 I0 X0 q! p$.1^5 - 5/2*$.1^4 + 5/3*$.1^3 - 1/6*$.1

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

22.JPG

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

33.JPG


作者: lilianjie    时间: 2012-1-12 19:55
本帖最后由 lilianjie 于 2012-1-12 19:56 编辑 , C* U/ E0 F& g+ A; A; i' m

. z# f; z. J$ q. J% u. a( R! Z
7 p7 P3 H1 C- l. i, p7 I; _, O% s: O" l
伯努利数可以用黎曼ζ函数表达为Bn = − nζ(1 − n),也就说明它们本质上是这函数在负整数的值。因此,可推测它们有深刻的算术性质,事实也的确如此,这是库默尔(Kummer)研究费马最后定理时发现的。
) Y: U& W" Y% F5 P( Z3 V, N: G" t( N
5 g* C5 O. \+ G( U) l9 E' S伯努利数的可整除性是与分圆域的理想类群有关。这关系由库默尔的一道定理和更强的埃尔贝朗-里贝定理(Herbrand-Ribet)描述。而这性质与实二次域的关系由安克尼-阿廷-乔拉猜想(Ankeny-Artin-Chowla)给出。伯努利数还和代数K理论有关% q5 O! u" L+ K) `! M

作者: lilianjie    时间: 2012-1-12 20:38
本帖最后由 lilianjie 于 2012-1-12 20:38 编辑
1 X" t4 d" s# v( N! V) n/ ]/ c' f6 [7 g$ n  i3 I  H0 L  A
拆分 。。。。强!! a" b+ Q3 y+ A% M7 ]2 v

( I" d# |: U1 {NumberOfPartitions(5);NumberOfPartitions(100)artitions(10) ;# t0 X  j. j0 c! I

# C5 A1 m! t* d5 _; o" q4 ^7# k/ ^* {4 k+ q: V
190569292
4 I9 j1 W- n$ w4 V. G9 Z8 e9 j  [[
& Z- `# S5 e( x2 R    [ 10 ],
' [  G# X) W0 z6 O    [ 9, 1 ],
$ b# V+ z8 A) }* \    [ 8, 2 ],
7 Z" T# K0 p3 j/ a- T  W4 k    [ 8, 1, 1 ],. f2 L6 m6 k. p8 m7 E$ ?
    [ 7, 3 ],0 \6 a1 ?% A: |. c) Z! _
    [ 7, 2, 1 ],
1 V" l+ `8 [) l9 ~    [ 7, 1, 1, 1 ],# t( V) N4 u; C5 ^. A
    [ 6, 4 ],
8 X/ N' I2 P5 a: H6 M    [ 6, 3, 1 ],
6 r- `0 w% s2 a/ C5 z7 E- }    [ 6, 2, 2 ],7 ^8 p- `' b1 ~. d
    [ 6, 2, 1, 1 ],
$ ^6 w3 W! c. i9 R% n. y    [ 6, 1, 1, 1, 1 ],
& R" h. R1 p+ n# N; ~3 z$ z: s# E    [ 5, 5 ],
' \  B6 w/ M# ~% R4 L' Z    [ 5, 4, 1 ],
8 {- ~6 ^; A, s  N) n8 U    [ 5, 3, 2 ],# A, R# F1 M. E0 }$ Y5 t
    [ 5, 3, 1, 1 ],9 P. m1 c! V9 _" M8 R( M
    [ 5, 2, 2, 1 ],
. T! {( H9 Q: }# m+ }6 f    [ 5, 2, 1, 1, 1 ],& `) t% W3 x) V9 Y6 p6 r
    [ 5, 1, 1, 1, 1, 1 ],2 [: a; T  X; Q9 c
    [ 4, 4, 2 ]," s* p& {% h8 _- ]
    [ 4, 4, 1, 1 ],7 g1 f. c( Z8 K
    [ 4, 3, 3 ],
2 A8 J  @1 d- E/ R    [ 4, 3, 2, 1 ],9 ]8 a5 W+ y) g& s4 `
    [ 4, 3, 1, 1, 1 ],
6 s$ Z" x2 a% Z( @2 B6 \' N    [ 4, 2, 2, 2 ],1 n/ E* n( A* E( h8 `5 W
    [ 4, 2, 2, 1, 1 ],* }8 y1 @+ b2 i$ A
    [ 4, 2, 1, 1, 1, 1 ],
- \  k1 ^" P5 G9 ~0 f6 M" I    [ 4, 1, 1, 1, 1, 1, 1 ],
& K1 T' l# I) _" H$ K. }    [ 3, 3, 3, 1 ],% y: c+ A9 h+ C
    [ 3, 3, 2, 2 ],$ U" k$ N/ o& V$ p) r# w
    [ 3, 3, 2, 1, 1 ],
9 i# ^) |. j' m    [ 3, 3, 1, 1, 1, 1 ],
  d, j* S( }: G  K    [ 3, 2, 2, 2, 1 ],8 s$ |1 `5 V; ]5 _
    [ 3, 2, 2, 1, 1, 1 ],/ e0 F) h% e% T
    [ 3, 2, 1, 1, 1, 1, 1 ],5 q, n+ \% ^3 `* {
    [ 3, 1, 1, 1, 1, 1, 1, 1 ],1 }1 C2 b7 L$ @, ~( {* w- m
    [ 2, 2, 2, 2, 2 ],8 P* G# U9 K# `8 {% K
    [ 2, 2, 2, 2, 1, 1 ],( ]+ p& M+ o2 G
    [ 2, 2, 2, 1, 1, 1, 1 ],
1 w! j/ {1 T' s3 E3 D/ L! C    [ 2, 2, 1, 1, 1, 1, 1, 1 ],
% x+ N/ B6 r/ ~, ~1 A    [ 2, 1, 1, 1, 1, 1, 1, 1, 1 ],% M% K6 R4 ]0 R: O
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]+ r* u* i7 Y8 P3 s( W
]
作者: xxgzftj    时间: 2012-1-16 17:07





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