組合數(shù)學(xué)課件-教案

1、課程簡(jiǎn)介課程簡(jiǎn)介相關(guān)課程相關(guān)課程使用教材使用教材數(shù)學(xué)分析數(shù)學(xué)分析高等代數(shù)高等代數(shù)離散數(shù)學(xué)離散數(shù)學(xué)書(shū)名：組合數(shù)學(xué)（第三版）書(shū)名：組合數(shù)學(xué)（第三版） 本課程針對(duì)計(jì)算機(jī)科學(xué)中的一個(gè)重要學(xué)科本課程針對(duì)計(jì)算機(jī)科學(xué)中的一個(gè)重要學(xué)科組合數(shù)學(xué)，組合數(shù)學(xué)，組合數(shù)學(xué)是數(shù)學(xué)的一個(gè)分支，它研究事物在結(jié)定模式下的配組合數(shù)學(xué)是數(shù)學(xué)的一個(gè)分支，它研究事物在結(jié)定模式下的配置，研究這種配置的存在性，所有可能配置的計(jì)數(shù)和分類以置，研究這種配置的存在性，所有可能配置的計(jì)數(shù)和分類以及配置的各種性質(zhì)。組合數(shù)學(xué)在計(jì)算機(jī)科學(xué)中有著極其廣泛及配置的各種性質(zhì)。組合數(shù)學(xué)在計(jì)算機(jī)科學(xué)中有著極其廣泛的應(yīng)用。的應(yīng)用。 組合學(xué)問(wèn)題求解方法層出不窮、干變

2、萬(wàn)化，應(yīng)以理解為組合學(xué)問(wèn)題求解方法層出不窮、干變?nèi)f化，應(yīng)以理解為基礎(chǔ)，善于總結(jié)各種技巧，掌握科學(xué)的組織和推理方法?；A(chǔ)，善于總結(jié)各種技巧，掌握科學(xué)的組織和推理方法。目錄（目錄（1）引言引言第第1章章 排列與組合排列與組合 1.1 加法法則和乘法法則 1.2 排列 1.3 組合 1.4 二項(xiàng)式定理 1.5 組合恒等式及其含義 1.6 模型轉(zhuǎn)換 本章小結(jié) 習(xí)題第第2章章 鴿籠原理鴿籠原理 2.1 鴿籠原理 2.2 鴿籠原理的推廣 2.3 Ramsey定理 本章小結(jié) 習(xí)題第第3章章 容斥原理容斥原理 3.1 容斥原理 3.2 重集r-組合 3.3 錯(cuò)排問(wèn)題 3.4 有限制排列 3.5* 一般有限制排

3、列 3.6* 廣義容斥原理 本章小結(jié) 習(xí)題第第4章章 母函數(shù)母函數(shù) 4.1 母函數(shù)的基本概念 4.2 母函數(shù)的基本運(yùn)算 4.3 在排列組合中的應(yīng)用 4.4 整數(shù)的拆分 4.5 Ferrers圖目目 錄錄目錄（目錄（2） 4.6* 在組合恒等式中的應(yīng)用 本章小結(jié) 習(xí)題第第5章章 遞推關(guān)系遞推關(guān)系 5.1 遞推關(guān)系的建立 5.2 常系數(shù)線性齊次遞推關(guān)系 5.3 常系數(shù)線性非齊次遞推關(guān)系 5.4 迭代法與歸納法 5.5 母函數(shù)在遞推關(guān)系中的應(yīng)用 5.6* 典型的遞推關(guān)系 本章小結(jié) 習(xí)題第第6章章 Plya定理定理 6.1 群的概念 6.2 置換群 6.3 循環(huán)、奇循環(huán)與偶循環(huán) 6.4 Burnsid

4、e引理 6.5 Plya定理 6.6 Plya定理的應(yīng)用 6.7 母函數(shù)形式的Plya定理 6.8* 圖的計(jì)數(shù) 6.9* Plya定理的若干推廣 本章小結(jié) 習(xí)題*課程總結(jié)課程總結(jié)注：加*的章節(jié)一般性了解引引 言言發(fā)展歷史發(fā)展歷史涵蓋內(nèi)容涵蓋內(nèi)容學(xué)習(xí)目的學(xué)習(xí)目的學(xué)習(xí)方法學(xué)習(xí)方法 存在性問(wèn)題存在性問(wèn)題 計(jì)數(shù)和枚舉計(jì)數(shù)和枚舉 優(yōu)化優(yōu)化問(wèn)題問(wèn)題 構(gòu)造性問(wèn)題構(gòu)造性問(wèn)題 科學(xué)的組織科學(xué)的組織 科學(xué)的推理科學(xué)的推理 古老古老 年輕年輕 練習(xí)練習(xí) 思考總結(jié)思考總結(jié) 筆記筆記組合數(shù)學(xué)研究的中心問(wèn)題是按照一定的規(guī)組合數(shù)學(xué)研究的中心問(wèn)題是按照一定的規(guī)則來(lái)安排有限多個(gè)對(duì)象則來(lái)安排有限多個(gè)對(duì)象 如果人們想把有限多個(gè)對(duì)象

5、按照它們所應(yīng)滿足的條件來(lái)進(jìn)行安排，當(dāng)符合要求的安排并非顯然存在或顯然不存在時(shí)，首要的問(wèn)題就是要證明或者否定它的存在。這就是存在性問(wèn)題。如果所要求的安排存在，則可能有多種不同的安排，這又經(jīng)常給人們提出這樣的問(wèn)題：有多少種可能的安排方案？如何對(duì)安排的方案進(jìn)行分類？這就是計(jì)數(shù)問(wèn)題。如果一個(gè)組合問(wèn)題有解，則往往需要給出求其某一特定解的算法，這就是所謂的構(gòu)造性問(wèn)題。如果算法很多，就需要在一定的條件下找出一個(gè)或者幾個(gè)最優(yōu)或近乎最優(yōu)的安排方案，這就是優(yōu)化問(wèn)題。第第1章章 排列與組合排列與組合 本章重點(diǎn)介紹以下的基本計(jì)數(shù)方法：本章重點(diǎn)介紹以下的基本計(jì)數(shù)方法： 加法法則和乘法法則加法法則和乘法法則 排列排列 組

6、合組合 二項(xiàng)式定理的應(yīng)用二項(xiàng)式定理的應(yīng)用 組合恒等式組合恒等式 相互獨(dú)立相互獨(dú)立的事件的事件 A、B 分別有分別有 k 和和 l 種方法產(chǎn)生，則產(chǎn)生種方法產(chǎn)生，則產(chǎn)生 A 或或 B 的方的方法數(shù)為法數(shù)為 k+l 種。種。1.1 加法法則1.1 加法法則和乘法法則加法法則和乘法法則1.1.1 加法法則加法法則加法法則加法法則集合論定義集合論定義 若若|A|=k，|B|=l ，且，且AB= ，則則|AB| = k+l 。 設(shè)設(shè)S是有限集合，若是有限集合，若 ，且，且時(shí)，時(shí)， ，則有，則有 。ij ijSS 1,miiiSSSS 11mmiiiiSSS 1.1 加法法則例11.1 加法法則和乘法法則

7、加法法則和乘法法則1.1.1 加法法則加法法則例例 題題例例1、有一所學(xué)校給一名物理競(jìng)賽優(yōu)勝有一所學(xué)校給一名物理競(jìng)賽優(yōu)勝者發(fā)獎(jiǎng)，獎(jiǎng)品有三類，第一類是三種者發(fā)獎(jiǎng)，獎(jiǎng)品有三類，第一類是三種不同版本的法漢詞典；第二類是四種不同版本的法漢詞典；第二類是四種不同類型的物理參考書(shū)；第三類是二不同類型的物理參考書(shū)；第三類是二種不同的獎(jiǎng)杯。這位優(yōu)勝者只能挑選種不同的獎(jiǎng)杯。這位優(yōu)勝者只能挑選一樣獎(jiǎng)品。那么，這位優(yōu)勝者挑選獎(jiǎng)一樣獎(jiǎng)品。那么，這位優(yōu)勝者挑選獎(jiǎng)品的方法有多少種？品的方法有多少種？解：解：設(shè)設(shè)S是所有這些獎(jiǎng)品的集合，是所有這些獎(jiǎng)品的集合，Si是第是第i類獎(jiǎng)品的集合類獎(jiǎng)品的集合(i=1,2,3)，顯然，顯

