組合數(shù)學(xué)CH11,12

1、組合數(shù)學(xué)組合數(shù)學(xué)主講人:高巧琴I(mǎi)n our classes,all the mobile phones should be switched off !The class is begin!課程簡(jiǎn)介課程簡(jiǎn)介相關(guān)課程相關(guān)課程數(shù)學(xué)分析數(shù)學(xué)分析高等代數(shù)高等代數(shù)離散數(shù)學(xué)離散數(shù)學(xué) 本課程針對(duì)計(jì)算機(jī)科學(xué)中的一個(gè)重要學(xué)科組合數(shù)學(xué)，組合數(shù)學(xué)是數(shù)學(xué)的一個(gè)分支，它研究事物在結(jié)定模式下的配置，研究這種配置的存在性，所有可能配置的計(jì)數(shù)和分類(lèi)以及配置的各種性質(zhì)。組合數(shù)學(xué)在計(jì)算機(jī)科學(xué)中有著極其廣泛的應(yīng)用。 組合學(xué)問(wèn)題求解方法層出不窮、千變?nèi)f化，應(yīng)以理解為基礎(chǔ)，善于總結(jié)各種技巧，掌握科學(xué)的組織和推理方法。參考教材參考教材:

2、l孫世新編,組合數(shù)學(xué),電子科技大學(xué)出版;社,2006年l孫淑玲編,組合數(shù)學(xué),(第三版)中國(guó)科學(xué)技術(shù)大學(xué)出版社,2012年;l盧開(kāi)澄,盧華明編,組合數(shù)學(xué),清華大學(xué)出版社,2002年;lRichard A.Brualdi著,馮速等譯,組合數(shù)學(xué)(第五版),機(jī)械工業(yè)出版社,2012年. 現(xiàn)代數(shù)學(xué)可以分為兩大類(lèi)：一類(lèi)是研究連續(xù)對(duì)象的，如分析、方程等；另一類(lèi)就是研究離散對(duì)象的組合數(shù)學(xué)。 計(jì)算機(jī)出現(xiàn)以后，由于離散對(duì)象的處理是計(jì)算機(jī)科學(xué)的核心，研究離散對(duì)象的組合數(shù)學(xué)得到迅猛發(fā)展。 它能夠運(yùn)用到很多學(xué)科，而之前這些學(xué)科與數(shù)學(xué)幾乎沒(méi)有關(guān)聯(lián)。組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematic

3、s)院士指出，每個(gè)時(shí)代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個(gè)新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個(gè)新的分支也是在時(shí)代的要求下產(chǎn)生的。 最近,院士又指出，信息技術(shù)很可能會(huì)給數(shù)學(xué)本身帶來(lái)一場(chǎng)根本性的變革，而組合數(shù)學(xué)則將顯示出它的重要作用。 組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)教授曾提出要向中國(guó)領(lǐng)導(dǎo)人呼吁，組合數(shù)學(xué)是計(jì)算機(jī)軟件產(chǎn)業(yè)的基礎(chǔ)，中國(guó)最終一定能成為一個(gè)軟件大國(guó)，但是要實(shí)現(xiàn)這個(gè)目標(biāo)的一個(gè)突破點(diǎn)就是發(fā)展組合數(shù)學(xué)。同志在1998年接見(jiàn)“五四”青年獎(jiǎng)?wù)聲r(shí)發(fā)表的講話中指出，組合數(shù)學(xué)不同于傳統(tǒng)的純數(shù)學(xué)的一個(gè)分支，它還是一門(mén)應(yīng)用學(xué)科，一門(mén)交叉學(xué)科。他希望中國(guó)的組

