章六節(jié)非線性遞推關(guān)系舉例ppt課件

1、第第2章章 遞推關(guān)系與母函數(shù)遞推關(guān)系與母函數(shù) 2.1 2.1 遞推關(guān)系遞推關(guān)系 2.2 2.2 母函數(shù)母函數(shù)( (生成函數(shù)生成函數(shù)) ) 2.3 Fibonacci 2.3 Fibonacci數(shù)列數(shù)列 2.4 2.4 優(yōu)選法與優(yōu)選法與FibonacciFibonacci序列的運(yùn)用序列的運(yùn)用 2.5 2.5 母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 2.6 2.6 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系 2.7 2.7 關(guān)于常系數(shù)非齊次遞推關(guān)系關(guān)于常系數(shù)非齊次遞推關(guān)系 2.8 2.8 整數(shù)的拆分整數(shù)的拆分 2.9 ferrers2.9 ferrers圖像圖像 2.10 2.10 拆分?jǐn)?shù)估計(jì)拆分?jǐn)?shù)估計(jì) 2.

2、11 2.11 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 2.12 2.12 廣義二項(xiàng)式定理廣義二項(xiàng)式定理 2.13 2.13 運(yùn)用舉例運(yùn)用舉例 2.14 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例 2.15 2.15 遞推關(guān)系解法的補(bǔ)充遞推關(guān)系解法的補(bǔ)充 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例(一一)多項(xiàng)式展開(kāi)式的討論多項(xiàng)式展開(kāi)式的討論(二二)第一類司特林第一類司特林(Stirling)數(shù)的討論數(shù)的討論(三三)第二類司特林第二類司特林(Stirling)數(shù)的討論數(shù)的討論 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例 (1)多項(xiàng)式系數(shù)多項(xiàng)式系數(shù) (x+y)n展開(kāi)式的通項(xiàng)展開(kāi)式的通項(xiàng)xkyn-k項(xiàng)

3、的系數(shù)是項(xiàng)的系數(shù)是:C(n,k) 相當(dāng)于相當(dāng)于2個(gè)不同的球取個(gè)不同的球取n個(gè)作有反復(fù)的陳列，其個(gè)作有反復(fù)的陳列，其中中x取取k個(gè)，個(gè)，y取取n-k個(gè)。個(gè)。 也相當(dāng)于也相當(dāng)于n個(gè)不同的球放入個(gè)不同的球放入2個(gè)不同盒子，個(gè)不同盒子，x盒子盒子放放k個(gè)，個(gè)，y盒子放盒子放n-k個(gè)。個(gè)。 指數(shù)型母函數(shù)是？指數(shù)型母函數(shù)是？(一一)多項(xiàng)式展開(kāi)式的討論多項(xiàng)式展開(kāi)式的討論 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例 (一一)多項(xiàng)式展開(kāi)式的討論多項(xiàng)式展開(kāi)式的討論 (2)多項(xiàng)式系數(shù)和多項(xiàng)式系數(shù)和 (x+y)n展開(kāi)式的系數(shù)和是展開(kāi)式的系數(shù)和是:2n 這種情況對(duì)應(yīng)著指數(shù)型母函數(shù)是？這種情況對(duì)應(yīng)著指數(shù)型母函數(shù)是？

4、展開(kāi)式的過(guò)程相當(dāng)于兩個(gè)不同的元素取展開(kāi)式的過(guò)程相當(dāng)于兩個(gè)不同的元素取n個(gè)的個(gè)的有反復(fù)的陳列。有反復(fù)的陳列。 也相當(dāng)于把也相當(dāng)于把n個(gè)不同的球放進(jìn)兩個(gè)不同的盒個(gè)不同的球放進(jìn)兩個(gè)不同的盒子中。子中。 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例 (一一)多項(xiàng)式展開(kāi)式的討論多項(xiàng)式展開(kāi)式的討論 (3)多項(xiàng)式的項(xiàng)數(shù)多項(xiàng)式的項(xiàng)數(shù) (x+y)n展開(kāi)式的項(xiàng)數(shù)是展開(kāi)式的項(xiàng)數(shù)是n+1 相當(dāng)于從兩個(gè)不同元素中取相當(dāng)于從兩個(gè)不同元素中取n個(gè)的組合數(shù)，允個(gè)的組合數(shù)，允許反復(fù)。許反復(fù)。 也相當(dāng)于把也相當(dāng)于把n個(gè)一樣的球放進(jìn)兩個(gè)不同的盒子個(gè)一樣的球放進(jìn)兩個(gè)不同的盒子中的方案數(shù)。中的方案數(shù)。 母函數(shù)是？母函數(shù)是？ 定理定理