8、然，SiSj= (ij) ，根據(jù)加法，根據(jù)加法法則法則有有iiSSSSS31231| | | |3429 1.1 加法法則例2、31.1 加法法則和乘法法則加法法則和乘法法則1.1.1 加法法則加法法則例例 題題例例2、大于大于0小于小于10的奇偶數(shù)的奇偶數(shù)有多少個(gè)？有多少個(gè)？例例3、小于小于20可被可被2或或3整除的自然整除的自然數(shù)有多少個(gè)？數(shù)有多少個(gè)？解：解：設(shè)設(shè)S是符合條件數(shù)的集合，是符合條件數(shù)的集合，S1、S2分別是符合條件的分別是符合條件的奇數(shù)、偶數(shù)集合，顯然，奇數(shù)、偶數(shù)集合，顯然，S1S2= ，根據(jù)加法，根據(jù)加法法則法則有有SSS12| | |549 若若|A|=k，|B|=l ，

9、A B=(a,b)|aA，bB，則，則|A B| = k l 。1.1 乘法法則1.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則乘法法則乘法法則 相互獨(dú)立相互獨(dú)立的事件的事件 A、B 分別有分別有 k 和和 l 種方法產(chǎn)生，則選取種方法產(chǎn)生，則選取A以后以后再選取再選取B 的方法數(shù)為的方法數(shù)為 kl 種。種。集合論定義集合論定義 設(shè)設(shè) 是有限集合，且是有限集合，且 ，則有，則有 。11mmiiiiSSS1miiSS (1,2,.,)iS im 12(,.,)|,1,2,.,miia aaaS im1.1 乘法法則例41.1 加法法則和乘法法則加法法則和乘法法則1.1.2

10、 乘法法則乘法法則例例 題題例例4、從從A 地到地到B地有二條不同的道地有二條不同的道路，從路，從B地到地到C地有四條不同的道路，地有四條不同的道路，而從而從C地到地到D地有三條不同的道路。地有三條不同的道路。求從求從A地經(jīng)地經(jīng)B、C兩地到達(dá)兩地到達(dá)D地的道路地的道路數(shù)。數(shù)。解：解：設(shè)設(shè)S是所求的道路數(shù)集合，是所求的道路數(shù)集合，S1、S2、S3分別是從分別是從A到到B、從、從B到到C、從、從C到到D的道路集合，根據(jù)乘法的道路集合，根據(jù)乘法法則法則有有SSSS123| | | |2 4 324 1.1 乘法法則例51.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則例例 題題

11、例例5、由數(shù)字由數(shù)字1,2,3,4,5可以構(gòu)成多少個(gè)可以構(gòu)成多少個(gè)所有數(shù)字互不相同的四位偶數(shù)？所有數(shù)字互不相同的四位偶數(shù)？解：解：所求的是四位偶數(shù)，故個(gè)位只能選所求的是四位偶數(shù)，故個(gè)位只能選2或或4，有兩種選，有兩種選擇方法；又由于要求四位數(shù)字互不相同，故個(gè)位選中后，擇方法；又由于要求四位數(shù)字互不相同，故個(gè)位選中后，十位只有四種選擇方法；同理，百位、千位分別有三種、十位只有四種選擇方法；同理，百位、千位分別有三種、兩種選擇方法，根據(jù)乘法兩種選擇方法，根據(jù)乘法法則，四位數(shù)互不相同的偶數(shù)法則，四位數(shù)互不相同的偶數(shù)個(gè)數(shù)為個(gè)數(shù)為2 4 3 2=481.1 乘法法則例61.1 加法法則和乘法法則加法法則

12、和乘法法則1.1.2 乘法法則乘法法則例例 題題例例6、求出從求出從8個(gè)計(jì)算機(jī)系的學(xué)生、個(gè)計(jì)算機(jī)系的學(xué)生、 9個(gè)數(shù)學(xué)系的學(xué)生和個(gè)數(shù)學(xué)系的學(xué)生和10個(gè)經(jīng)濟(jì)系的學(xué)生個(gè)經(jīng)濟(jì)系的學(xué)生中選出兩個(gè)不同專業(yè)的學(xué)生的方法數(shù)。中選出兩個(gè)不同專業(yè)的學(xué)生的方法數(shù)。解：解：由乘法由乘法法則法則有有選一個(gè)計(jì)算機(jī)系和一個(gè)數(shù)學(xué)系的方法數(shù)為選一個(gè)計(jì)算機(jī)系和一個(gè)數(shù)學(xué)系的方法數(shù)為89=72選一個(gè)數(shù)學(xué)系和一個(gè)經(jīng)濟(jì)系的方法數(shù)為選一個(gè)數(shù)學(xué)系和一個(gè)經(jīng)濟(jì)系的方法數(shù)為910=90選一個(gè)經(jīng)濟(jì)系和一個(gè)計(jì)算機(jī)系的方法數(shù)為選一個(gè)經(jīng)濟(jì)系和一個(gè)計(jì)算機(jī)系的方法數(shù)為108=80由加法由加法法則法則，符合要求的方法數(shù)為，符合要求的方法數(shù)為72+90+80=2

13、421.1 重集的概念1.1 加法法則和乘法法則加法法則和乘法法則1.1.3 計(jì)數(shù)問(wèn)題的分類計(jì)數(shù)問(wèn)題的分類 有序安排或有序選擇有序安排或有序選擇 允許重復(fù)允許重復(fù)/不允許重復(fù)不允許重復(fù) 無(wú)序安排或無(wú)序選擇無(wú)序安排或無(wú)序選擇 允許重復(fù)允許重復(fù)/不允許重復(fù)不允許重復(fù) 標(biāo)準(zhǔn)集的特性：確定、無(wú)序、標(biāo)準(zhǔn)集的特性：確定、無(wú)序、相異等。相異等。 重集：重集：B=k1*b1, k2*b2, kn*bn，其中：，其中：bi為為n個(gè)互不相個(gè)互不相同的元素，稱同的元素，稱 ki為為bi的的重?cái)?shù)重?cái)?shù)， i=1,2,n，n=1,2, ，ki=1,2, 。重集的概念重集的概念1.2 線排列1.2 排列排列定義定義 1.1

14、1.2.1 線排列線排列集合論定義集合論定義定理定理 1.1從從n個(gè)不同元素中，取個(gè)不同元素中，取r個(gè)個(gè)(0rn)按一按一定順序排列起來(lái)，其排列數(shù)定順序排列起來(lái)，其排列數(shù)P(n,r)。設(shè)設(shè)A=an ，從，從A中選擇中選擇r個(gè)個(gè)(0rn)元素排元素排列起來(lái)，列起來(lái)，A的的r有序子集，有序子集，A的的r排列。排列。如如n, rZ且且nr0, P(n,r)=n!/(n-r)!。如如n=r，稱全排列，稱全排列P(n,n)= n!；如如nr, P(n,r)=0；如；如r=0, P(n,r)=1。證明：證明：構(gòu)造集合構(gòu)造集合A的的r排列時(shí)，可以從排列時(shí)，可以從A的的n各元素中任各元素中任選一個(gè)作為排列的第