4、合數(shù)學(xué)研究能夠?yàn)閲?guó)家的經(jīng)濟(jì)建設(shè)服務(wù)。 組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics) 另一方面，我們?cè)谌粘Ｉ钪形覀兂３Ｓ龅浇M合數(shù)學(xué)的問(wèn)題。：如果你仔細(xì)留心一張世界地圖，你會(huì)發(fā)現(xiàn)用一種顏色對(duì)一個(gè)國(guó)家著色，那么一共只需要四種顏色就能保證每?jī)蓚€(gè)相鄰的國(guó)家的顏色不同。這樣的著色效果能使每一個(gè)國(guó)家都能清楚地顯示出來(lái)。但要證明這個(gè)結(jié)論確是一個(gè)著名的世界難題，最終借助計(jì)算機(jī)才得以解決，最近人們才發(fā)現(xiàn)了一個(gè)更簡(jiǎn)單的證明。 ：組合數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。 1977年美國(guó)旅行者1號(hào)、2號(hào)宇宙飛

5、船就帶上了幻方以作為人類(lèi)智慧的信號(hào)。神 農(nóng) 幻 方4923578162200BC 1 15 14 412 6 7 9 8 10 11 513 3 2 16 15世紀(jì) 階 幻 方組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)：給定來(lái)自6種軍銜和6個(gè)軍團(tuán)的36名軍官，能不能把他們排成一個(gè)66編隊(duì)，使得每一行上和每一列上都滿(mǎn)足每個(gè)軍銜有一名軍官且每個(gè)軍團(tuán)有一名軍官呢？ 這個(gè)問(wèn)題是18世紀(jì)由瑞典數(shù)學(xué)家L.Euler提出的一個(gè)數(shù)學(xué)娛樂(lè)問(wèn)題，它對(duì)統(tǒng)計(jì)學(xué)特別是試驗(yàn)設(shè)計(jì)等產(chǎn)生重要的影響。組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics) 對(duì)于城市的交

6、通管理，交通規(guī)劃，哪些地方可能是阻塞要地，哪些地方 應(yīng)該設(shè)單行道，立交橋建在哪里最合適，紅綠燈怎樣設(shè)定最合理， 如此等等，全是組合數(shù)學(xué)的問(wèn)題。 組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)：一個(gè)通訊網(wǎng)絡(luò)怎樣布局最節(jié)??？美國(guó)的貝爾實(shí)驗(yàn)室和IBM公司都有世界一流的組合數(shù)學(xué)家在研究這個(gè)問(wèn)題，這個(gè)問(wèn)題直接關(guān)系到巨大的經(jīng)濟(jì)利益。 是一種兩人玩的游戲，玩家雙方對(duì)一堆硬幣。假設(shè)k堆硬幣，每堆分別為n1,n2,nk枚硬幣。這一游戲的目標(biāo)目標(biāo)就是取得最后一枚硬幣。游戲規(guī)則如下： 1）玩家輪番出場(chǎng)； 2）當(dāng)輪到一個(gè)玩家取子時(shí)，他們都要從選擇的硬幣堆中至少取走一枚硬幣；（這位玩家可

7、以把所選硬幣堆都取走，于是剩下一個(gè)空堆，這時(shí)它“退出”）當(dāng)所有的硬幣堆都空了的時(shí)候，游戲結(jié)束。走最后一步的玩家，即取走最后一枚硬幣的玩家獲勝獲勝。 組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics) 總之，組合數(shù)學(xué)無(wú)處不在，它的主要應(yīng)用就是在各種復(fù)雜關(guān)系中找出最優(yōu)的方案。所以組合數(shù)學(xué)完全可以看成是一門(mén)量化的關(guān)系學(xué)關(guān)系學(xué)，一門(mén)量化了的運(yùn)籌學(xué)運(yùn)籌學(xué)，一門(mén)量化了的管理學(xué)管理學(xué)。 組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics) T存在性問(wèn)題:符合要求的安排是否存在？

8、符合要求的安排是否存在？T計(jì)數(shù)問(wèn)題:如有，這種安排有多少種？如有，這種安排有多少種？T構(gòu)造問(wèn)題:怎樣作出這些安排？怎樣作出這些安排？T優(yōu)化問(wèn)題:當(dāng)有衡量這種安排的優(yōu)劣的標(biāo)準(zhǔn)當(dāng)有衡量這種安排的優(yōu)劣的標(biāo)準(zhǔn)時(shí)，怎樣求出最優(yōu)安排？時(shí)，怎樣求出最優(yōu)安排？一、組合數(shù)學(xué)研究什么組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)二、組合數(shù)學(xué)的主要內(nèi)容引言引言第第1章章 排列與組合排列與組合 1.1 加法法則和乘法法則 1.2 排列 1.3 組合 1.4 二項(xiàng)式定理 1.5 組合恒等式及其含義 本章小結(jié)第第2章章 鴿籠原理與鴿籠原理與容斥原容斥原理理 2.1 鴿籠原理 2.2 容斥原

