1、4.9 非線性遞推關(guān)系 4.9 Stirling數(shù) n個(gè)球放到m個(gè)盒子里，依球和盒子是否有區(qū)別？是否允許空盒？共有 多少 種狀態(tài)。其方案計(jì)數(shù)分別列于下表。 n個(gè)球有區(qū)別，m個(gè)盒子有區(qū)別，有空盒時(shí)方案計(jì)數(shù)為多少個(gè) n個(gè)球無(wú)區(qū)別，m個(gè)盒子有區(qū)別，有空盒時(shí)方案計(jì)數(shù)為多少個(gè)4.9 Stirling數(shù) n個(gè)球無(wú)區(qū)別，m個(gè)盒子有區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為多少個(gè) n個(gè)球無(wú)區(qū)別，m個(gè)盒子無(wú)區(qū)別，有空盒時(shí)方案計(jì)數(shù)為多少個(gè) n個(gè)球無(wú)區(qū)別，m個(gè)盒子無(wú)區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為多少個(gè)4.9 Stirling數(shù) n個(gè)球有區(qū)別，m個(gè)盒子無(wú)區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為多少個(gè) n個(gè)球有區(qū)別，m個(gè)盒子無(wú)區(qū)別，有空盒時(shí)方案計(jì)數(shù)為多少個(gè)

2、n個(gè)球有區(qū)別，m個(gè)盒子有區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為多少個(gè)4.9 Stirling數(shù) 定義: n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中,要求無(wú)一空盒,其不同的方案數(shù)用 表示,稱為Stirling數(shù). 例如紅,黃,藍(lán),白四種顏色的球,放到兩個(gè)無(wú)區(qū)別的盒子里,不允許有空盒,其方案有如下七種:4.9 Stirling數(shù) 其中r表紅球,y表黃球,b表藍(lán)球,w表白球,4.9 Stirling數(shù) 定理: 第二類Stirling數(shù) 有下列性質(zhì):證明:公式(a),(b),(e)是顯然的,只證(c),(d).4.9 Stirling數(shù)(c)設(shè)有n個(gè)不相同的球 從中取出球 ,其余的 個(gè)球,每個(gè)都有與 同盒,或不與 同盒兩種

3、選擇.但必須排除一種情況,即全體與 同盒,因這時(shí)另一盒將是空盒.故實(shí)際上只有 種方案, 即4.9 Stirling數(shù) (d)n個(gè)球放到 個(gè)盒子里,不允許有一空盒,故必有一盒有兩個(gè)球,從n個(gè)有區(qū)別的球中取2個(gè)共有 種組合方案. 定理: 第二類Stirling數(shù)滿足下面的遞推關(guān)系,4.9 Stirling數(shù) 證明: 設(shè)有n個(gè)有區(qū)別的球 從中取一個(gè)球設(shè)為 .把n個(gè)球放到m個(gè)盒子無(wú)一空盒的方案的全體可分為兩類。 （a） 獨(dú)占一盒，其方案數(shù)顯然為 （b） 不獨(dú)占一盒，這相當(dāng)于先將剩下的 個(gè)球放到m個(gè)盒子，不允許空盒，共 4.9 Stirling數(shù)共有 種不同方案，然后將 球放進(jìn)其中一盒，從乘法法則得 不

4、獨(dú)占一盒的方案數(shù)應(yīng)為 根據(jù)加法法則有 上面證明遞推公式 的過程，也就是給出構(gòu)造所有方案的辦法。例如今將4.9 Stirling數(shù)紅、黃、藍(lán)、白、綠五個(gè)球放到無(wú)區(qū)別的兩個(gè)盒子里。故共有15種不同的方案。 先把綠球取走，余下的四個(gè)球放到兩個(gè)盒子的方案已見前面的例子。和前面一樣用r，y，b，w分別表示紅，黃，藍(lán)，白球，綠球用g表示，故得表 4.9 Stirling數(shù)表 4-9-1證明： S (n,m)表示把n個(gè)不同的球放入 m個(gè)相同的盒子，而且無(wú)一盒為空的方式數(shù)。如果考慮盒子是編號(hào)的。因?yàn)閙個(gè)盒子共有m!種編號(hào)方式，于是由乘法法則知共有m!S (n,m) 種方式把n個(gè)不同的球放入m個(gè)不同編號(hào)的盒子中