15、一項(xiàng)，有選一個(gè)作為排列的第一項(xiàng)，有n種選法；第一項(xiàng)選定后種選法；第一項(xiàng)選定后從剩下的從剩下的n-1個(gè)元素中選排列的第二項(xiàng)有個(gè)元素中選排列的第二項(xiàng)有n-1種選法；種選法；由此類推，第由此類推，第r項(xiàng)有項(xiàng)有n-r+1種選法。根據(jù)乘法種選法。根據(jù)乘法法則法則有有!( , )(1).(1)()!nP n rn nnrnr 1.2 線排列推論11.2 排列排列1.2.1 線排列線排列兩個(gè)推論兩個(gè)推論推論推論1.1.1：如如n, rN且且nr2，則，則P(n,r)=nP(n-1,r-1) 。證明：證明：在集合在集合A的的n個(gè)元素中，任一個(gè)元素都可以排在個(gè)元素中，任一個(gè)元素都可以排在它的它的r排列首位，故首

16、位有排列首位，故首位有n種取法；首位取定后，其種取法；首位取定后，其他位置的元素正好是從他位置的元素正好是從A的另的另n-1個(gè)元素中取個(gè)元素中取r-1個(gè)的排個(gè)的排列，因此有列，因此有P(n-1,r-1)種取法。由乘法法則有種取法。由乘法法則有P(n,r)=nP(n-1,r-1)證畢。證畢。1.2 線排列推論21.2 排列排列1.2.1 線排列線排列兩個(gè)推論兩個(gè)推論推論推論1.1.1：如如n, rN且且nr2，則，則P(n,r)=nP(n-1,r-1) 。推論推論1.1.2：如如n, rN且且nr2，則，則P(n,r)= rP(n-1,r-1)+P(n-1,r) 。證明：證明：當(dāng)當(dāng)r2時(shí)，把集合

17、時(shí)，把集合A的的r排列分為兩大類：一類包含排列分為兩大類：一類包含A中的某個(gè)固定元素，不妨設(shè)為中的某個(gè)固定元素，不妨設(shè)為a1，另一類不包含，另一類不包含a1 。第。第一類排列相當(dāng)于先從一類排列相當(dāng)于先從A-a1中取中取r-1個(gè)元素進(jìn)行排列，有個(gè)元素進(jìn)行排列，有P(n-1,r-1)種取法，再將種取法，再將a1放入每一個(gè)上述排列中，對(duì)任一放入每一個(gè)上述排列中，對(duì)任一排列，排列，a1都有都有r種放法。由乘法法則，第一類排列共有種放法。由乘法法則，第一類排列共有rP(n-1,r-1)個(gè)。第二類排列實(shí)質(zhì)上是個(gè)。第二類排列實(shí)質(zhì)上是A-a1的的r排列，共排列，共有有P(n-1,r)個(gè)。再由加法法則有個(gè)。再由

18、加法法則有P(n,r)= rP(n-1,r-1)+P(n-1,r)證畢。證畢。1.2 線排列例11.2 排列排列1.2.1 線排列線排列例例 題題例例1、由數(shù)字由數(shù)字1,2,3,4,5可以構(gòu)成多可以構(gòu)成多少個(gè)所有數(shù)字互不相同的四位數(shù)？少個(gè)所有數(shù)字互不相同的四位數(shù)？解：解：由于所有的四位數(shù)字互不相同，故每一個(gè)四位數(shù)就由于所有的四位數(shù)字互不相同，故每一個(gè)四位數(shù)就是集合是集合1,2,3,4,5的一個(gè)的一個(gè)4排列，因而所求的四位數(shù)個(gè)排列，因而所求的四位數(shù)個(gè)數(shù)為數(shù)為5!(5,4)120(54)!P 1.2 線排列例21.2 排列排列1.2.1 線排列線排列例例 題題例例 2 、 將 具 有將 具 有 9

19、 個(gè) 字 母 的 單 詞個(gè) 字 母 的 單 詞FRAGMENTS進(jìn)行排列，要求字母進(jìn)行排列，要求字母A總是緊跟在字母總是緊跟在字母R的右邊，問(wèn)有的右邊，問(wèn)有多少種這樣的排法？如果再要求字多少種這樣的排法？如果再要求字母母M和和N必須相鄰呢？必須相鄰呢？解：解：由于由于A總是總是R的右邊，故這樣的排列的右邊，故這樣的排列相當(dāng)于相當(dāng)于是是8個(gè)元個(gè)元素的集合素的集合F,RA,G,M,E,N,T,S的一個(gè)全排列，個(gè)數(shù)為的一個(gè)全排列，個(gè)數(shù)為如果再要求如果再要求M和和N必須相鄰，可先把必須相鄰，可先把M和和N看成一個(gè)整看成一個(gè)整體體 =M,N，進(jìn)行，進(jìn)行7個(gè)元素的集合個(gè)元素的集合F,RA,G,E,T,S,

20、 的全的全排列，在每一個(gè)排列中再進(jìn)行排列，在每一個(gè)排列中再進(jìn)行 M,N的全排列，由乘法的全排列，由乘法法則，排列個(gè)數(shù)為法則，排列個(gè)數(shù)為(8,8)8!40320P(7,7)(2,2)7! 2!10080PP1.2 線排列例31.2 排列排列1.2.1 線排列線排列例例 題題例例3、有多少個(gè)有多少個(gè)5位數(shù)，每位數(shù)字都位數(shù)，每位數(shù)字都不相同，不能取不相同，不能取0，且數(shù)字，且數(shù)字7和和9不能不能相鄰？相鄰？解：解：由于所有的由于所有的5位數(shù)字互不相同，且不能取位數(shù)字互不相同，且不能取0，故每一，故每一個(gè)個(gè)5位數(shù)就是集合位數(shù)就是集合1,2,9的一個(gè)的一個(gè)5-排列，其排列數(shù)為排列，其排列數(shù)為P(9,5)

21、，其中，其中7和和9相鄰的排列數(shù)為相鄰的排列數(shù)為c(7,3)4!242P(7,3)，滿足題目要求的滿足題目要求的5位數(shù)個(gè)數(shù)為位數(shù)個(gè)數(shù)為(9,5)4 2(7,3)15120168013440PP 1.2 圓排列1.2 排列排列定義定義 1.21.2.2 圓排列圓排列定理定理 1.2設(shè)設(shè)A=an ，從，從A中取中取r個(gè)個(gè)(0rn)元素按元素按某種順序（如逆時(shí)針）排成一個(gè)圓圈，某種順序（如逆時(shí)針）排成一個(gè)圓圈，稱為圓排列（循環(huán)排列）。稱為圓排列（循環(huán)排列）。設(shè)設(shè)A=an，A的的r圓排列個(gè)數(shù)為圓排列個(gè)數(shù)為P(n,r)/r。證明：證明：由于把一個(gè)圓排列旋轉(zhuǎn)所得到另一個(gè)圓排列視為由于把一個(gè)圓排列旋轉(zhuǎn)所得到

22、另一個(gè)圓排列視為相同的圓排列，因此線排列相同的圓排列，因此線排列a1a2ar，a2a3ara1， ara1a2ar-1在圓排列中是一個(gè)，即一個(gè)圓排列可產(chǎn)生在圓排列中是一個(gè)，即一個(gè)圓排列可產(chǎn)生r個(gè)個(gè)不同的線排列；同理，不同的線排列；同理， r個(gè)不同的線排列對(duì)應(yīng)一個(gè)圓排個(gè)不同的線排列對(duì)應(yīng)一個(gè)圓排列。而總共有列。而總共有P(n,r)個(gè)線排列，故圓排列的個(gè)數(shù)為個(gè)線排列，故圓排列的個(gè)數(shù)為 P(n,r)/r= n!/(r(n-r)!)證畢。證畢。1.2 圓排列例41.2 排列排列例例 題題1.2.2 圓排列圓排列例例4、有有8人圍圓桌就餐，問(wèn)有多少種人圍圓桌就餐，問(wèn)有多少種就座方式？如果有兩人不愿坐在一起

