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

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

2、w，y分別代表紅球，白球，黃球。4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例由此可見，除一個球也不取的情況外，有： （a）取一個球的組合數(shù)為三，即分別取紅，白，黃，三種。 （b）取兩個球的組合數(shù)為四，即兩個紅的，一紅一黃，一紅一白，一白一黃。 （c）取三個球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白。 （d）取四個球的組合數(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個完全一樣的球放到m個有標志的盒子中，不允許有空盒，問共有多少種不同的方案？其中 由于不允許有空盒，令n

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

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

5、 。它的根是解方程4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例6：平面上有一點P，它是n個域的共同交界點，見圖 現(xiàn)取k種顏色對這n個域進行著色，要求相鄰兩個域著的顏色不同。試求著色的方案數(shù)。令 表示這n個域的著色方案數(shù)。無非有兩種情況： 圖 4.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（1） 和 有相同的顏色；（2） 和 所著顏色不同。第一種情形， 域有 種顏色可用，即 域所用顏色除外；而且從 到 的著色方案，和 個域的著色方案一一對應(yīng)。后一種 域有 種顏色可供使用；而且從 到 的每一個著色方案和 個域的著色方案一一對應(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進制最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。對于n位2進制數(shù) 從左而右進行掃描，一當出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃描，例如對11位2進制數(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)系，需對滿足條件的數(shù)的結(jié)構(gòu)進行分析。由于n位中除了最后三位是010已確定，其余 位可取0或1：4.8

7、 母函數(shù)和遞推關(guān)系應(yīng)用舉例故最后3位是010的n位2進制數(shù)的個數(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進制數(shù)中最后三位才第一次出現(xiàn)010圖象的數(shù)的個數(shù)。 即求對n位2進制數(shù) 從左而右掃描，第一次在最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。自然，最后三位除外任取連續(xù)三個都不會是010的。 設(shè) 表滿足條件的n位數(shù)個數(shù)，和前例類似，最后三位是010

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

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