5、2.14 (x1+x2+xm)n 展開(kāi)式通項(xiàng)展開(kāi)式通項(xiàng)項(xiàng)數(shù)等于項(xiàng)數(shù)等于C(m+n-1,n)nnnnxxxmnnnmm.,.2122112.14.1 司特林司特林(Stirling)數(shù)數(shù)* 系數(shù)之和等于系數(shù)之和等于mn 。 的系數(shù)是的系數(shù)是:!.!21mnnnn定義定義2.14.1 ) 1).(2)(1(nxxxxxn稱稱s(n,0),s(n,1),s(n,n)為第一類司特林?jǐn)?shù)。為第一類司特林?jǐn)?shù)。nkxnnsxknsxnsns),(.),(.) 1 ,() 0 ,(2.14.1 司特林司特林(Stirling)數(shù)數(shù)) 1)(2).(2)(1(nxnxxxx其中其中xk項(xiàng)的系數(shù)為項(xiàng)的系數(shù)為s(n-

6、1,k-1)-(n-1)s(n-1,k)1) 1, 1(.) 1 , 1() 0 , 1(kxknsxnsns2.14.1 司特林司特林(Stirling)數(shù)數(shù) ) 1).(2)(1(nxxxxxnnkxnnsxknsxnsns),(.),(.) 1 ,() 0 ,() 1(nx遞推關(guān)系式遞推關(guān)系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k) 1, 1(.), 1(1nkxnnsxkns2.14.1 司特林司特林(Stirling)數(shù)數(shù) ) 1).(2)(1(nxxxxxnnkxnnsxknsxnsns),(.),(.) 1 ,() 0 ,(遞推關(guān)系式遞推關(guān)系式s(n,k)=

7、s(n-1,k-1)-(n-1)s(n-1,k)初始條件：初始條件：s(n,0)=0當(dāng)當(dāng)kn時(shí)，時(shí)，s(n,k)=0s(n,n)=1* 定義定義2.14.2 n個(gè)有區(qū)別的球放到個(gè)有區(qū)別的球放到m個(gè)一個(gè)一樣的盒子中，要求無(wú)一空盒，其不同的方樣的盒子中，要求無(wú)一空盒，其不同的方案數(shù)用案數(shù)用S(n,m)表示，稱為第二類司特林?jǐn)?shù)。表示，稱為第二類司特林?jǐn)?shù)。 例如：紅、黃、藍(lán)例如：紅、黃、藍(lán)3種顏色的球種顏色的球3個(gè)，個(gè)，放到兩個(gè)無(wú)區(qū)別的盒子里，不允許空盒。放到兩個(gè)無(wú)區(qū)別的盒子里，不允許空盒。其方案如下：其方案如下：2.14.1 司特林司特林(Stirling)數(shù)數(shù)123盒盒ryb盒盒ybrbry討論的

