高級(jí)計(jì)數(shù)Catalan

數(shù)第一類Stirling

數(shù)第二類Stirling

數(shù)討論要點(diǎn)定義遞推方程恒等式對(duì)應(yīng)的組合問題生成函數(shù)第六節(jié)高級(jí)計(jì)數(shù)定義：一個(gè)凸n+1

邊形，通過不相交于n

邊形內(nèi)部的對(duì)角線把n邊形拆分成的三角形個(gè)數(shù)，記作hn，稱為Catalan數(shù).遞推方程考慮n+1

條邊的多邊形，端點(diǎn)A1,An+1

的邊記為a,以Ak+1（k=1,2,…,n-1）A1

為邊，An+1Ak+1

為另一邊，構(gòu)成三角形T,T

將多邊形劃分成R1

和R2

兩個(gè)部分，分別為k+1

邊形和n-k+1

邊形.n-1hn

=

hk

hn-k

,

n

?

2k

=1h1

=

11

2n

-

2n n

-

1h

=nCatalan數(shù)生成函數(shù)H

(

x)

=

1

-

1

-

4x2對(duì)應(yīng)的組合問題（1）從(0,0)到(n,n)的除了端點(diǎn)以外不接觸對(duì)角線的非降路徑數(shù)n

-

12

2n

-

2na1·a2·…·an,

不改變因子順序，加括號(hào)的方法數(shù)hnn

片樹葉的有序三度根樹個(gè)數(shù)2n個(gè)點(diǎn)均勻分布在圓周上，用n條不相交的弦配對(duì)的 方法數(shù)Catalan數(shù)（續(xù)）1,2,…,n

放入堆棧后的不同的輸出個(gè)數(shù)分析：1．1

進(jìn)棧；2．k

個(gè)數(shù)（2,…,k+1）任意進(jìn)棧并且出棧；3．1

出棧；4．處理k+2,…,n

的進(jìn)棧問題；步2：子問題規(guī)模k步4：子問題規(guī)模n-k-1T

(1)

=

1

T

(n)

=

T

(k

)T

(n

-

1

-

k

)n-1k

=0應(yīng)用（棧的輸出個(gè)數(shù)）￥￥￥

1n=0nn=1n-1n=0n-1k

=0x

2nn

+

1

nxG(

x)

=1-

4

x

,G(

x)

-

1=

T

(n)

x

=￥

￥

￥

n-1G2

(

X

)

=

(

T

(k

)

xk

)(T

(l

)

xl

)

=

xn-1(

T

(k

)T

(n

-

1-

k

))k

=0

l

=0

n=1

k

=0T

(n)

xn

,G(

x)

=T

(0)

=

1,

T

(1)

=

1T

(n)

=

T

(k

)T

(n

-

1-

k

)xG2

(

x)

-

G(

x)

+

1

=

0

2

xG(

x)

=

1–由于0G(0)

=

0,

2

xG(

x)

=

1-

1-

4

x棧的輸出個(gè)數(shù)（續(xù)）定義：多項(xiàng)式x(x-1)(x-2)…(x-n+1)的展開式為

Snxn-Sn-1xn-1+Sn-2xn-2-…+(-1)n-1S1xrr將

x

的系數(shù)的絕對(duì)值

S

記作

r

n,稱為第一類Stirling

數(shù)實(shí)例x(x-1)=x2-xx(x-1)(x-2)=x3-3x2+2x

3

3

0

=

0,

1

=

2,

2

=

3,

3

=

1

3

3

2

0

=

0,

1

=

1,

2

=

1

2

2第一類Stirlin數(shù)

0

=

0,

1

=

(n

-

1)!nnn

>

r

?

1

+

r

-

1rn

-

1

n

-

1

r

=

(n

-

1)n

=

+

...

(x

-

n

+

1)-

n

-

2

xxn

-

1

n

-

1

n

-

1x(

x

-

1)...(

x

-

n

+

2)(

x

-

n

+

1)n

-

1

n

-

2n-1

n-2x(

x

-

1)...(

x

-

n

+

2)

=

n

-

1

xn

-1

-

n

-

1

xn-2

+

...r其中x的系數(shù)

r

n=(n-1)+

n

-

1

n

-

1r

r

-

1.第一類Stirling數(shù)（遞推方程）第一類Stirling數(shù)（遞推三角形）恒等式

rn

n

nnnr

=1