9、理及其應(yīng)用本章小結(jié) 第第3章章 母函數(shù)母函數(shù) 3.1 母函數(shù)的基本概念 3.2 母函數(shù)的基本運(yùn)算 3.3 在排列組合中的應(yīng)用 3.4 整數(shù)的拆分 本章小結(jié) 習(xí)題第第4章章 遞推關(guān)系遞推關(guān)系 4.1 遞推關(guān)系的建立 4.2 常系數(shù)線性齊次遞推關(guān)系 4.3 常系數(shù)線性非齊次遞推關(guān)系 4.4 迭代法與歸納法 4.5 母函數(shù)在遞推關(guān)系中的應(yīng)用本章小結(jié) 目目 錄錄 本課程主要內(nèi)容為組合數(shù)學(xué)，是一門(mén)理論性較強(qiáng)，應(yīng)用性較廣的課程。因此，通過(guò)本課程的學(xué)習(xí)，使學(xué)生熟悉組合計(jì)算方法的基本原理和基本方法，掌握常見(jiàn)組合計(jì)算的方法，能把一種較難的組合計(jì)數(shù)問(wèn)題轉(zhuǎn)化為一個(gè)較易的組合問(wèn)題，進(jìn)一步提高組合計(jì)算能力。運(yùn)用組合數(shù)學(xué)

10、的思想和方法，培養(yǎng)分析問(wèn)題和解決問(wèn)題的能力。組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics)三、開(kāi)課目的和要求三、開(kāi)課目的和要求四、計(jì)劃及注意點(diǎn)四、計(jì)劃及注意點(diǎn) 把好入門(mén)關(guān)，牢固掌握基本原理與方法，反復(fù)思考，認(rèn)真體會(huì)。解題需要智慧和靈感。組合數(shù)學(xué)源于實(shí)踐用于實(shí)踐。 共32課時(shí)，第一四章組合數(shù)學(xué)概述組合數(shù)學(xué)概述(Combinatorial mathematics) 本章重點(diǎn)介紹以下的基本計(jì)數(shù)方法：本章重點(diǎn)介紹以下的基本計(jì)數(shù)方法： 加法法則和乘法法則加法法則和乘法法則 排列排列 組合組合 二項(xiàng)式定理的應(yīng)用二項(xiàng)式定理的應(yīng)用 組合恒等式組合恒等式 相互獨(dú)立相互獨(dú)立的事件的

11、事件 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 換言之：若集合S可以分解成互不相交的子集1,S之和，則確定S中的事物個(gè)數(shù)，可以先求出各子集個(gè)數(shù)，然后相加。2,mSSiS中的事物1.1