5、去，而且沒有一個(gè)空盒。設(shè)S表示n個(gè)不同的球任意放入m個(gè)有編號(hào)的盒子里的所有方法的集合，顯然|S|=mn 。令pi(i=1,2,m)表示盒子i為空這一性質(zhì)，Ai(i=1,2,m)表示S中具有性質(zhì)pi的元素組成的集合。則 表示沒有一個(gè)箱子為空的元素集合。由容斥原理即可得因此可得4.9 Stirling數(shù) n個(gè)球有區(qū)別，m個(gè)盒子無(wú)區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為 n個(gè)球有區(qū)別，m個(gè)盒子有區(qū)別，無(wú)空盒時(shí)方案計(jì)數(shù)為4.9 Stirling數(shù) n個(gè)球有區(qū)別，m個(gè)盒子無(wú)區(qū)別，有空盒時(shí)方案計(jì)數(shù)為4.10 Catalan 數(shù) 4.10 Catalan 數(shù) 這一節(jié)討論Catalan數(shù),其遞推關(guān)系是非線性的,許多有意義的計(jì)

6、數(shù)問題都導(dǎo)致這樣的遞推關(guān)系. 一個(gè)凸n邊形,通過不相交于n邊形的對(duì)角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用 表之. 4.10 Catalan 數(shù)例如五邊形有如下五種拆分方案，故圖 4-10-14.10 Catalan 數(shù)1.遞推關(guān)系定理：2.11 Catalan 數(shù)1.遞推關(guān)系定理：2.11 Catalan 數(shù)證明： 的證明：如圖 所示，以 作為一個(gè)邊的三角形 ，將凸 邊形分割成兩部分，一部分是 邊形，圖 2-11-22.11 Catalan 數(shù)另一部分是 邊形， 即點(diǎn)可以是 點(diǎn)中任意一點(diǎn)。依據(jù)加法法則有2.11 Catalan 數(shù) 的證明：如圖 所示，從 點(diǎn)向其它 個(gè)頂點(diǎn)可引出 條對(duì)

7、角線。對(duì)角線 把 邊形分割成兩個(gè)部分，因此圖 2-11-32.11 Catalan 數(shù)以 對(duì)角線作為拆分線的方案數(shù)為 可以是 中任一點(diǎn)，對(duì)所有這些點(diǎn)求和得以 取代 點(diǎn)也有類似的結(jié)果。但考慮到對(duì)角線有兩個(gè)頂點(diǎn)，同一對(duì)角線在兩個(gè)頂點(diǎn)分別計(jì)算了一次，2.11 Catalan 數(shù)作 式并不就給出剖分?jǐn)?shù)，無(wú)疑其中是有重復(fù)的。其重復(fù)度是由于一個(gè)凸 邊形的剖分有 條對(duì)角線，而對(duì)其每一條邊計(jì)數(shù)時(shí)該剖分都計(jì)數(shù)了一次，故重復(fù)了次即 式給出的結(jié)果是 的 倍。2.11 Catalan 數(shù) 式和 式都是非線性的遞推關(guān)系。2.11 Catalan 數(shù)2.Catalan 數(shù)計(jì)算公式由 式及 ,故得2.11 Catalan 數(shù)由整理得令2.11 Catalan 數(shù)即2.11 Catalan 數(shù)2.11 Catalan 數(shù)3.母函數(shù)方法設(shè)2.11 Catalan 數(shù)即2.11 Catalan 數(shù)后面將看到只能