23、，就座方式？如果有兩人不愿坐在一起，又有多少種就座方式？又有多少種就座方式？解：解：由上述定理知由上述定理知8人圍圓桌就餐，有人圍圓桌就餐，有8!/8=7!=5040種就種就座方式。座方式。又有兩人不愿坐在一起，不妨設(shè)此二人為又有兩人不愿坐在一起，不妨設(shè)此二人為A、B，當(dāng)，當(dāng)A、B坐在一起時(shí)，相當(dāng)于坐在一起時(shí)，相當(dāng)于7人圍圓桌就餐，有人圍圓桌就餐，有7!/7=6!種就種就座方式。座方式。 而而A、B坐在一起時(shí)，又有兩種情況，或者坐在一起時(shí)，又有兩種情況，或者A在在B的左面，或者的左面，或者A在在B的右面，因此的右面，因此A、B坐在一起時(shí)，坐在一起時(shí)，共有共有26!種就座方式，因此如果有兩人不愿

24、坐在一起，種就座方式，因此如果有兩人不愿坐在一起，就座方式為就座方式為7!-26!= 56!=36001.2 圓排列例51.2 排列排列例例 題題1.2.2 圓排列圓排列例例5、4男男4女圍圓桌交替就座有多女圍圓桌交替就座有多少種就座方式？少種就座方式？解：解：顯然，這是一個(gè)圓排列問(wèn)題。首先讓顯然，這是一個(gè)圓排列問(wèn)題。首先讓4個(gè)男的圍圓個(gè)男的圍圓桌就座，有桌就座，有4!/4=3!種就座方式。種就座方式。 因?yàn)橐竽信畤鷪A桌因?yàn)橐竽信畤鷪A桌交替就座，在男的坐定后，兩兩之間均需留有一個(gè)空位，交替就座，在男的坐定后，兩兩之間均需留有一個(gè)空位，女的就座相當(dāng)于一個(gè)女的就座相當(dāng)于一個(gè)4元素集合的全排列，

25、就座方式數(shù)元素集合的全排列，就座方式數(shù)為為4!。由乘法法則知，就座方式數(shù)為。由乘法法則知，就座方式數(shù)為3!4!=1441.2 重排列1.2 排列排列定義定義 1.31.2.3 重排列重排列集合論定義集合論定義定理定理 1.3從從n個(gè)不同元素中，可重復(fù)選取個(gè)不同元素中，可重復(fù)選取r個(gè)按個(gè)按一定順序排列起來(lái)，稱為重排列。一定順序排列起來(lái)，稱為重排列。從重集從重集B=k1*b1, k2*b2, , kn*bn中選中選取取r個(gè)按一定順序排列起來(lái)。個(gè)按一定順序排列起來(lái)。重集重集B=*b1, *b2, , *bn 的的r排排列的個(gè)數(shù)為列的個(gè)數(shù)為nr。證明：證明：構(gòu)造構(gòu)造B的的r排列如下：選擇第一項(xiàng)時(shí)可從排

26、列如下：選擇第一項(xiàng)時(shí)可從n個(gè)元素個(gè)元素中任選一個(gè)，有中任選一個(gè)，有n種選法，選擇第二項(xiàng)時(shí)由于可以重復(fù)種選法，選擇第二項(xiàng)時(shí)由于可以重復(fù)選取，仍有選取，仍有n種選法，種選法，同理，選擇第，同理，選擇第r項(xiàng)時(shí)仍有項(xiàng)時(shí)仍有n種種選法，根據(jù)乘法法則，可得出選法，根據(jù)乘法法則，可得出r排列的個(gè)數(shù)為排列的個(gè)數(shù)為nr。證畢。證畢。1.2 重排列例61.2 排列排列例例 題題1.2.3 重排列重排列例例6、由數(shù)字由數(shù)字1,2,3,4,5,6這六個(gè)數(shù)字能這六個(gè)數(shù)字能組成多少個(gè)五位數(shù)？又可組成多少組成多少個(gè)五位數(shù)？又可組成多少大于大于34500的五位數(shù)？的五位數(shù)？解：解：一個(gè)五位數(shù)的各位數(shù)字可重復(fù)出現(xiàn)，是一個(gè)典型的

27、一個(gè)五位數(shù)的各位數(shù)字可重復(fù)出現(xiàn)，是一個(gè)典型的重排列問(wèn)題，相當(dāng)于重集重排列問(wèn)題，相當(dāng)于重集B=*1,*2,*6的的5排排列，所求的五位數(shù)個(gè)數(shù)為列，所求的五位數(shù)個(gè)數(shù)為65=7776。 大于大于34500的五位數(shù)可由下面三種情況組成：的五位數(shù)可由下面三種情況組成： 萬(wàn)位選萬(wàn)位選4,5,6中的一個(gè)，其余中的一個(gè)，其余4位相當(dāng)于重集位相當(dāng)于重集B的的4排列，排列，由乘法法則知，共有由乘法法則知，共有3 64個(gè)五位數(shù)；個(gè)五位數(shù)； 萬(wàn)位是萬(wàn)位是3，千位，千位5,6中的一個(gè)，其余中的一個(gè)，其余3位相當(dāng)于重集位相當(dāng)于重集B的的3排列，由乘法法則知，共有排列，由乘法法則知，共有2 63個(gè)五位數(shù)；個(gè)五位數(shù)； 萬(wàn)位是

28、萬(wàn)位是3，千位，千位4中的一個(gè)，百位選中的一個(gè)，百位選5,6中的一個(gè)，其余中的一個(gè)，其余2位相當(dāng)于重集位相當(dāng)于重集B的的2排列，由乘法法則知，共有排列，由乘法法則知，共有2 62個(gè)五位數(shù)；個(gè)五位數(shù)； 由加法法則知，大于由加法法則知，大于34500的五位數(shù)個(gè)數(shù)為的五位數(shù)個(gè)數(shù)為364 + 263 + 262=43921.2 重排列計(jì)數(shù)1.2 排列排列1.2.3 重排列重排列定理定理 1.4重集重集B=n1*b1,n2*b2,nk*bk的全排列的全排列個(gè)數(shù)為個(gè)數(shù)為112!,! .!kiiknnnnnn其其中中證明：證明：將將B中的中的ni個(gè)個(gè)bi看作不同的看作不同的ni個(gè)元素，賦予上標(biāo)個(gè)元素，賦予上

29、標(biāo)1,2, ni，即，即 ，如此，重集，如此，重集B就變成具有就變成具有n1+n2+nk=n個(gè)不同的元素集合個(gè)不同的元素集合顯然，集合顯然，集合A的全排列個(gè)數(shù)為的全排列個(gè)數(shù)為n!。又由于又由于ni個(gè)個(gè)bi賦予上標(biāo)的方法有賦予上標(biāo)的方法有ni!種，于是對(duì)重集種，于是對(duì)重集B的任一的任一個(gè)全排列，都可以產(chǎn)生集合個(gè)全排列，都可以產(chǎn)生集合A的的n1!n2!nk!個(gè)排列（由個(gè)排列（由乘法法則），故重集乘法法則），故重集B的全排列個(gè)數(shù)為的全排列個(gè)數(shù)為證畢。證畢。注：利用組合數(shù)的計(jì)數(shù)方法同樣可以得出證明。注：利用組合數(shù)的計(jì)數(shù)方法同樣可以得出證明。12,.,(1,2,., )iniiib bbik 12121