8、是生討論的是生活中的分堆活中的分堆景象景象:與拆分有什與拆分有什么區(qū)別？么區(qū)別？ 定理定理2.14 第二類司特林?jǐn)?shù)第二類司特林?jǐn)?shù)S(n,k)有以下性質(zhì)：有以下性質(zhì)：; 1, 1.5; 1, 11.4; 1,0.3; 1,0.2;000.1nS(n,n)n)S(n,nkS(n,k)knS(n,k),n)S()S(n,若若若若 )4,(3)3,(2.9)2,(1.8;2)13(213.7; 122.6111nCnC)S(n,nnC)S(n,n)S(n,)S(n,nnn 2.14.1 司特林司特林(Stirling)數(shù)數(shù); 000. 1,n)S()S(n, 性質(zhì)性質(zhì)1的意思是把的意思是把n個(gè)不同的球

9、放進(jìn)個(gè)不同的球放進(jìn)0個(gè)盒子個(gè)盒子中或把中或把0個(gè)不同的球放進(jìn)個(gè)不同的球放進(jìn)n個(gè)盒子的方案數(shù)都是個(gè)盒子的方案數(shù)都是0。 性質(zhì)性質(zhì)2的意思是把的意思是把n個(gè)不同的球放進(jìn)個(gè)不同的球放進(jìn)k個(gè)盒子個(gè)盒子中中,當(dāng)球等于或多于盒子時(shí)，至少有一種方案。當(dāng)球等于或多于盒子時(shí)，至少有一種方案。 ; 1, 0 . 2knS(n,k)若2.14.1 司特林司特林(Stirling)數(shù)數(shù); 1, 0 . 3nkS(n,k)若 性質(zhì)性質(zhì)3的意思是把的意思是把n個(gè)球放進(jìn)個(gè)球放進(jìn)k個(gè)盒子中個(gè)盒子中,當(dāng)盒當(dāng)盒子多于球數(shù)時(shí)，要想使盒子不空是不能夠的。子多于球數(shù)時(shí)，要想使盒子不空是不能夠的。; 1, 11 . 4n)S(n,若 性

10、質(zhì)性質(zhì)4的意思是把的意思是把n個(gè)球放進(jìn)個(gè)球放進(jìn)1個(gè)盒子中個(gè)盒子中,放法只需一種。放法只需一種。; 1, 1. 5nS(n,n)若 性質(zhì)性質(zhì)5的意思是把的意思是把n個(gè)不同的球放進(jìn)個(gè)不同的球放進(jìn)n個(gè)一樣個(gè)一樣的盒子中的盒子中,不允許空盒，放法也只需一種。不允許空盒，放法也只需一種。2.14.1 司特林司特林(Stirling)數(shù)數(shù); 122 . 61n)S(n,意思是把意思是把n個(gè)不同的球放進(jìn)個(gè)不同的球放進(jìn)2個(gè)一樣的盒子中個(gè)一樣的盒子中, 當(dāng)?shù)谝粋€(gè)球放進(jìn)其中一個(gè)盒子后，其他當(dāng)?shù)谝粋€(gè)球放進(jìn)其中一個(gè)盒子后，其他n-1個(gè)有標(biāo)志的球都有兩種選擇，一種是選擇與第個(gè)有標(biāo)志的球都有兩種選擇，一種是選擇與第一個(gè)球

