組合數(shù)學(xué)-第四章8母函數(shù)和遞推關(guān)系應(yīng)用舉例

1、4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例1：下圖是一邏輯回路，符號(hào)D是一延遲裝置，即在時(shí)間t輸入一個(gè)信號(hào)給延遲裝置D，在t+1時(shí)刻D將輸出同樣的信號(hào)，符號(hào) 表示加法裝置DDD輸入u輸出v圖4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 若在 時(shí)刻，輸入信號(hào) 求相同時(shí)刻的輸出信號(hào) 。顯然，一般的有DDD輸入u輸出v圖4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 若信號(hào)輸入的序列 的母函數(shù)為 ，輸出的信號(hào)序列 的母函數(shù)為 ，則其中被裝置的特性所確定，可以看作是該裝置的傳遞函數(shù)，如圖4-8-14.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例2：由紅球兩個(gè)，白球、黃球各一個(gè)，試求有多少種不同的組合方案。設(shè)r，

2、w，y分別代表紅球，白球，黃球。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例由此可見，除一個(gè)球也不取的情況外，有： （a）取一個(gè)球的組合數(shù)為三，即分別取紅，白，黃，三種。 （b）取兩個(gè)球的組合數(shù)為四，即兩個(gè)紅的，一紅一黃，一紅一白，一白一黃。 （c）取三個(gè)球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白。 （d）取四個(gè)球的組合數(shù)為一，即兩紅一黃一白。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 令取r的組合數(shù)為 ，則序列 的母函數(shù)為共有1+3+4+3+1=12種組合方式。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例3：n個(gè)完全一樣的球放到m個(gè)有標(biāo)志的盒子中，不允許有空盒，問共有多少種不同的方案？其中 由于不允許有空盒，令n

3、個(gè)球放到m個(gè)有標(biāo)志的盒子的方案數(shù)為 ，序列 對(duì)應(yīng)的母函數(shù)為 。則4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例因故二項(xiàng)式 中 項(xiàng)系數(shù)為4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例即4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例4：某單位有8個(gè)男同志，5個(gè)女同志，現(xiàn)要組織一個(gè)有數(shù)目為偶數(shù)的男同志和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式。 令 為從8位男同志中抽取出n個(gè)的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故 。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故數(shù)列 對(duì)應(yīng)一母函數(shù)類似的方法可得女同志的允許組合數(shù)對(duì)應(yīng)的母函數(shù)位4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 中 項(xiàng)的系數(shù) 為符合要求的 個(gè)人組成的小

4、組的數(shù)目，總的組成方式數(shù)目為4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例5：10個(gè)數(shù)字（0到9）和4個(gè)四則運(yùn)算符 組成的14個(gè)元素。求由其中的n個(gè)元素的排列構(gòu)成一算術(shù)表達(dá)式的個(gè)數(shù)。 因所求的n個(gè)元素的排列是算術(shù)表達(dá)式，故從左向右的最后一個(gè)符號(hào)必然是數(shù)字。而第n-1位有兩種可能，一是數(shù)字，一是運(yùn)算符。如若第n-1位是十個(gè)數(shù)字之一，則前n-1位必然構(gòu)成一算術(shù)表達(dá)式。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例如若不然，即第 位是4個(gè)運(yùn)算符之一，則前 位必然是算術(shù)表達(dá)式。根據(jù)以上分析，令 表 個(gè)元素排列成算術(shù)表達(dá)式的個(gè)數(shù)。則指的是從0到99的100個(gè)數(shù)，以及4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例利用遞推關(guān)系 ，得 特征多項(xiàng)式

5、 。它的根是解方程4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例6：平面上有一點(diǎn)P，它是n個(gè)域的共同交界點(diǎn)，見圖 現(xiàn)取k種顏色對(duì)這n個(gè)域進(jìn)行著色，要求相鄰兩個(gè)域著的顏色不同。試求著色的方案數(shù)。令 表示這n個(gè)域的著色方案數(shù)。無(wú)非有兩種情況： 圖 4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（1） 和 有相同的顏色；（2） 和 所著顏色不同。第一種情形， 域有 種顏色可用，即 域所用顏色除外；而且從 到 的著色方案，和 個(gè)域的著色方案一一對(duì)應(yīng)。后一種 域有 種顏色可供使用；而且從 到 的每一個(gè)著色方案和 個(gè)域的著色方案一一對(duì)應(yīng)。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例則 的特征方程為4.8 母函