30、212111222,.,.,.,.,knnnkkkAb bbb bbb bb 112! .!kiiknnnnnn其其中中1.2 重排列例71.2 排列排列1.2.3 重排列重排列例例 題題例例6、有四面紅旗，三面藍(lán)旗，二面有四面紅旗，三面藍(lán)旗，二面黃旗，五面綠旗可以組成多少種由黃旗，五面綠旗可以組成多少種由14面旗子組成的一排彩旗？面旗子組成的一排彩旗？解：解：這是一個(gè)重排列問(wèn)題，是求重集這是一個(gè)重排列問(wèn)題，是求重集4*紅旗紅旗,3*藍(lán)旗藍(lán)旗,2*黃黃旗旗,5*綠旗綠旗的全排列個(gè)數(shù)，根據(jù)定理，一排彩旗的種數(shù)為的全排列個(gè)數(shù)，根據(jù)定理，一排彩旗的種數(shù)為14!25225204! 3! 2! 5! 1

31、.2 重排列例81.2 排列排列1.2.3 重排列重排列例例 題題例例8、用字母用字母A、B、C組成五個(gè)字母組成五個(gè)字母的符號(hào)，要求在每個(gè)符號(hào)里，的符號(hào)，要求在每個(gè)符號(hào)里，A至多至多出現(xiàn)出現(xiàn)2次，次，B至多出現(xiàn)至多出現(xiàn)1次，次，C至多出至多出現(xiàn)現(xiàn)3次，求此類符號(hào)的個(gè)數(shù)。次，求此類符號(hào)的個(gè)數(shù)。解：解：這也是一個(gè)重排列問(wèn)題。根據(jù)分析，符合題意的符號(hào)這也是一個(gè)重排列問(wèn)題。根據(jù)分析，符合題意的符號(hào)個(gè)數(shù)相當(dāng)于求重集個(gè)數(shù)相當(dāng)于求重集M=2*A,1*B,3*C的的5排列個(gè)數(shù)，可分排列個(gè)數(shù)，可分為三種情況：需要分別求為三種情況：需要分別求M-A、M-B和和M-C的全排列的全排列個(gè)數(shù)。根據(jù)加法法則，此類符號(hào)個(gè)數(shù)

32、為個(gè)數(shù)。根據(jù)加法法則，此類符號(hào)個(gè)數(shù)為5!5!5!601! 1! 3!2! 0! 3!2! 1! 2! 1.2 項(xiàng)鏈排列1.2 排列排列定義定義 1.41.2.4 項(xiàng)鏈排列項(xiàng)鏈排列 對(duì)圓排列，通過(guò)轉(zhuǎn)動(dòng)、平移、翻轉(zhuǎn)、可重合的，即對(duì)圓排列，通過(guò)轉(zhuǎn)動(dòng)、平移、翻轉(zhuǎn)、可重合的，即可看作項(xiàng)鏈排列?？煽醋黜?xiàng)鏈排列。 如如n個(gè)不同元素的個(gè)不同元素的r項(xiàng)鏈排列個(gè)數(shù)為項(xiàng)鏈排列個(gè)數(shù)為P(n,r)/(2r)，具體參照具體參照Plya定理定理。1.3 無(wú)重組合1.3 組合組合定義定義 1.51.3.1 （無(wú)重）組合（無(wú)重）組合集合論定義集合論定義定理定理 1.5設(shè)設(shè)A=an，從，從A中選擇中選擇r個(gè)個(gè)(0rn)元素組合元

33、素組合起來(lái)，起來(lái)，A的的r無(wú)序子集，無(wú)序子集，A的的r組合。組合。如如rn，有，有C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)。如如nr=0，C(n,r)=1；如如nr，C(n,r)=0。從從n個(gè)不同元素中，取個(gè)不同元素中，取r個(gè)個(gè)(0rn)不考不考慮順序組合起來(lái)，其組合數(shù)慮順序組合起來(lái)，其組合數(shù)C(n,r) 或或 。 nr證明：證明：從從n個(gè)不同元素中取個(gè)不同元素中取r個(gè)元素的組合數(shù)為個(gè)元素的組合數(shù)為C(n,r)，而而r個(gè)元素可組成個(gè)元素可組成r!個(gè)個(gè)r排列，即一個(gè)排列，即一個(gè)r組合對(duì)應(yīng)組合對(duì)應(yīng)r!個(gè)個(gè)r排列。于是排列。于是C(n,r)個(gè)個(gè)r組合對(duì)應(yīng)組合對(duì)應(yīng)r!C(n,r)個(gè)

34、個(gè)r排列，這是排列，這是從從n個(gè)不同元素中取個(gè)不同元素中取r個(gè)元素的個(gè)元素的r排列數(shù)排列數(shù)P(n,r)，因此有，因此有 ( , )!( , )!()!P n rnnC n rrrrnr1.3 無(wú)重組合推論11.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合三個(gè)推論三個(gè)推論推論推論1.5.1：C(n,r)=C(n,n-r)證明：證明：實(shí)際上，從實(shí)際上，從n個(gè)不同元素中選出個(gè)不同元素中選出r個(gè)元素的同時(shí)，個(gè)元素的同時(shí)，就有就有n-r個(gè)元素沒(méi)有被選出，因此選出個(gè)元素沒(méi)有被選出，因此選出r個(gè)元素的方式數(shù)個(gè)元素的方式數(shù)等于選出等于選出n-r個(gè)元素的方式數(shù)，即個(gè)元素的方式數(shù)，即C(n,r)=C(n,n-

35、r)。得證。得證。另外，也可通過(guò)計(jì)算得出證明如下另外，也可通過(guò)計(jì)算得出證明如下 !( ,)( , )()!()! !nnC n nrC n rnrnnrnrr1.3 無(wú)重組合推論21.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合三個(gè)推論三個(gè)推論推論推論1.5.1：C(n,r)=C(n,n-r)推論推論1.5.2 (Pascal公式公式)：C(n,r)=C(n-1,r)+C(n-1,r-1) 證明：證明：利用組合分析法。在集合利用組合分析法。在集合A的的n個(gè)不同元素中固個(gè)不同元素中固定一個(gè)元素，不妨設(shè)為定一個(gè)元素，不妨設(shè)為a1 ，從，從n個(gè)元素中選出個(gè)元素中選出r個(gè)元素的個(gè)元素的組合由下面兩

36、種情況組成：組合由下面兩種情況組成： r個(gè)元素中包含個(gè)元素中包含a1。相當(dāng)于從除去。相當(dāng)于從除去a1的的n-1個(gè)元素中選個(gè)元素中選出出r-1個(gè)元素的組合，再加上個(gè)元素的組合，再加上a1而得到，組合數(shù)為而得到，組合數(shù)為C(n-1,r-1)； r個(gè)元素中不包含個(gè)元素中不包含a1。相當(dāng)于從除去。相當(dāng)于從除去a1的的n-1個(gè)元素中個(gè)元素中選出選出r個(gè)元素的組合而得到，組合數(shù)為個(gè)元素的組合而得到，組合數(shù)為C(n-1,r)。由加法法則即得由加法法則即得C(n,r)=C(n-1,r)+C(n-1,r-1)另外，也可通過(guò)計(jì)算得出證明如下另外，也可通過(guò)計(jì)算得出證明如下 !(1)!()(1)!(1)!( , )!