11、同盒，第二種選擇是與第一個(gè)球不同盒。一個(gè)球同盒，第二種選擇是與第一個(gè)球不同盒。共有共有2n-1種能夠，種能夠， 要排除都放在同一個(gè)盒子的情況。因此共要排除都放在同一個(gè)盒子的情況。因此共有有2n-1-1種方案。種方案。2.14.1 司特林司特林(Stirling)數(shù)數(shù);2) 13(213 . 711nn)S(n,2.14.1 司特林司特林(Stirling)數(shù)數(shù))2 ,(1 . 8nC)S(n,n 把把n個(gè)有標(biāo)志的球放進(jìn)個(gè)有標(biāo)志的球放進(jìn)n-1個(gè)一樣的盒子中，個(gè)一樣的盒子中，由于必需保證每個(gè)盒子中都有球，因此只需由于必需保證每個(gè)盒子中都有球，因此只需1個(gè)個(gè)盒子中有盒子中有2個(gè)球，問(wèn)題就是求兩個(gè)球的

12、組合數(shù)，個(gè)球，問(wèn)題就是求兩個(gè)球的組合數(shù)，因此有因此有C(n,2)種方案。種方案。)4 ,(3) 3 ,(2 . 9nCnC)S(n,n (1)、剩余的兩個(gè)球放進(jìn)一個(gè)盒子中，這樣的方、剩余的兩個(gè)球放進(jìn)一個(gè)盒子中，這樣的方案對(duì)應(yīng)著從案對(duì)應(yīng)著從n中取中取3個(gè)的組合數(shù)，是個(gè)的組合數(shù)，是C(n,3)。 (2)、剩余的兩個(gè)球放進(jìn)二個(gè)盒子中，這樣的、剩余的兩個(gè)球放進(jìn)二個(gè)盒子中，這樣的方案對(duì)應(yīng)著從方案對(duì)應(yīng)著從n中取中取4個(gè)，然后再把個(gè)，然后再把4個(gè)球兩兩分成個(gè)球兩兩分成2組，將組，將4個(gè)球分成兩組的方案數(shù)是個(gè)球分成兩組的方案數(shù)是C(4,2)/2。 因此在這種情況下方案數(shù)是：因此在這種情況下方案數(shù)是：C(n,4

13、)C(4,2)/2=3C(n,4)。 例如：例如：1,2,3,41,2,3,4分成兩兩分成兩兩2 2組的方案。組的方案。 (1,2),(3,4),(1,3),(2,4),(1,4),(2,3) (1,2),(3,4),(1,3),(2,4),(1,4),(2,3)2.14.1 司特林司特林(Stirling)數(shù)數(shù)定理定理2.15 第二類司特林?jǐn)?shù)滿足下面的遞推關(guān)系：第二類司特林?jǐn)?shù)滿足下面的遞推關(guān)系：1, 1),1, 1(), 1(mnmnSmnmSS(n,m) 證明：設(shè)有證明：設(shè)有n個(gè)有區(qū)別的球個(gè)有區(qū)別的球b1,b2,bn,對(duì)于對(duì)于其中的某一個(gè)球其中的某一個(gè)球bi, 根據(jù)根據(jù)bi的情況分為兩類：

14、的情況分為兩類：1、 bi獨(dú)占一盒，其方案為獨(dú)占一盒，其方案為S(n-1,m-1) 2、 bi不獨(dú)占一盒，這相當(dāng)于先將剩下的不獨(dú)占一盒，這相當(dāng)于先將剩下的n-1個(gè)球放到個(gè)球放到m個(gè)盒子，不允許空盒，共有個(gè)盒子，不允許空盒，共有S(n-1,m)種種不同方案，不同方案，2.14.1 司特林司特林(Stirling)數(shù)數(shù) 然后將然后將bi球放進(jìn)其中一盒，共有球放進(jìn)其中一盒，共有m種選擇方種選擇方式。式。bi球不獨(dú)占一盒的方案數(shù)為球不獨(dú)占一盒的方案數(shù)為mS(n-1,m)1, 1),1, 1(), 1(mnmnSmnmSS(n,m)2.14.1 司特林司特林(Stirling)數(shù)數(shù); 1, 1 .4;

15、1, 11 .3; 1,0 .2;000 .1nS(n,n)n)S(n,nkS(n,k),n)S()S(n,若若若 2、n個(gè)有標(biāo)志的球放進(jìn)個(gè)有標(biāo)志的球放進(jìn)m個(gè)有區(qū)別的盒子，個(gè)有區(qū)別的盒子，不允許空盒問(wèn)題不允許空盒問(wèn)題2.14.1 司特林司特林(Stirling)數(shù)數(shù) 1、n個(gè)有標(biāo)志的球放進(jìn)個(gè)有標(biāo)志的球放進(jìn)m個(gè)一樣的盒子，個(gè)一樣的盒子，不允許空盒問(wèn)題不允許空盒問(wèn)題 n個(gè)有標(biāo)志的球個(gè)有標(biāo)志的球b1,b2,bn ，放進(jìn)有區(qū)別，放進(jìn)有區(qū)別的的m個(gè)盒子個(gè)盒子c1,c2,cm中，無(wú)一空盒，其方中，無(wú)一空盒，其方案數(shù)為案數(shù)為m!S(n,m),其中其中1mnmknknkmkmCa0)(,() 1(mknkkm

16、kmCmmnS0)(,() 1(!1),(2.14.1 司特林司特林(Stirling)數(shù)數(shù)mknkkmkmCmmnS0)(,() 1(!1),(; 122 . 61n)S(n,;2) 13(213 . 711nn)S(n, n個(gè)球放到個(gè)球放到m個(gè)盒子里，那么球和盒子能否個(gè)盒子里，那么球和盒子能否有區(qū)別？能否允許空盒？共有有區(qū)別？能否允許空盒？共有23=8種形狀，其種形狀，其方案情況如下：方案情況如下： 1、n個(gè)不同的球放到個(gè)不同的球放到m個(gè)不同的盒子里，個(gè)不同的盒子里，允許空盒？允許空盒？ 2、n個(gè)不同的球放到個(gè)不同的球放到m個(gè)不同的盒子里，個(gè)不同的盒子里，不允許空盒。不允許空盒。有有mn個(gè)

17、方案。個(gè)方案。有有m!S(n,m)。2.14.1 司特林司特林(Stirling)數(shù)數(shù)mknknkmkmCa0)(,() 1( 4、n個(gè)不同的球放到個(gè)不同的球放到m個(gè)一樣的盒子里，允個(gè)一樣的盒子里，允許空盒，方案數(shù)情況？許空盒，方案數(shù)情況？S(n,1)+S(n,2)+S(n,m),nmS(n,1)+S(n,2)+S(n,n),nm。 可分為空可分為空m-1盒，盒，m-2盒，盒，空，空1盒，都不空。盒，都不空。 3、n個(gè)不同的球放到個(gè)不同的球放到m個(gè)一樣的盒子里，不個(gè)一樣的盒子里，不允許空盒，方案數(shù)情況？允許空盒，方案數(shù)情況？有有S(n,m)2.14.1 司特林司特林(Stirling)數(shù)數(shù)mk

18、nknkmkmCma0)(,() 1(!1 5、n個(gè)一樣的球放到個(gè)一樣的球放到m個(gè)不一樣的盒個(gè)不一樣的盒子里，允許空盒，方案數(shù)情況？子里，允許空盒，方案數(shù)情況？有有C(m+n-1,n)。 6、n個(gè)一樣的球放到個(gè)一樣的球放到m個(gè)不一樣的盒個(gè)不一樣的盒子里，不允許空盒，方案數(shù)情況？子里，不允許空盒，方案數(shù)情況？ 先取先取m個(gè)球每盒一個(gè)，余下的個(gè)球每盒一個(gè)，余下的n-m無(wú)區(qū)無(wú)區(qū)別的球放進(jìn)別的球放進(jìn)m個(gè)不一樣的盒子中。那么有個(gè)不一樣的盒子中。那么有C(m+(n-m)-1,n-m)=C(n-1,n-m)=C(n-1,m-1),2.14.1 司特林司特林(Stirling)數(shù)數(shù) 7、n個(gè)一樣的球放到個(gè)一樣

19、的球放到m個(gè)一樣的盒子里，允個(gè)一樣的盒子里，允許空盒，方案數(shù)為：許空盒，方案數(shù)為：)1).(1)(1 (1)(2mxxxxG xn項(xiàng)系數(shù)，相當(dāng)項(xiàng)系數(shù)，相當(dāng)于于n用用1,2,m進(jìn)進(jìn)展拆分的拆分?jǐn)?shù)。展拆分的拆分?jǐn)?shù)。 8、n個(gè)一樣的球放到個(gè)一樣的球放到m個(gè)一樣的盒子里，個(gè)一樣的盒子里，不允許空盒，方案數(shù)為：不允許空盒，方案數(shù)為：)1).(1)(1 ()(2mmxxxxxG的的xn項(xiàng)系數(shù)。項(xiàng)系數(shù)。2.14.1 司特林司特林(Stirling)數(shù)數(shù)*2.13 運(yùn)用舉例運(yùn)用舉例 錯(cuò)排問(wèn)題：假設(shè)一個(gè)陳列使得一切的錯(cuò)排問(wèn)題：假設(shè)一個(gè)陳列使得一切的元素都不在原來(lái)的位置上，那么稱這個(gè)陳元素都不在原來(lái)的位置上，那么

20、稱這個(gè)陳列為錯(cuò)排，也叫重排。列為錯(cuò)排，也叫重排。1,2的錯(cuò)排是獨(dú)一的的錯(cuò)排是獨(dú)一的,即即211,2,3的錯(cuò)排有的錯(cuò)排有312,231。2.13 運(yùn)用舉例運(yùn)用舉例對(duì)于對(duì)于1,2,n，設(shè)，設(shè)n個(gè)數(shù)的錯(cuò)排數(shù)為個(gè)數(shù)的錯(cuò)排數(shù)為Dn綜合以上分析得到遞推關(guān)系：綜合以上分析得到遞推關(guān)系： 1, 0),)(1(2121DDDDnDnnn 取取n分別與其它的分別與其它的n-1個(gè)數(shù)之一互換，其他個(gè)數(shù)之一互換，其他n-2個(gè)數(shù)進(jìn)展錯(cuò)排，共得個(gè)數(shù)進(jìn)展錯(cuò)排，共得(n-1)Dn-2個(gè)錯(cuò)排。個(gè)錯(cuò)排。 1、與、與Dn-1的關(guān)系：的關(guān)系： n-1個(gè)數(shù)進(jìn)展錯(cuò)排，然后個(gè)數(shù)進(jìn)展錯(cuò)排，然后n與其中每一個(gè)數(shù)與其中每一個(gè)數(shù)互換得到互換得到(n

21、-1)Dn-1個(gè)錯(cuò)排。個(gè)錯(cuò)排。 2、與、與Dn-2的關(guān)系：的關(guān)系：2.13 運(yùn)用舉例運(yùn)用舉例! nDEnn令21!) 1(!) 1(!nnnDnnDnnnD1, 0),)(1(2121DDDDnDnnn)!2(1)!1() 1(21nDnnDnnnn211)11 (nnnEnEnE)(1(211nnnnEEnEE2.13 運(yùn)用舉例運(yùn)用舉例)(1(211nnnnEEnEE1nnnEEF設(shè)11nnFnF2221!2)1(.)(11)(1(1FnFnnFnFnnnn21! 1! 212122DDEEF2.13 運(yùn)用舉例運(yùn)用舉例!1) 1(,!1) 1(1nEEnFnnnnn即211)!1(1) 1(

22、!1) 1(!1) 1(nnnnnnEnnEnE1! )!1) 1(.! 31! 21! 111 ( ! !ennnEnDnnn121! 2) 1(.)!1() 1(!) 1(Ennnn 2.13 運(yùn)用舉例運(yùn)用舉例 例例2.13.1 數(shù)數(shù)1,2,3,9的全陳列中，求偶數(shù)在的全陳列中，求偶數(shù)在原來(lái)位置上，其他都不在原來(lái)位置上的錯(cuò)排數(shù)目。原來(lái)位置上，其他都不在原來(lái)位置上的錯(cuò)排數(shù)目。 實(shí)踐上這是一個(gè)實(shí)踐上這是一個(gè)79的錯(cuò)排問(wèn)題。的錯(cuò)排問(wèn)題。441-520-60 )12012416121120( )! 51! 41! 31! 21! 111 ( ! 55D2.13 運(yùn)用舉例運(yùn)用舉例 例例2.13.2

23、求在求在8個(gè)字母?jìng)€(gè)字母A,B,C,D,E,F,G,H的的全陳列中，只需全陳列中，只需4個(gè)元素不在原來(lái)位置上的陳個(gè)元素不在原來(lái)位置上的陳列數(shù)。列數(shù)。914-12 )2416121(24)! 41! 31! 21! 111 ( ! 44D從從8個(gè)字母中任取個(gè)字母中任取4個(gè)的組合數(shù)為個(gè)的組合數(shù)為C(8,4)6309) 4 , 8 (C 4個(gè)字母的錯(cuò)排數(shù)為：個(gè)字母的錯(cuò)排數(shù)為：例例2.13.3 求求nknkS02解：解：2222) 1(.321nnSn2221) 1(.321nSn21nSSnn2.13 運(yùn)用舉例運(yùn)用舉例特解特解:)(33221nknknkSn23322133221) 1() 1() 1

24、(nnknknknknknk2.13 運(yùn)用舉例運(yùn)用舉例23323221332nknknkknkk130320332132kkkkkk,31,21,61312kkk)312161(32nnnhSn32312161nnnSn2.13 運(yùn)用舉例運(yùn)用舉例 例例2.13.4 10個(gè)數(shù)字個(gè)數(shù)字(0到到9)和和4個(gè)四那么運(yùn)算個(gè)四那么運(yùn)算符符+、-、組成的組成的14個(gè)元素。求由其中的個(gè)元素。求由其中的n個(gè)元素的陳列構(gòu)成一算術(shù)表達(dá)式的個(gè)數(shù)。個(gè)元素的陳列構(gòu)成一算術(shù)表達(dá)式的個(gè)數(shù)。1、與、與an-1的關(guān)系的關(guān)系 解：設(shè)解：設(shè)n個(gè)元素的算術(shù)表達(dá)式個(gè)數(shù)為個(gè)元素的算術(shù)表達(dá)式個(gè)數(shù)為an。10an-1 。2、與、與an-2的關(guān)

25、系的關(guān)系40an-2 。214010nnnaaa2.13 運(yùn)用舉例運(yùn)用舉例 例例2.13.5 n條直線將平面分成多少個(gè)域？假定無(wú)三條直線將平面分成多少個(gè)域？假定無(wú)三線共點(diǎn)，且兩兩相交。線共點(diǎn)，且兩兩相交。 設(shè)設(shè)n條直線將平面分成條直線將平面分成Dn個(gè)域，那么第個(gè)域，那么第n條直線被條直線被其他的其他的n-1條直線分割成條直線分割成n段。這段。這n段正好是新添加的段正好是新添加的n個(gè)域的邊境。個(gè)域的邊境。 所以：所以：Dn=Dn-1+n,D1=2, D0=12.13 運(yùn)用舉例運(yùn)用舉例 例例2.13.6 設(shè)有設(shè)有n條橢圓曲線，兩兩相交于兩點(diǎn)，恣意條橢圓曲線，兩兩相交于兩點(diǎn)，恣意3條橢圓曲線條橢圓曲

26、線不相交于一點(diǎn)，試問(wèn)這樣的不相交于一點(diǎn)，試問(wèn)這樣的n個(gè)橢圓將平面分隔成多少部分？個(gè)橢圓將平面分隔成多少部分？ 一個(gè)橢圓將平面分隔成內(nèi)、外兩部分。一個(gè)橢圓將平面分隔成內(nèi)、外兩部分。an= an-1+2(n-1), a1=22.13 運(yùn)用舉例運(yùn)用舉例 例例 2.13.7 一個(gè)圓域，依圓心等分成一個(gè)圓域，依圓心等分成n個(gè)部分如下圖，個(gè)部分如下圖，用用k種顏色對(duì)這種顏色對(duì)這n個(gè)域進(jìn)展涂色，要求相鄰的域不同色，試個(gè)域進(jìn)展涂色，要求相鄰的域不同色，試問(wèn)有多少種涂色方案。問(wèn)有多少種涂色方案。 設(shè)設(shè)an表示表示n個(gè)域的涂色方案數(shù)，分兩種情況來(lái)個(gè)域的涂色方案數(shù)，分兩種情況來(lái)討論。討論。 (1)與與an-1的關(guān)系，的關(guān)