=

n!(3)n(n

-

1)n

-

1

=

2

=

2

(2)n=

1,(1)證：x的n次方系數(shù)為1；x的n-1次方系數(shù)為1+2+…+n-1=n(n-1)/2(3)式的證明在后面.生成函數(shù)：x(x+1)(x+2)…(x+n-1)第一類Stirling數(shù)（恒等式生成函數(shù)）n

r

n

元對(duì)稱群S

，在表示式中具有r

個(gè)不交輪換的置換個(gè)數(shù)是n證明：設(shè)這樣的置換為nr個(gè)，得到這種置換的方法有兩種：從Sn-1

的含r-1

個(gè)輪換的置換中加入(n)，方法有n

-

1r

-

1種；從

Sn-1

的含有

r

個(gè)輪換的置換中加入

n,

加入的方法有

n-1

種，=

0,+=

(n

-

1)!n1n

-

1

n

-

1r r

-

1=

(n

-

1)nrn0實(shí)例定義：n

個(gè)不同的球恰好放到r

個(gè)相同的盒子里的方法數(shù)

r

稱為第二類Stirling

數(shù)，記作nS(4,2)

=

7a,b,c

|

da,b,d

|

ca,b

|

c,da,c,d

|

bb,c,d

|

aa,c

|

b,da,d

|

b,c第二類Stirling數(shù)遞推方程0

=

0,

1

=

1

n

nrn

-

1

n

-

1

r

=

r

+

r

-

1n

證明：取球a1，1

r

-

1a

單獨(dú)放一個(gè)盒子，n

-11

ra

不單獨(dú)放一個(gè)盒子，r

n

-1先放n-1

個(gè)球到r

個(gè)盒子里，插入a1

有r

種方法第二類Stirling數(shù)（遞推方程）

=

=

nn

m

ii

n

rkkm

m

n

n

nn

n

nni

=0

k

=11

2r

-

1n

+

1n=

1

2

-

12(6)

k!=

m(5)

=

m!m

,n

n

...n(4)(3)(2)(1)

n

=

2n-1

-

1對(duì)滿足n1

+n2

+...+nm

=n

的正整數(shù)解求和第二類Stirling數(shù)（恒等式）證明：

2（1）

n

=

2n-1

-

1a1

先放在一個(gè)盒子里，剩下的n-1

個(gè)球每個(gè)有2

種選擇，但是全落入a1

的盒子的方法不符合要求，減去.

2

1

n（2）

n

-

=

nn個(gè)球放到n-1個(gè)盒子，必有一個(gè)盒子含2個(gè)球，其余每個(gè)盒子1

個(gè)球.選擇兩個(gè)球有C(n,2)種方法.恒等式證明n

n

m

=

m!m,（4）

n

n

...n1

2對(duì)滿足n1

+n2

+...+nm

=n

的正整數(shù)解求和對(duì)應(yīng)n

個(gè)不同的球恰好放到m

個(gè)不同盒子的方法數(shù)（無空盒）（5）

nk

km

m

nk

=1

k!=

m按照含球的盒子數(shù)分類，對(duì)應(yīng)了允許存在空盒的方法

=

（6）

n

n

k

=0

r

k r

-

1n

+

1

k至多n個(gè)不同的球放到r-1個(gè)相同的盒子不存在空盒的方法按照球數(shù)分類恒等式證明（續(xù)）近似指數(shù)生成函數(shù)nnxnm

n

m

a

=

￥

=

m!m,=

n

n

...nn!(e

x

-

1)m其中求和是對(duì)一切滿足方程n1

+n2

+...+nm

=n

的正整數(shù)解求和1

2n1!n2!

...nm

!=

(

x

+

+

...)

=

an2!

n=0n!x

2生成函數(shù)n個(gè)球放到m

個(gè)盒子里的方法數(shù).球標(biāo)號(hào)盒子標(biāo)號(hào)允許空盒放球方法數(shù)對(duì)應(yīng)的組合問題否否否Pm(n)-Pm-1(n)將n

恰好無序拆分成m

部分否否是Pm(n)將n

無序拆分成t

個(gè)部分(t￡m)否是否C(n-1,m-1)x1+x2+…+xm=n

的正整數(shù)解否是是C(n+m-1,n)x1+x2+…+xm=n

的非負(fù)整數(shù)解是否否

n

m

第二類Stirling

數(shù)是否是m