37、()!(1)!(1)!(1)!(1)!(1)!(1)!(1(1)!(1, )(1,1)nn nnrnr nC n rrnrrnrr rnrnrnnrnrrnrC nrC nr 1.3 無(wú)重組合推論31.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合三個(gè)推論三個(gè)推論推論推論1.5.1：C(n,r)=C(n,n-r)推論推論1.5.2 (Pascal公式公式)：C(n,r)=C(n-1,r)+C(n-1,r-1) 推論推論1.5.3：C(n,r)=C(n-1,r-1)+C(n-2,r-1)+ +C(r-1,r-1)證明：證明：反復(fù)利用反復(fù)利用Pascal公式，即可證明。公式，即可證明?；蚶媒M合

38、分析法，在集合或利用組合分析法，在集合A=an的的n個(gè)不同元素選出個(gè)不同元素選出r個(gè)元素的個(gè)元素的組合可分為以下多種情況：組合可分為以下多種情況： 如如r個(gè)元素中包含個(gè)元素中包含a1，相當(dāng)于從除去，相當(dāng)于從除去a1的的n-1個(gè)元素中選出個(gè)元素中選出r-1個(gè)元素的組合，再加上個(gè)元素的組合，再加上a1而得到，組合而得到，組合數(shù)為數(shù)為C(n-1,r-1)；如；如r個(gè)元素中不包含個(gè)元素中不包含a1但包含但包含a2，相當(dāng)于從除去，相當(dāng)于從除去a1,a2的的n-2個(gè)元素中選出個(gè)元素中選出r-1個(gè)元素的組合，再加上個(gè)元素的組合，再加上a2而得到，組而得到，組合數(shù)為合數(shù)為C(n-2,r-1), 同理如同理如r

39、個(gè)元素中不包含個(gè)元素中不包含a1,a2,an-r，但包含，但包含an-r+1，相當(dāng)于從剩下的，相當(dāng)于從剩下的r-1個(gè)元素中選出個(gè)元素中選出r-1個(gè)元素的組合，再加個(gè)元素的組合，再加上上an-r+1而得到，組合數(shù)為而得到，組合數(shù)為C(r-1,r-1) 。由加法法則得。由加法法則得C(n,r)=C(n-1,r-1)+C(n-2,r-1)+ +C(r-1,r-1)1.3 無(wú)重組合例11.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合例例 題題例例1、有有5本日文書(shū)，本日文書(shū)，7本英文書(shū)，本英文書(shū)，10本中文書(shū)，從中取兩本不同文字的書(shū)，本中文書(shū)，從中取兩本不同文字的書(shū)，問(wèn)有多少種方案？若取兩本相同文

40、字問(wèn)有多少種方案？若取兩本相同文字的書(shū)，問(wèn)有多少種方案？任取兩本書(shū)，的書(shū)，問(wèn)有多少種方案？任取兩本書(shū)，有多少種方案？有多少種方案？解：解：從三種文字的書(shū)中取兩種共有從三種文字的書(shū)中取兩種共有C(3,2)=3種取法。根據(jù)乘法法種取法。根據(jù)乘法法則有：日英各一本的方法數(shù)為則有：日英各一本的方法數(shù)為57=35，中英各一本的方法數(shù)為，中英各一本的方法數(shù)為107=70，中日各一本的方法數(shù)為，中日各一本的方法數(shù)為105=50，由加法法則得，由加法法則得35+70+50=155取兩本相同文字的，有兩本中文、兩本英文或兩本日文三種方取兩本相同文字的，有兩本中文、兩本英文或兩本日文三種方式，由加法法則得式，由加

41、法法則得C(5,2)+C(7,2)+C(10,2)=76任取兩本書(shū)，相當(dāng)于從任取兩本書(shū)，相當(dāng)于從5+7+10=22本書(shū)中取兩本的組合，即本書(shū)中取兩本的組合，即C(22,2)=2311.3 無(wú)重組合例21.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合例例 題題例例2、從從1300之間任取之間任取3個(gè)不同的數(shù)，個(gè)不同的數(shù)，使得這使得這3個(gè)數(shù)的和正好被個(gè)數(shù)的和正好被3除盡，問(wèn)共除盡，問(wèn)共有幾種方案？有幾種方案？解：解：所有的整數(shù)可分為以下所有的整數(shù)可分為以下3個(gè)分類：模個(gè)分類：模3余余0、模、模3余余1和模和模3余余2，故故1300的的300個(gè)數(shù)可以分為個(gè)數(shù)可以分為3個(gè)集合：個(gè)集合：A=1,4,

42、298，B=2,5,299，C=3,6,300。任取。任取3個(gè)數(shù)其和正好被個(gè)數(shù)其和正好被3整除的整除的情況如下：情況如下：三個(gè)數(shù)同屬于集合三個(gè)數(shù)同屬于集合A，有，有C(100,3)種方案；種方案；三個(gè)數(shù)同屬于集合三個(gè)數(shù)同屬于集合B，有，有C(100,3)種方案；種方案；三個(gè)數(shù)同屬于集合三個(gè)數(shù)同屬于集合C，有，有C(100,3)種方案；種方案；三個(gè)數(shù)分別屬于集合三個(gè)數(shù)分別屬于集合A,B,C，由乘法法則有，由乘法法則有1003種方案。種方案。由加法法則得，所求的方案數(shù)為由加法法則得，所求的方案數(shù)為3C(100,3)+1003=14851001.3 無(wú)重組合例31.3 組合組合1.3.1 （無(wú)重）組

43、合（無(wú)重）組合例例 題題例例3、某車站有某車站有1到到6個(gè)入口處，每個(gè)個(gè)入口處，每個(gè)入口處每次只能進(jìn)一個(gè)人，問(wèn)一小組入口處每次只能進(jìn)一個(gè)人，問(wèn)一小組9個(gè)人進(jìn)站的方案數(shù)有多少？個(gè)人進(jìn)站的方案數(shù)有多少？解解I ：把兩個(gè)入口間設(shè)上一個(gè)標(biāo)志，加上這把兩個(gè)入口間設(shè)上一個(gè)標(biāo)志，加上這5個(gè)標(biāo)志相當(dāng)于每一個(gè)標(biāo)志相當(dāng)于每一個(gè)排列有個(gè)排列有14個(gè)元素，問(wèn)題轉(zhuǎn)化為重集個(gè)元素，問(wèn)題轉(zhuǎn)化為重集1*p1,1*p2,1*p9,5*標(biāo)志標(biāo)志的全排列（的全排列（pi代表代表9個(gè)人，個(gè)人，i=1,9），故進(jìn)站方案數(shù)為），故進(jìn)站方案數(shù)為14!/5!=726485760解解II ：考慮考慮9個(gè)人選擇方案，第個(gè)人選擇方案，第1個(gè)人有個(gè)

44、人有6種選擇，第種選擇，第2個(gè)人除了個(gè)人除了選擇入口，還要考慮在第選擇入口，還要考慮在第1個(gè)人的前面或后面，故有個(gè)人的前面或后面，故有7種選擇種選擇同理，第同理，第9個(gè)人有個(gè)人有14種選擇，根據(jù)乘法法則，故進(jìn)站方案數(shù)為種選擇，根據(jù)乘法法則，故進(jìn)站方案數(shù)為6 7 14=7264857601.3 無(wú)重組合例61.3 組合組合1.3.1 （無(wú)重）組合（無(wú)重）組合例例 題題例例6、求能除盡求能除盡1400的正整數(shù)數(shù)目（的正整數(shù)數(shù)目（1除外），其中包含多少個(gè)奇數(shù)？除外），其中包含多少個(gè)奇數(shù)？ 解：解：1400=23527，故除盡，故除盡1400的正整數(shù)分解為素?cái)?shù)的乘積的正整數(shù)分解為素?cái)?shù)的乘積的形式應(yīng)該為

45、的形式應(yīng)該為2l5m7n，其中，其中0l3,0m2,0n1，但應(yīng)排除，但應(yīng)排除l=m=n=0的情況。故滿足條件的數(shù)目為的情況。故滿足條件的數(shù)目為(3+1)(2+1)(1+1)-1=23其中包含的奇數(shù)為其中包含的奇數(shù)為(1)(2+1)(1+1)-1=51.3 重復(fù)組合1.3 組合組合定義定義 1.61.3.2 重復(fù)組合重復(fù)組合集合論定義集合論定義定理定理 1.6從從n個(gè)不同元素中，可重復(fù)選取個(gè)不同元素中，可重復(fù)選取r個(gè)不個(gè)不考慮順序組合起來(lái)，其組合數(shù)考慮順序組合起來(lái)，其組合數(shù)F(n,r)。從重集從重集B=k1*b1, k2*b2, , kn*bn中取中取r個(gè)元素不考慮順序的組合。個(gè)元素不考慮順序