12、 加法法則例11.1 加法法則和乘法法則加法法則和乘法法則1.1.1 加法法則加法法則例例 題題例例1、有一所學(xué)校給一名數(shù)學(xué)競(jìng)賽優(yōu)勝有一所學(xué)校給一名數(shù)學(xué)競(jìng)賽優(yōu)勝者發(fā)獎(jiǎng)，獎(jiǎng)品有三類(lèi)，第一類(lèi)是三種者發(fā)獎(jiǎng)，獎(jiǎng)品有三類(lèi)，第一類(lèi)是三種不同版本的法漢詞典；第二類(lèi)是四種不同版本的法漢詞典；第二類(lèi)是四種不同類(lèi)型的數(shù)學(xué)參考書(shū)；第三類(lèi)是二不同類(lèi)型的數(shù)學(xué)參考書(shū)；第三類(lèi)是二種不同的獎(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類(lèi)獎(jiǎng)品的集合

13、類(lèi)獎(jiǎng)品的集合(i=1,2,3)，顯然，顯然，SiSj= (ij) ，根據(jù)加法法則有，根據(jù)加法法則有iiSSSSS31231| | | |3429 注：注：運(yùn)用加法法則的技巧是把集合運(yùn)用加法法則的技巧是把集合S劃分成劃分成的部分。的部分。 若若|A|=k，|B|=l ，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 種。種

14、。集合論定義集合論定義 設(shè)設(shè) 是有限集合，且是有限集合，且 ，則有，則有 。11mmiiiiSSS 1miiSS (1,2,.,)iS im 12(,.,)|,1,2,.,miia aaaS im 換言之：若集合S是集合1,S2,mSS的事物個(gè)數(shù)，可以先求出各個(gè)集合的直積，則確定S中iS中的事物個(gè)數(shù)，然后相乘。Si1.1 乘法法則例51.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則例例 題題例例2 由數(shù)字由數(shù)字1,2,3,4,5可以構(gòu)成多少個(gè)所可以構(gòu)成多少個(gè)所有數(shù)字互不相同的四位偶數(shù)？有數(shù)字互不相同的四位偶數(shù)？解：解：所求的是四位偶數(shù)，故個(gè)位只能選所求的是四位偶數(shù)，故個(gè)

15、位只能選2或或4，有兩種選，有兩種選擇方法；又由于要求四位數(shù)字互不相同，故個(gè)位選中后，擇方法；又由于要求四位數(shù)字互不相同，故個(gè)位選中后，十位只有四種選擇方法；同理，百位、千位分別有三種、十位只有四種選擇方法；同理，百位、千位分別有三種、兩種選擇方法，根據(jù)乘法法則，四位數(shù)互不相同的偶數(shù)兩種選擇方法，根據(jù)乘法法則，四位數(shù)互不相同的偶數(shù)個(gè)數(shù)為個(gè)數(shù)為2 4 3 2=481.1 乘法法則例61.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則例例 題題例例3 求出從求出從8個(gè)計(jì)算機(jī)系的學(xué)生、個(gè)計(jì)算機(jī)系的學(xué)生、 9個(gè)個(gè)數(shù)學(xué)系的學(xué)生和數(shù)學(xué)系的學(xué)生和10個(gè)經(jīng)濟(jì)系的學(xué)生中個(gè)經(jīng)濟(jì)系的學(xué)生中選出

16、兩個(gè)不同專(zhuān)業(yè)的學(xué)生的方法數(shù)。選出兩個(gè)不同專(zhuān)業(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=2421、計(jì)算事物的有序安排或有序選擇數(shù)。這又分為兩種情況：（1）不允許任何事物重復(fù)；（2）允許事物重復(fù)。2、計(jì)算事物的無(wú)序安排或無(wú)序選擇數(shù)。這又分為兩種情況：（1）不允許任何事物重復(fù)

17、；（2）允許事物重復(fù)。 這是屬于排列問(wèn)題. 這是屬這是屬于組合問(wèn)于組合問(wèn)題題在實(shí)際中，大量的計(jì)數(shù)問(wèn)題分為兩大類(lèi)： 1.1 加法法則和乘法法則加法法則和乘法法則一、線排列一、線排列設(shè)集合12,nAa aa是具有n個(gè)元素的集合，r是正整數(shù)注意：!,(1)(1)()!nrnPP n rn nnrnr 則集合A的r-排列為當(dāng)r n時(shí)，則稱(chēng)A的n-排列為全排列，即,!.nnPP n nn,(1,1);,(1,1)(1, ).P n rnP nrP n rrP nrP nr2nr當(dāng)時(shí)，二、二、圓圓排列排列三、重排列三、重排列1.2 排列排列二、二、圓圓排列排列 例1 由數(shù)字1,2,3,4,5,6可以構(gòu)成多

18、少個(gè)數(shù)字互不相同的四位數(shù). 例2 將具有9個(gè)字母的單詞FRAGMENTS進(jìn)行排列,要求A總是緊跟在字母R的右邊,問(wèn)有多少種這樣的排法.設(shè)集合(6,4)360; (8,8)8!40320.PP是具有n個(gè)元素的集合，r是正整數(shù),!()!P n rnMrr nr則集合A的r-圓排列為注意：把一個(gè)圓排列旋轉(zhuǎn)可得到另一個(gè)圓排列，這兩個(gè)圓排列是相同的。 12,nAa aa答案：1.2 排列排列 例例3 排列26個(gè)字母，使得在a和b之間正好有7個(gè)字母，問(wèn)有多少種方法？分析分析（1）將a和b之間的7個(gè)字母作排列有P(24,7)； （2） a和b又有兩種排法，由乘法原理得以a和b為端點(diǎn)的9個(gè)字母的排列有2P(2

19、4，7); （3）把一個(gè)排列看成一個(gè)整體再與剩下的17個(gè)字母進(jìn)行全排列有18！； （4）由乘法原理，所求的排列數(shù)為2 (24,7) 18!36 24!.NP 例例4 假定有8位成員,兩兩配對(duì)分成4組,試問(wèn)有多少種方案N?7 5 3105N 86424!1052222N 1.2 排列排列 例5 有8人圍圓桌就餐，問(wèn)有多少種就坐方式？如果有兩人不愿坐在一起，又有多少種就坐方式？若8人是4男4女并交替就坐，又有多少種就坐方式？分析：這顯然都是圓排列問(wèn)題。8!7!;7! 2 6!3600;(4! 4) 4 3 2 1144.8 答案：1.2 排列排列 例6 用20個(gè)不同顏色的念珠串成一條項(xiàng)鏈，能做成多

20、少不同的項(xiàng)鏈？分析：這顯然都是圓排列問(wèn)題。20!19!;20答案：19!/ 2.又因?yàn)轫?xiàng)鏈還可以翻轉(zhuǎn)過(guò)來(lái)而念珠的排列未改動(dòng)，因此項(xiàng)鏈的總數(shù)是1.2 排列排列定義定義 1.3三、三、 重排列重排列集合論定義集合論定義定理定理 1.1從從n個(gè)不同元素中，可重復(fù)選取個(gè)不同元素中，可重復(fù)選取r個(gè)按個(gè)按一定順序排列起來(lái)，稱(chēng)為重排列。一定順序排列起來(lái)，稱(chēng)為重排列。從重集從重集B=k1b1, k2b2, , knbn中選中選取取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í)可從排列如下

