組合數(shù)學(xué)2-5-應(yīng)用舉例

1、例1 9個(gè)數(shù)字(1到9)和4個(gè)四則運(yùn)算符(+,-,?,?)組成的13個(gè)元素，求由其中的n個(gè)元素的排列構(gòu)成一算術(shù)表達(dá)式的個(gè)數(shù)。,這里所說(shuō)的算術(shù)表達(dá)式指的是普通意義下的四則運(yùn)算表達(dá)式，不允許運(yùn)算符連續(xù)出現(xiàn)，最后一位必定是數(shù)字。,假設(shè)n個(gè)元素的算術(shù)表達(dá)式個(gè)數(shù)為an。由于最后一位必定是數(shù)字，接下來(lái)看第n-1位，即倒數(shù)第二位。,2.5 應(yīng)用舉例,若第n-1位是數(shù)字，則前n-1位構(gòu)成算術(shù)表達(dá)式，個(gè)數(shù)為an-1，加上最后一位有9種取法，因此這樣的

2、n位算術(shù)表達(dá)式個(gè)數(shù)為9an-1。,若第n-1位是運(yùn)算符，則第n-2位必定是數(shù)字(不允許兩個(gè)運(yùn)算符連續(xù)出現(xiàn))，即前n-2位構(gòu)成算術(shù)表達(dá)式，個(gè)數(shù)為an-2，加上最后一位有9種取法，倒數(shù)第二位有4種取法，這樣的n位算術(shù)表達(dá)式個(gè)數(shù)為36an-2。,因此可以得到遞推關(guān)系式：,初始條件為a1=9，a2=90。,這里a2=90指的是81個(gè)兩位數(shù)和-1到-9。,為了后面的計(jì)算方便，我們把a(bǔ)1，a2代入原遞推關(guān)系反解出a0=1/4。,從特征方程x2-9x

3、-36=0解出特征根為12，-3。,因此可以設(shè),代入初始條件有,因此有：,由此解出,例2 n條直線把平面分成多少個(gè)區(qū)域？假定直線兩兩相交且無(wú)三線共點(diǎn)。,設(shè)n條直線把平面分成Dn個(gè)區(qū)域。,這是一個(gè)非齊次遞推關(guān)系。由于1是1重特征根，因此特解應(yīng)設(shè)為2次多項(xiàng)式，加上齊次方程的通解為常數(shù)，因此可以設(shè),代入初始條件：D1=2，D2=4，D3=7，解得A=B=1/2,C=1。因此有,第n條直線被其它n-1條直線分成n段，這n段剛好對(duì)應(yīng)增加了n個(gè)新

4、的區(qū)域。因此有,例3 設(shè)有n條封閉的曲線，兩兩相交于兩點(diǎn)，任意三條封閉曲線不相交于一點(diǎn)。求這樣的 n條曲線把平面分割成幾個(gè)部分？,設(shè)n條曲線把平面分割成an個(gè)部分。,這2n-2個(gè)交點(diǎn)把第n條曲線分成2n-2段。,這是一個(gè)線性常系數(shù)非齊次遞推關(guān)系。,第n條曲線與其他n-1條曲線共有2(n-1)個(gè)交點(diǎn)。,這2n-2段剛好是增加的區(qū)域的邊界，即增加了2n-2個(gè)區(qū)域。因此有,右端項(xiàng)為一次多項(xiàng)式，但因?yàn)?是1重特征根，因此特解應(yīng)該設(shè)為二次多項(xiàng)式

5、。加上齊次遞推關(guān)系的通解為常數(shù)，因此有,對(duì)于初始條件，顯然有a1=2，a2=4。,在遞推關(guān)系an-an-1=2n-2中令n=1還可以得到a0=2。,把這三個(gè)初始條件代入有,因此有：,例4 空間有n個(gè)平面，任意三個(gè)平面交于一點(diǎn)，且無(wú)四平面共點(diǎn)。這樣的n個(gè)平面把空間分成多少個(gè)不重疊的區(qū)域？,設(shè)這樣的n個(gè)平面把空間分成an個(gè)區(qū)域。,因此關(guān)鍵在于第n個(gè)平面被其它n-1個(gè)平面分成多少個(gè)區(qū)域？,題目的條件保證了第n個(gè)平面與其它n-1個(gè)平面各有一條

6、交線，而且這些直線兩兩相交，且無(wú)三線共點(diǎn)。,第n個(gè)平面被其它n-1個(gè)平面分成一些區(qū)域，這些區(qū)域剛好對(duì)應(yīng)到新增加了的空間區(qū)域個(gè)數(shù)。,因此根據(jù)例2的結(jié)論，這n-1條直線把第n個(gè)平面分成的區(qū)域個(gè)數(shù)為：Dn-1=n(n-1)/2+1。,這表明,與前面的討論類似，這個(gè)遞推關(guān)系的解應(yīng)該是三次多項(xiàng)式，即可設(shè),初始條件有a1=2，a2=4，a3=8，a0=1。代入有,因此有,例5 平面上有一點(diǎn)P，它是n個(gè)區(qū)域D1,D2,…Dn的共同交界點(diǎn)。現(xiàn)取k種顏

