【正文】 賽中的數(shù)學(xué)知識(shí) ◆ 集合的運(yùn)算 ◆ 排列與組合 ◆ 集合及其運(yùn)算 集合的運(yùn)算：并、交、補(bǔ)、差 容斥原理 集合的運(yùn)算：并、交、補(bǔ)、差 并： ∪ 交： ∩ 補(bǔ)： ^或 ～或 差 : A B A B A A B A ∪ B A ∩ B A AB 8. （ NOIP9）設(shè)全集 E={1， 2， 3， 4， 5}，集合 A={1， 4}， B={1， 2， 5}， C={2，4}，則集合（ A ∩B ） ∪ ～ C 為（ ）。 A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g} 2. （ NOIP11）設(shè)全集 I = {a, b, c, d, e, f, g, h}， 集合 B∪A = {a, b, c, d, e, f}， C∩ A = {c, d, e}， A∩~B = {a, d} ，那么集合 C∩ B∩ A 為（ ）。 對(duì)有限集合 S，用 表示 S的元素個(gè)數(shù) S容斥原理的第一形式： 設(shè) A， B是有限集合，則 A B A B A B? ? ? ? ?容斥原理的第二形式：設(shè) A、 B、 C是有限集合，則 A B C A B C B C C A A B A B C? ? ? ? ? ? ? ? ? ? ? ? ? ? （ NOIP10） 75名兒童到游樂(lè)場(chǎng)去玩。已知其中20人這三種東西都玩過(guò)， 55人至少玩過(guò)其中的兩種。 某學(xué)校足球隊(duì)有球衣 30件，籃球隊(duì)有球衣 15件，排球隊(duì)有球衣 18件，三隊(duì)隊(duì)員總數(shù)為 50人，其中有 2人同時(shí)參加 3個(gè)隊(duì)，那么同時(shí) 只 參加兩個(gè)隊(duì)的隊(duì)員有多少？ ３、分母是 1001的最簡(jiǎn)分?jǐn)?shù)一共有多少個(gè)？ 10， 9 ◆ 排列與組合 : 從 n個(gè)不同元素中 ,任取 m個(gè)元素 ,按照一定的順序排成一列 ,叫做從 n個(gè)不同元素中取出 m個(gè)元素的一個(gè)排列 . 排列數(shù)公式 : 全排列問(wèn)題： n個(gè)不同的元素排成一排，排列方法有： nnP=n*(n1)*(n2)*?*2*1=n! : 從 n個(gè)不同元素中 ,任取 m個(gè)元素 ,并成一組 ,叫做從 n個(gè)不同元素中取出 m個(gè)元素的一個(gè)組合 . 組合數(shù)公式 : 排列與組合的區(qū)別與聯(lián)系 :與順序有關(guān)的為排列問(wèn)題 ,與順序無(wú)關(guān)的為組合問(wèn)題 . )!(!!!)1()2)(1(mnmnmmnnnnPPC mmmnmn?????????加法原理和乘法原理 從 A到 C共有多少中走法？ A B C 例 1 :學(xué)校師生合影，共 8個(gè)學(xué)生， 4個(gè)老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同的合影方式？ 解 先排學(xué)生共有 種排法 ,然后把老師插入學(xué)生之間的空檔，共有 7個(gè)空檔可插 ,選其中的 4個(gè)空檔 ,共有 種選法 .根據(jù)乘法原理 ,共有的不同坐法為 種 . 88P47P 4788 PP結(jié)論 1 插入法 :對(duì)于某兩個(gè)元素或者幾個(gè)元素要求不相鄰的問(wèn)題 ,可以用插入法 .即先排好沒有限制條件的元素 ,然后將有限制條件的元素按要求插入排好元素的空檔之中即可 . 例 2 : 5個(gè)男生 3個(gè)女生排成一排 ,3個(gè)女生要排在一起 ,有多少種不同的排法 ? 解 因?yàn)榕旁谝黄?,所以可以將 3個(gè)女生看成是一個(gè)人 ,與 5個(gè)男生作全排列 ,有 種排法 ,其中女生內(nèi)部也有 種排法 ,根據(jù)乘法原理 ,共有 種不同的排法 . 33P66P3366 PP結(jié)論 2 捆綁法 :要求某幾個(gè)元素必須排在一起的問(wèn)題 ,可以用捆綁法來(lái)解決問(wèn)題 .即將需要相鄰的元素合并為一個(gè)元素 ,再與其它元素一起作排列 ,同時(shí)要注意合并元素內(nèi)部也可以作排列 . 例 3 : 袋中有不同年份生產(chǎn)的 5分硬幣 23個(gè) ,不同年份生產(chǎn)的 1角硬幣 10個(gè) ,如果從袋中取出 2元錢 ,有多少種取法 ? 解 把所有的硬幣全部取出來(lái) ,將得到 23+ 10= ,所以比 2元多 ,所以剩下 3個(gè) 5分或 1個(gè) 5分與 1個(gè) 1角 ,所以共有 種取法 . 110123323 CCC ??結(jié)論 3 剩余法 :在組合問(wèn)題中 ,有多少取法 ,就有多少種剩法 ,他們是一一對(duì)應(yīng)的 ,因此 ,當(dāng)求取法困難時(shí) ,可轉(zhuǎn)化為求剩法 . 分析 此題是一個(gè)組合問(wèn)題 ,若是直接考慮取錢的問(wèn)題的話 ,情況比較多 ,也顯得比較凌亂 ,難以理出頭緒來(lái) .但是如果根據(jù)組合數(shù)性質(zhì)考慮剩余問(wèn)題的話 ,就會(huì)很容易解決問(wèn)題 . 例 4 學(xué)校安排考試科目 9門 ,語(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)支部書記至少有一人在內(nèi)的抽法有多少種 ? 解 43人中任抽 5人的方法有 種 ,正副班長(zhǎng) ,團(tuán)支部書記都不在內(nèi)的抽法有 種 ,所以正副班長(zhǎng) ,團(tuán)支部書記至少有 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，排成一排，有多少種排列方法。 2.（ NOIP7）平面上有三條平行直線，每條直線上分別有 7，5， 6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。 A. 40320 B. 39600 C. 840 D. 780 E. 60 1． (NOIP8) 在書架上放有編號(hào)為 1 ， 2 ，．．．， n的 n本書。例如： 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。 分析： 設(shè) f(n)為 n個(gè)不同元素的錯(cuò)排方案。 第二部分： n和其他的 n1個(gè)之一交換，其余的 n2個(gè)錯(cuò)排，共有 （ n1） *f（ n2）種方案。f(2)=1。從中取出一個(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)題。 Si≠∮ 。 S1∪ S2∪ … ∪ Sm=S。 編程：輸入 n和 m的值，輸出不同的劃分方案數(shù)。 樣例： 輸入： 4 3 輸出： 6 noip13 ? 1．給定 n 個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為 1， 2， …， n。例如，S(4,2)=7，這 7 種不同的放置方法依次為 ? {(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, ? {(14),(23)}。例如五邊形有如下五種拆分方案，故 f(5)=5。 區(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ù)目 問(wèn)題描述：求 n個(gè)結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目。 容易知道： f(1)=1。所以有： F(n)= 為了計(jì)算的方便：約定 f（ 0） =1 ???101)if( n *f( i)ni211nnCn ?問(wèn)題三：出棧序列 問(wèn)題描述： N個(gè)不同元素按一定的順序入棧，求不同的出棧序列數(shù)目。 容易得出： f（ 1） =1； f（ 2） =2。所以有： ??ni 1i)f ( n *1)f ( iF(n)= 三、集合取數(shù)問(wèn)題 設(shè) f(n,k)是從集合 {1， 2。 【 問(wèn)題分析 】 ： N有兩種情況： ① 當(dāng) n在子集時(shí)，則 n1一定不在子集中，即在 {1，2。 ② 當(dāng) n不在子集中時(shí)，則在 {1， 2。 所以： f(n,k)= f(n2,k1) +f(n1,k) 邊界條件： F(n,1)=n, f(n,k)=0 ( n=k) noip14 ? 2．書架上有 21本書，編號(hào)從 1到 21，從其中選 4本，其中每?jī)杀镜木幪?hào)都不相鄰的選法一共有 ______種。 例如： n=7， k=3，下面三種分法被認(rèn)為是相同的。 1， 5， 1。 問(wèn)有多少種不同的分法。 樣例 輸入： 7 3 輸出： 4 {四種分法為： 1， 1， 5。1， 3， 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的拆分方案。 ? 采用 a,b,c三個(gè)數(shù)組， a：被乘數(shù)， b：乘數(shù)， c：乘積。每次借助 k從 b中取項(xiàng)。任意兩種分法不能相同 (不考慮順序 )