46、的組合。重集重集B=*b1, *b2, , *bn 的的r組組合數(shù)合數(shù)F(n,r) = C(n+r-1, r)證明：證明：設(shè)設(shè)n個(gè)元素個(gè)元素b1,b2,bn和自然數(shù)和自然數(shù)1,2,n一一對(duì)應(yīng)。于一一對(duì)應(yīng)。于是任何組合皆可看作是一個(gè)是任何組合皆可看作是一個(gè)r個(gè)數(shù)的組合個(gè)數(shù)的組合c1,c2,cr。由于。由于是組合，不妨認(rèn)為各是組合，不妨認(rèn)為各ci是按照大小順序排列的，相同的是按照大小順序排列的，相同的ci連連續(xù)排在一起，不妨設(shè)續(xù)排在一起，不妨設(shè)c1c2cr 。又令又令di=ci+i-1(i=1,2,r)，即，即d1=c1,d2=c2+1,dr=cr+r-1。因因1cin，故，故1din+r-1，得

47、到一個(gè)集合，得到一個(gè)集合1,2,n+r-1的的r組合組合 d1,d2,dr (d1d2dr) 。顯然有一種顯然有一種c1,c2,cr的取法，就有一種的取法，就有一種d1,d2,dr的取的取法，反之亦然，這兩種取法是法，反之亦然，這兩種取法是一一對(duì)應(yīng)的一一對(duì)應(yīng)的，從而這兩種取，從而這兩種取法是法是等價(jià)的等價(jià)的。如此，從。如此，從n個(gè)不同元素中可重復(fù)選取個(gè)不同元素中可重復(fù)選取r個(gè)的組個(gè)的組合數(shù)，和從合數(shù)，和從n+r-1個(gè)不同元素中不重復(fù)選取個(gè)不同元素中不重復(fù)選取r個(gè)的組合數(shù)是個(gè)的組合數(shù)是相同的，故相同的，故F(n,r) = C(n+r-1, r)1.3 重復(fù)組合例71.3 組合組合定理定理 1.7

48、1.3.2 重復(fù)組合重復(fù)組合例例 題題r個(gè)無(wú)區(qū)別的球放入個(gè)無(wú)區(qū)別的球放入n個(gè)有標(biāo)志的盒子個(gè)有標(biāo)志的盒子里，每盒的球數(shù)可多于里，每盒的球數(shù)可多于1個(gè)，則共有個(gè)，則共有F(n,r)種方案。種方案。例例7、試問(wèn)試問(wèn)(x+y+z)4的展開(kāi)式有多少的展開(kāi)式有多少項(xiàng)？項(xiàng)？證明：證明：這是一個(gè)允許重復(fù)組合的典型問(wèn)題，實(shí)質(zhì)上定這是一個(gè)允許重復(fù)組合的典型問(wèn)題，實(shí)質(zhì)上定理理1.6的另一種說(shuō)法。由于每盒的球數(shù)不受限制，相當(dāng)?shù)牧硪环N說(shuō)法。由于每盒的球數(shù)不受限制，相當(dāng)于重集于重集*a1,*a2,*an的的r組合。組合。解：解：(x+y+z)4展開(kāi)式每一項(xiàng)都是展開(kāi)式每一項(xiàng)都是4次方的，相當(dāng)于從次方的，相當(dāng)于從3個(gè)個(gè)不同元

49、素中可以重復(fù)的選擇不同元素中可以重復(fù)的選擇4個(gè)，或者相當(dāng)于將個(gè)，或者相當(dāng)于將4個(gè)無(wú)個(gè)無(wú)區(qū)別的球放到區(qū)別的球放到3個(gè)有標(biāo)志的盒子里。故展開(kāi)項(xiàng)個(gè)數(shù)為個(gè)有標(biāo)志的盒子里。故展開(kāi)項(xiàng)個(gè)數(shù)為 F(3,4)=C(3+4-1,4)=151.3 重復(fù)組合例8、91.3 組合組合例例 題題1.3.2 重復(fù)組合重復(fù)組合例例8、某餐廳有某餐廳有7種不同的菜，為了招種不同的菜，為了招待朋友，一個(gè)顧客需要買待朋友，一個(gè)顧客需要買14個(gè)菜，問(wèn)個(gè)菜，問(wèn)有多少種買法？有多少種買法？例例9、求求n個(gè)無(wú)區(qū)別的個(gè)無(wú)區(qū)別的球放入球放入r個(gè)有標(biāo)志的盒個(gè)有標(biāo)志的盒子里子里(nr)而無(wú)一空盒而無(wú)一空盒的方案數(shù)。的方案數(shù)。解 ：解 ： 這 個(gè)

50、問(wèn) 題 相 當(dāng) 于 重 集這 個(gè) 問(wèn) 題 相 當(dāng) 于 重 集*1,*2,*7的的14組合。根組合。根據(jù)定理?yè)?jù)定理1.6知買菜的方法數(shù)為知買菜的方法數(shù)為F(7,14)=C(7+14-1,14)=4845解：解：由于每個(gè)盒子不能為空，故每個(gè)盒子里可先放一個(gè)球，由于每個(gè)盒子不能為空，故每個(gè)盒子里可先放一個(gè)球，這樣還剩這樣還剩n-r個(gè)球，再將這個(gè)球，再將這n-r個(gè)球防到個(gè)球防到r個(gè)盒子里，由于這時(shí)個(gè)盒子里，由于這時(shí)每盒的球數(shù)不受限制，相當(dāng)于重集每盒的球數(shù)不受限制，相當(dāng)于重集*a1,*a2,*ar的的n-r組合。根據(jù)定理組合。根據(jù)定理1.6知，其組合數(shù)為知，其組合數(shù)為 F(r,n-r)=C(r+n-r-

51、1,n-r)=C(n-1,r-1)1.3 重復(fù)組合例101.3 組合組合例例 題題1.3.2 重復(fù)組合重復(fù)組合例例10、在由數(shù)在由數(shù)0,1,9組成的組成的r位整數(shù)所組成的集合中，如果將位整數(shù)所組成的集合中，如果將一個(gè)整數(shù)重新排列得到另一個(gè)整數(shù)，則稱這兩個(gè)整數(shù)是一個(gè)整數(shù)重新排列得到另一個(gè)整數(shù)，則稱這兩個(gè)整數(shù)是等價(jià)等價(jià)的。的。那么，那么，有多少不等價(jià)的整數(shù)？有多少不等價(jià)的整數(shù)？如果如果0和和9最多只能出現(xiàn)一次，又有多少不等價(jià)的整數(shù)？最多只能出現(xiàn)一次，又有多少不等價(jià)的整數(shù)？解：解：分析題意知，一個(gè)分析題意知，一個(gè)r位整數(shù)只和所取的數(shù)字有關(guān)，與其順位整數(shù)只和所取的數(shù)字有關(guān)，與其順序無(wú)關(guān)，因而是個(gè)組合問(wèn)

52、題。又每一整數(shù)的每一位可從序無(wú)關(guān)，因而是個(gè)組合問(wèn)題。又每一整數(shù)的每一位可從0,1,9中任取，故不等價(jià)的中任取，故不等價(jià)的r位整數(shù)相當(dāng)于重集位整數(shù)相當(dāng)于重集*0,*1,*9的的r組合。根據(jù)定理組合。根據(jù)定理1.6知，其組合數(shù)為知，其組合數(shù)為F(10,r)=C(10+r-1, r)=C(9+r,r) 0和和9最多只出現(xiàn)一次，可分為三種情況：均不出現(xiàn)時(shí)相當(dāng)于最多只出現(xiàn)一次，可分為三種情況：均不出現(xiàn)時(shí)相當(dāng)于重集重集B=*1,*2,*8的的r組合，組合數(shù)為組合，組合數(shù)為F(8,r)=C(r+7,r)；只出現(xiàn)其一，若只出現(xiàn)其一，若0出現(xiàn)，相當(dāng)于出現(xiàn)，相當(dāng)于B的的r-1組合，然后加入組合，然后加入0，組合，