7、色對(duì)這n個(gè)區(qū)域進(jìn)行著色，要求相鄰兩個(gè)區(qū)域著的顏色不同。求著色的方案數(shù)。,設(shè)不同的著色方案數(shù)為an。,(1) D1和Dn-1著色相同；,滿足條件的著色方案分為兩類：,(2) D1和Dn-1著色不同；,(1) 從D1到Dn-2的著色方案數(shù)為an-2(D1和Dn-2看作相鄰，著色不同)。,然后Dn-1和D1同色，Dn有k-1種顏色可選。,這種情形的總方案數(shù)為(k-1)an-2。,特征方程為：x2-(k-2)x-(k-1)=0。,由初始條件

8、a2=k(k-1)，a3=k(k-1)(k-2)，有,(2) 從D1到Dn-1的著色方案數(shù)為an-1(D1和Dn-1看作相鄰，著色不同)。,然后Dn有k-2種顏色可選。這種方案數(shù)為(k-2)an-1。,因此可以得到遞推關(guān)系式：,特征根為：k-1，-1。因此有,有,由此解得：,把a(bǔ)0=k，a1=0代入,因此滿足條件的不同著色方案數(shù)為：,例6 求n位二進(jìn)制數(shù)中最后三位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)。,這里所說(shuō)的010圖象是指：對(duì)于n位2進(jìn)制數(shù)從

9、左向右進(jìn)行掃描，一旦出現(xiàn)010圖象，便從這圖象后面一位繼續(xù)開(kāi)始掃描。,例如對(duì)11位2進(jìn)制數(shù)00101001010從左向右的掃描結(jié)果應(yīng)該是2-4，7-9位出現(xiàn)010圖象，即,而不是4-6，9-11位出現(xiàn)的010圖象，即不是,注意最后三位是010和最后三位出現(xiàn)010圖象的區(qū)別。,最后三位是010的n位二進(jìn)制數(shù)顯然有2n-3個(gè)。,設(shè)最后三位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)為an。,這些數(shù)可以分為兩類：最后三位出現(xiàn)010圖象以及第n-4位至第n-2位

10、出現(xiàn)010圖象。,這是一個(gè)二階線性常系數(shù)非齊次遞推關(guān)系。初始條件為a3=1，a4=2。,最后三位出現(xiàn)010圖象的數(shù)有an個(gè)，第n-4位至第n-2位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)為an-2。因此有,代入遞推關(guān)系解得： a2=2-a4=0，a1=1-a3=0，a0=1/2-a2=1/2。,先求對(duì)應(yīng)的齊次遞推關(guān)系的通解。,特征方程為x2+1=0，特征

11、根為i和-i。,由于右端項(xiàng)是2n-3，因此可以設(shè)一個(gè)特解為C2n。,所以遞推關(guān)系的解可以表示為：,因此齊次遞推關(guān)系的通解為：,代入初始條件有：,由此解得：,因此最后三位出現(xiàn)010圖象的數(shù)的個(gè)數(shù)為：,例7 求n位二進(jìn)制數(shù)中最后三位第一次出現(xiàn)010圖象的數(shù)的個(gè)數(shù)。,設(shè)最后三位第一次出現(xiàn)010圖象的數(shù)的個(gè)數(shù)為an。,同上例，最后三位是010的數(shù)有2n-3個(gè)。,這些數(shù)包括：,(1) 最后三位第一次出現(xiàn)010圖象的，個(gè)數(shù)為an：,(2) 第n-

12、4至n-2位第一次出現(xiàn)010圖象的，個(gè)數(shù)為an-2：,(3) 第n-5至n-3位第一次出現(xiàn)010圖象的，個(gè)數(shù)為an-3：,(4) 第n-6至n-4位第一次出現(xiàn)010圖象的：,注意到第n-3位可以取1或0，因此這種數(shù)有2an-4個(gè)。,一般的，對(duì)于k>3，第n-k-2至第n-k位第一次出現(xiàn)010圖象的數(shù)的個(gè)數(shù)為2k-3an-k，因?yàn)閺牡趎-k+1至第n-3的這k-3位每位都可取1或0。,因此有：,初始條件為a3=1，a4=2，a5=3

13、。,注意a5=3是因?yàn)樽詈?位是010的5位數(shù)有4個(gè)：,00010，01010，10010，11010.,但其中01010不滿足條件。,這不是一個(gè)常系數(shù)遞推關(guān)系，左邊的遞推關(guān)系中的項(xiàng)數(shù)和系數(shù)都是在不斷變化的。,例如，令n=6，則a6+a4+a3=8，由此得到a6=5。,例如，令n=7，則a7+a5+a4+2a3=16，由此得到a7=9。,得到一般通項(xiàng)表達(dá)式的方法比較特別。,設(shè)序列an對(duì)應(yīng)的母函數(shù)為：,則有：,x3:,x4:,x5:,+)

14、,整理得：,因此有：,例8 計(jì)算如下電路中各點(diǎn)的電壓vj(j=1,2,…n)：,取如右圖所示部分電路：,根據(jù)歐姆定律有,此外還有：ij+1=ij+vj+1/2。,消去ij即得到關(guān)于vj的遞推關(guān)系式：,或,特別的，由(v1-v0)/4=v0/2，可得v1=3v0。,這是一個(gè)線性常系數(shù)齊次遞推關(guān)系。,特征方程為：x2-4x+1=0，特征根為： 因此設(shè),代入初始條件：,解得：,則有,若電源電壓v已知，則可以由,解出v0