【正文】 質(zhì)考慮剩余問(wèn)題的話 ,就會(huì)很容易解決問(wèn)題 . 例 4 學(xué)校安排考試科目 9門(mén) ,語(yǔ)文要在數(shù)學(xué)之前考 ,有多少種不同的安排順序 ? 解 不加任何限制條件 ,整個(gè)排法有 種 ,“語(yǔ)文安排在數(shù)學(xué)之前考 ” ,與 “ 數(shù)學(xué)安排在語(yǔ)文之前考 ” 的排法是相等的 ,所以語(yǔ)文安排在數(shù)學(xué)之前考的排法共有 種 . 99P9921P結(jié)論 4 對(duì)等法 :在有些題目中 ,它的限制條件的肯定與否定是對(duì)等的 ,各占全體的二分之一 .在求解中只要求出全體 ,就可以得到所求 . 分析 對(duì)于任何一個(gè)排列問(wèn)題 ,就其中的兩個(gè)元素來(lái)講的話 ,他們的排列順序只有兩種情況 ,并且在整個(gè)排列中 ,他們出現(xiàn)的機(jī)會(huì)是均等的 ,因此要求其中的某一種情況 ,能夠得到全體 ,那么問(wèn)題就可以解決了 .并且也避免了問(wèn)題的復(fù)雜性 . 例 5 某個(gè)班級(jí)共有 43位同學(xué) ,從中任抽 5人 ,正、副班長(zhǎng)、團(tuán)支部書(shū)記至少有一人在內(nèi)的抽法有多少種 ? 解 43人中任抽 5人的方法有 種 ,正副班長(zhǎng) ,團(tuán)支部書(shū)記都不在內(nèi)的抽法有 種 ,所以正副班長(zhǎng) ,團(tuán)支部書(shū)記至少有 1人在內(nèi)的抽法有 種 . 543C540C540543 CC ?結(jié)論 5 排異法 :有些問(wèn)題 ,正面直接考慮比較復(fù)雜 ,而它的反面往往比較簡(jiǎn)捷 ,可以先求出它的反面 ,再?gòu)恼w中排除 . 分析 此題若是直接去考慮的話 ,就要將問(wèn)題分成好幾種情況 ,這樣解題的話 ,容易造成各種情況遺漏或者重復(fù)的情況 .而如果從此問(wèn)題相反的方面去考慮的話 ,不但容易理解 ,而且在計(jì)算中也是非常的簡(jiǎn)便 .這樣就可以簡(jiǎn)化計(jì)算過(guò)程 . 圓周排列： 從 n個(gè)不同的元素中取 r個(gè)沿一圓周排列，排列的方案： rnP/r N個(gè)元素的圓周排列： nnP/n =（ n1） ! 有重復(fù)元素的排列問(wèn)題： 如： n1個(gè) a， n2個(gè) b， n3個(gè) c，排成一排，有多少種排列方法。 1 2 31 2 3( ) !! * ! * !n n nn n n??重復(fù)元素的組合問(wèn)題： 從 n種不同的元素中取 r個(gè)的元素的組合，允許有重復(fù)元素的組合： 1rnrC ??典型模型： r個(gè)相同的小球，放到 n個(gè)不同的盒子里，所有的放置方法。 2.（ NOIP7）平面上有三條平行直線，每條直線上分別有 7，5， 6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？ （ NOIP10）由 3個(gè) a， 5個(gè) b和 2個(gè) c構(gòu)成的所有字符串中，包含子串“ abc” 的共有（ ）個(gè)。 A. 40320 B. 39600 C. 840 D. 780 E. 60 1． (NOIP8) 在書(shū)架上放有編號(hào)為 1 ， 2 ，．．．， n的 n本書(shū)。現(xiàn)將 n本書(shū)全部取下然后再放回去，當(dāng)放回去時(shí)要求每本書(shū)都不能放在原來(lái)的位置上。例如： n = 3時(shí)： 原來(lái)位置為： 1 2 3 放回去時(shí)只能為： 3 1 2 或 2 3 1 這兩種 問(wèn)題：求當(dāng) n = 5時(shí)滿足以上條件的放法共有多少種？（不用列出每種放法） 錯(cuò)排問(wèn)題： n個(gè)不同元素的錯(cuò)排問(wèn)題： 如： 1， 2， 3。， n 的錯(cuò)排問(wèn)題， i不在第 i個(gè)位置的排列方法。 分析： 設(shè) f(n)為 n個(gè)不同元素的錯(cuò)排方案。 第一部分： n先不動(dòng)，把另外的 n1個(gè)數(shù)錯(cuò)排，方案是： f（ n1），然后 n和另外的 n1個(gè)每一個(gè)交換，共有 (n1)*f(n1)種方案。 第二部分： n和其他的 n1個(gè)之一交換，其余的 n2個(gè)錯(cuò)排，共有 （ n1） *f（ n2）種方案。 由加法原理： f(n)=(n1)*(f(n1)+f(n2)) f(1)=0。f(2)=1。 44 1 1 1 1 1( ) ! ( ......( 1 ) )2 ! 3! 4 ! 5 !nf n nn? ? ? ? ?錯(cuò)排的計(jì)算公式： 幾類重要的遞推關(guān)系： 一、第二類 Stirling數(shù) 問(wèn)題一：放置小球 n個(gè)有區(qū)別的球放到 m個(gè)相同的盒子中，要求無(wú)一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類 Stirling數(shù) 設(shè)有 n個(gè)不同的球，分別用 b1,b2,……bn 表示。從中取出一個(gè)球 bn，bn的放法有以下兩種： 1)bn獨(dú)自占一個(gè)盒子；那么剩下的球只能放在 m1個(gè)盒子中，方案數(shù)為 S(n1,m1) 2)bn與別的球共占一個(gè)盒子；那么可以事先將 b1,b2,……bn 1這 n1個(gè)球放入 m個(gè)盒子中，然后再將球 bn可以放入其中一個(gè)盒子中，方案數(shù)為 m*S(n1,m) S(n,m)=m*S(n1,m)+S(n1,m1) (n1,m1) 邊界條件： S2(n,1)=1； S2(n,n)=1； S2(n,k)=0(kn) 問(wèn)題二：集合劃分問(wèn)題。 設(shè) S是一個(gè)包含 n個(gè)元素的集合， S={b1,b2,b3,…,bn}, 現(xiàn)需要將 S集合劃分為 m個(gè)滿足如下條件的集合 S1,S2, …Sm 。 Si≠∮ 。 Si∩Sj=∮ 。 S1∪ S2∪ … ∪ Sm=S。 (1=I ,j=m) 則稱 S1,S2, …,Sm 是 S的一個(gè)劃分。 編程：輸入 n和 m的值，輸出不同的劃分方案數(shù)。 要求：輸入數(shù)據(jù)有一行，第一個(gè)數(shù)是 n,第二個(gè)數(shù) m。 樣例： 輸入： 4 3 輸出： 6 noip13 ? 1．給定 n 個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為 1， 2， …， n。將這 n 個(gè)球放入 r 個(gè)相同的盒子里，不允許 ? 有空盒，其不同放置方法的總數(shù)記為 S(n,r)。例如，S(4,2)=7，這 7 種不同的放置方法依次為 ? {(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, ? {(14),(23)}。當(dāng) n=7,r=4 時(shí)， S(7,4)= _____________ 二、 Catalan數(shù) 問(wèn)題一：凸 n邊形的三角形剖分 在一個(gè)凸 n邊形中，通過(guò)不相交于 n邊形內(nèi)部的對(duì)角線，把 n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用 f(n)表之， f(n)即為 Catalan數(shù)。例如五邊形有如下五種拆分方案，故 f(5)=5。求對(duì)于一個(gè)任意的凸 n邊形相應(yīng)的 f(n)。 區(qū)域①是一個(gè)凸 k邊形，區(qū)域②是一個(gè)凸 nk+1邊形， 區(qū)域①的拆分方案總數(shù)是 f(k)； 區(qū)域②的拆分方案數(shù)為 f(nk+1)； 故包含△ P1PkPn的 n 邊形的拆分方案數(shù)為 f(k)* f(nk+1)種 ????121)if ( n *f ( i)niF(n)= 問(wèn)題二：二叉樹(shù)數(shù)目 問(wèn)題描述：求 n個(gè)結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目。 【 問(wèn)題分析 】 ： 設(shè) F(n)為 n個(gè)結(jié)點(diǎn)組成二叉樹(shù)的數(shù)目。 容易知道： f(1)=1。 f(2)=2, f(3)=5 選定其中 1個(gè)結(jié)點(diǎn)為根，左子樹(shù)結(jié)點(diǎn)的個(gè)數(shù)為 i，二叉樹(shù)數(shù)目 f（ i）種；右子樹(shù)結(jié)點(diǎn)數(shù)目為 ni1，二叉樹(shù)數(shù)目 f（ ni1）種， I的可取范圍 [0， n1]。所以有： F(n)= 為了計(jì)算的方便：約定 f（ 0） =1 ???101)if( n *f( i)ni211nnCn ?問(wèn)題三：出棧序列 問(wèn)題描述： N個(gè)不同元素按一定的順序入棧，求不同的出棧序列數(shù)目。 【 問(wèn)題分析 】 ： 設(shè) f（ n）為 n個(gè)元素的不同出棧序列數(shù)目。 容易得出： f（ 1） =1； f（ 2） =2。 第 n個(gè)元素可以第 i（ 1=i=n）個(gè)出棧，前面已出棧有 i1個(gè)元素，出棧方法： f（ i1）；后面出棧 ni 個(gè)元素，出棧方法為： f（ ni）。所以有： ??ni 1i)f ( n *1)f ( iF(n)= 三、集合取數(shù)問(wèn)題 設(shè) f(n,k)是從集合 {1， 2。， n}中能夠選擇的沒(méi)有 兩個(gè)連續(xù) 整數(shù)的 k個(gè)元素子集的數(shù)目，求遞歸式 f(n,k)。 【 問(wèn)題分析 】 ： N有兩種情況： ① 當(dāng) n在子集時(shí)，則 n1一定不在子集中，即在 {1，2。， n2}中選 k1個(gè)元素，數(shù)目為 f(n2,k1)。 ② 當(dāng) n不在子集中時(shí)，則在 {1， 2。， n1}中選 k個(gè)元素，數(shù)目為 f(n1,k)。 所以： f(n,k)= f(n2,k1) +f(n1,k) 邊界條件： F(n,1)=n, f(n,k)=0 ( n=k) noip14 ? 2．書(shū)架上有 21本書(shū)，編號(hào)從 1到 21，從其中選 4本，其中每?jī)杀镜木幪?hào)都不相鄰的選法一共有 ______種。 418 3060C ?插 空 問(wèn) 題 ：四、整數(shù)劃分問(wèn)題 將整數(shù) n分成 k份，且每份不能為空，任意兩種分法不能相同 (不考慮順序 )。 例如： n=7， k=3，下面三種分法被認(rèn)為是相同的。 1， 1， 5。 1， 5， 1。 5， 1， 1。 問(wèn)有多少種不同的分法。 輸入： n， k (6n=200， 2=k=6) 輸出：一個(gè)整數(shù)，即不同的分法。 樣例 輸入： 7 3 輸出： 4 {四種分法為： 1， 1， 5。1， 2， 4。1， 3， 3。2， 2， 3。} 【 問(wèn)題分析 】 ： 用 f(i,j)表示將整數(shù) i分成 j分的分法，可以劃分為兩類： 1) ： j分中不包含 1的分法，為保證每份都 =2，可以先那出 j個(gè) 1分到每一份，然后再把剩下的 ij分成 j份即可，分法有： f(ij,j). 2) : j份中至少有一份為 1的分法，可以先那出一個(gè) 1作為單獨(dú)的 1份，剩下的 i1再分成 j1份即可，分法有： f(i1,j1). 所以 ： f(i,j)= f(ij,j)+ f(i1,j1) 邊界條件： f（ i， 1） =1， f（ i， j） =0， （ ij） ? 自然數(shù) n的拆分方案。 ? n=5,拆分?jǐn)?shù) 6 ? n=6,拆分?jǐn)?shù) 10 ? n=7,拆分?jǐn)?shù) 14 ? 1:5=1+4 ? 2:5=1+1+3 ? 3:5=1+1+1+2 ? 4:5=1+1+1+1+1 ? 5:5=1+2+2 ? 6:5=2+3 nj = 2[ f ( n j , j ) + f ( n 1 , j 1 )]?? 用母函數(shù)法： ? 當(dāng) n=5時(shí)： ? 構(gòu)造母函數(shù)如下： ? F(x)=(x0+x1+x2+x3+x4+x5)([x2]0+[x2]1+[x2]2)([x3]0+[x3]1) ? ([x4]0+[x4]1)([x5]0+[x5]1) ? =(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5) ? =1+x+2x2+3x3+5x4+7x5+…… ? 項(xiàng) a[i]Xi的系數(shù) a[i]， a[i]1即自然數(shù) i的拆分?jǐn)?shù) . ? 減 1是因?yàn)榘?i=i的一種拆分方案。 ? 采用 a,b,c三個(gè)數(shù)組， a：被乘數(shù)， b：乘數(shù)， c：乘積。 ? 多個(gè)多項(xiàng)式采用逐次相乘的方法。每次借助 k從 b中取項(xiàng)。 ? 將整數(shù) n分成 k份，且每份不能為空，且最大值不超過(guò) m的分法 。任意兩種分法不能相同 (不考慮順序 )。