6、數(shù)和遞推關(guān)系應(yīng)用舉例解方程得4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例7：求n位2進(jìn)制最后三位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)。對(duì)于n位2進(jìn)制數(shù) 從左而右進(jìn)行掃描，一當(dāng)出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃描，例如對(duì)11位2進(jìn)制數(shù)00101001010從左而右的掃描結(jié)果應(yīng)該是2-4，7-9位出現(xiàn)010圖象，即4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例而不是4-6，7-9位出現(xiàn)的010圖象，即不是 為了區(qū)別于前者起見，我們說4-6，9-11位是010，但不是“出現(xiàn)010圖象”，這作為約定。 為了找出關(guān)于數(shù)列 的第推關(guān)系，需對(duì)滿足條件的數(shù)的結(jié)構(gòu)進(jìn)行分析。由于n位中除了最后三位是010已確定，其余 位可取0或1：4.8

7、 母函數(shù)和遞推關(guān)系應(yīng)用舉例故最后3位是010的n位2進(jìn)制數(shù)的個(gè)數(shù)是 。其中包含最后3位出現(xiàn)010圖象的以及在 位到第 位出現(xiàn)010圖象，而在最后3位并不出現(xiàn)010圖象的兩類數(shù)，后一種數(shù)為4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故有利用 推得特征方程為4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)解方程組4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例8：求n位的2進(jìn)制數(shù)中最后三位才第一次出現(xiàn)010圖象的數(shù)的個(gè)數(shù)。 即求對(duì)n位2進(jìn)制數(shù) 從左而右掃描，第一次在最后三位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)。自然，最后三位除外任取連續(xù)三個(gè)都不會(huì)是010的。 設(shè) 表滿足條件的n位數(shù)個(gè)數(shù)，和前例類似，最后三位是010

8、的n位2進(jìn)制數(shù)共 個(gè)，4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例對(duì)這 個(gè)數(shù)分析如下。（a）包含了在最后三位第1次出現(xiàn)010圖象的個(gè)數(shù)，其個(gè)數(shù)為 ，排除了在第 到第位第1次出現(xiàn)010圖象的可能。（b）包含了在第 到第 位第1次出現(xiàn)010圖象的數(shù)，其個(gè)數(shù)為 4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（c）包含了在第 位到第 位第1次出現(xiàn)010圖象的數(shù)，其個(gè)數(shù)是4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（d）包含了在第 位到第 位第1次出現(xiàn)010圖象的數(shù)，其個(gè)數(shù)是 ，因在第 位（打*號(hào)的格）可以取0或1兩種狀態(tài)。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例一般可以歸納為對(duì) ，從第 位到第 位第一次出現(xiàn)010圖象的數(shù)，其數(shù)目為 。從第 位到第

9、 位中間的 位可以取0，1兩種值，故有 種狀態(tài)。 4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故得遞推關(guān)系如下： 時(shí)有下面幾種狀態(tài)：排除了01010，因從左而右掃描時(shí)01010屬于前三位出現(xiàn)010圖象的。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例請(qǐng)注意，遞推關(guān)不是常系數(shù)遞推關(guān)系。故 時(shí)有 時(shí)有其它依此類推。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例令4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例整理得4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例9：設(shè)有地址從1到n的單元，用以紀(jì)錄一組信息。這個(gè)信息的每個(gè)元素都占用兩個(gè)單元，而且存放的地址是完全隨機(jī)的，因而可能出現(xiàn)兩個(gè)存放信息單元之間留下 一個(gè)空單元無(wú)法存放其他信息，求這n各單元留下空單元的平均數(shù)。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)這個(gè)平均數(shù)為 。 1 2 i+1 i+2 n-1 n存儲(chǔ)單元如上圖，設(shè)某一信息占用了第i+1，i+2兩個(gè)單元，把這組單元分割成兩個(gè)部分，一是從1到i，另一從i+3到n。由于用相鄰兩個(gè)單元的幾率相等，4.8 母函數(shù)和遞