21、：選擇第一項(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。證畢。證畢?？紤]在重集中選r個(gè)元素1122,nnBk b kbkb進(jìn)行的排列。1.2 重排列例61.2 排列排列例例 題題三、三、 重排列重排列例例7 由數(shù)字由數(shù)字1,2,3,4,5,6這六個(gè)數(shù)字能這六個(gè)數(shù)字能組成多少個(gè)五位數(shù)？又可組成多少組成多少個(gè)五位數(shù)？又可組成多少大于大于34500的五位數(shù)？的五

22、位數(shù)？解：解：一個(gè)五位數(shù)的各位數(shù)字可重復(fù)出現(xiàn)，是一個(gè)典型的一個(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排列，由乘法法則知，共有排列，由乘法

23、法則知，共有2 63個(gè)五位數(shù)；個(gè)五位數(shù)；萬(wàn)位是萬(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重集重集B=n1b1,n2b2,nkbk的全排列的全排列個(gè)數(shù)為個(gè)數(shù)為112!,! .!kiiknnnnnn其其中中證明：證明：將將B中的中的ni個(gè)個(gè)bi看作不同的看作不同的

24、ni個(gè)元素，賦予上標(biāo)個(gè)元素，賦予上標(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,., )

25、iniiib bbik 12121212111222,.,.,.,.,knnnkkkAb bbb bbb bb 112! .!kiiknnnnnn其其中中1.2 重排列例71.2 排列排列三、三、 重排列重排列例例 題題例例8 有四面紅旗，三面藍(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.2 重排列例81.2 排列排列三、三、 重排列重排列例例 題題例例9 用字母用字母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次，