53、組合數(shù)為數(shù)為F(8,r-1)=C(r+6,r-1)，同理，同理9出現(xiàn)的組合數(shù)為出現(xiàn)的組合數(shù)為C(r+6,r-1) ；均；均出現(xiàn)一次，相當(dāng)于出現(xiàn)一次，相當(dāng)于B的的r-2組合，然后加入組合，然后加入0,9，組合數(shù)為，組合數(shù)為F(8,r-2)=C(r+5,r-2)，由加法法則知，符合題意的整數(shù)個(gè)數(shù)為，由加法法則知，符合題意的整數(shù)個(gè)數(shù)為C(r+7,r)+2 C(r+6,r-1)+C(r+5,r-2)1.3 不相鄰組合1.3 組合（3）1.3 組合組合定義定義 1.71.3.3 不相鄰組合不相鄰組合定理定理 1.8從序列從序列A=1,2,n個(gè)中選取個(gè)中選取r個(gè)，其個(gè)，其中不存在中不存在i,i+1兩個(gè)相鄰

54、的數(shù)同時(shí)出現(xiàn)兩個(gè)相鄰的數(shù)同時(shí)出現(xiàn)于一個(gè)組合的組合。于一個(gè)組合的組合。從序列從序列A=1,2,n個(gè)中選取個(gè)中選取r個(gè)作不相個(gè)作不相鄰的組合，其組合數(shù)為鄰的組合，其組合數(shù)為C(n-r+1, r)證明：證明：設(shè)設(shè)d1,d2,dr是所求的一個(gè)不相鄰組合，不妨設(shè)是所求的一個(gè)不相鄰組合，不妨設(shè)d1d2dr。令。令ci=di-i+1(i=1,2,r)，即，即c1=d1,c2=d2-1,cr=dr-r+1。因因1din，故，故1cin-r+1，得到一個(gè)集合，得到一個(gè)集合1,2,n-r+1的的r組組合。顯然有一種合。顯然有一種d1,d2,dr的取法，就有一種的取法，就有一種c1,c2,cr的取法。的取法。反之亦

55、然，集合反之亦然，集合1,2,n-r+1的一個(gè)的一個(gè)r組合組合c1,c2,cr，不妨設(shè)，不妨設(shè)c1c2cr。令。令di=ci+i-1(i=1,2,r)，即，即d1=c1,d2=c2 +1,dr=cr+r-1。因。因1cin-r+1，故，故1din，得到一個(gè)集合，得到一個(gè)集合1,2,n的不的不相鄰組合相鄰組合d1,d2,dr 。顯然有一種。顯然有一種c1,c2,cr的取法，就有一種的取法，就有一種d1,d2,dr的取法。的取法。故這兩種取法是故這兩種取法是一一對(duì)應(yīng)的一一對(duì)應(yīng)的，從而這兩種取法是，從而這兩種取法是等價(jià)的等價(jià)的。從。從n個(gè)個(gè)不同元素中可選取不同元素中可選取r個(gè)的不相鄰組合數(shù)，和從個(gè)的

56、不相鄰組合數(shù)，和從n-r+1個(gè)不同元素中個(gè)不同元素中選取選取r個(gè)的組合數(shù)是相同的，即個(gè)的組合數(shù)是相同的，即C(n-r+1, r)。1.4 二項(xiàng)式定理1.4 二項(xiàng)式定理二項(xiàng)式定理定理定理 1.9 0,()nnkn kknnNx yRxyx yk如如有有證明：證明：因?yàn)橐驗(yàn)?x+y)n=(x+y)(x+y)(x+y)，等式右端有，等式右端有n個(gè)因子，項(xiàng)個(gè)因子，項(xiàng)xkyn-k是從這是從這n個(gè)因子中選取個(gè)因子中選取k個(gè)因子，個(gè)因子，k=0,1,n。在這。在這k個(gè)個(gè)(x+y)里都取里都取x，而從剩下的，而從剩下的n-k個(gè)因子個(gè)因子(x+y)中選取中選取y作乘積得到，因此作乘積得到，因此xkyn-k的系數(shù)

57、為上述選法的個(gè)數(shù)的系數(shù)為上述選法的個(gè)數(shù)C(n,r)。故有。故有證畢。證畢。注：可用數(shù)學(xué)歸納法證明，證明略；注：可用數(shù)學(xué)歸納法證明，證明略； C(n, k)又稱又稱二項(xiàng)式系數(shù)二項(xiàng)式系數(shù)。 0()nnkn kknxyx yk1.4 二項(xiàng)式定理推論11.4 二項(xiàng)式定理二項(xiàng)式定理四個(gè)推論四個(gè)推論推論推論1.9.1：推論推論1.9.2：推論推論1.9.3： 000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyxyknk如如有有 00,(1)nnnkkkknnnNxRxxxknk 如如有有 0,2nnknnNk如如有有證明：證明：在推論在推論1.9.2中令中令x=1，即可

58、得證。，即可得證。利用組合分析，等式左端相當(dāng)于從利用組合分析，等式左端相當(dāng)于從A=an中任意選擇中任意選擇k(0kn)個(gè)個(gè)元素的所有可能數(shù)目，即對(duì)元素的所有可能數(shù)目，即對(duì)n個(gè)元素，每一個(gè)都有被選擇和不被個(gè)元素，每一個(gè)都有被選擇和不被選擇的可能，總的可能數(shù)為選擇的可能，總的可能數(shù)為2n。另外，該等式還表明另外，該等式還表明A的所有子集個(gè)數(shù)為的所有子集個(gè)數(shù)為2n。1.4 二項(xiàng)式定理推論21.4 二項(xiàng)式定理二項(xiàng)式定理四個(gè)推論四個(gè)推論推論推論1.9.1：推論推論1.9.2：推論推論1.9.3：推論推論1.9.4： 000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyx

59、yknk如如有有 00,(1)nnnkkkknnnNxRxxxknk 如如有有 0,2nnknnNk如如有有 0,( 1)0nkknnNk如如有有證明：證明：在推論在推論1.9.2中令中令x=-1，即可得證。，即可得證。另外，該等式還表明另外，該等式還表明A=an的偶數(shù)子集個(gè)數(shù)和奇數(shù)子集個(gè)數(shù)相等。的偶數(shù)子集個(gè)數(shù)和奇數(shù)子集個(gè)數(shù)相等。1.4 廣義二項(xiàng)式定理1.4 二項(xiàng)式定理二項(xiàng)式定理定理定理 1.10定義定義 1.8 ( , ),(1).(1)/!01000CkRkZkkkkkk 廣義廣義二項(xiàng)式系數(shù)二項(xiàng)式系數(shù) 為：為： kkkR x yxyx yk0,|1,() 如如有有牛頓二項(xiàng)式定理：牛頓二項(xiàng)式

60、定理：1.4 廣義二項(xiàng)式定理推論11.4 二項(xiàng)式定理二項(xiàng)式定理六個(gè)推論六個(gè)推論推論推論1.10.1：推論推論1.10.2： kkzzzk0| |1,(1) 有有nkkknkzzzk01| |1,(1)( 1)有有證明：證明：0000(1).(1)(1)!( 1)(1).(1)!1( 1)nkkkkkkkkkknnnknzzzkkn nnkzknkzk 1.4 廣義二項(xiàng)式定理推論21.4 二項(xiàng)式定理二項(xiàng)式定理六個(gè)推論六個(gè)推論推論推論1.10.1：推論推論1.10.2：推論推論1.10.3：推論推論1.10.4：推論推論1.10.5： kkzzzk0| |1,(1) 有有nkkknkzzzk01|