離散數(shù)學及其應用-第2版 課件 第6章計數(shù)

第6章

計數(shù)第6章計數(shù)6.1基本計數(shù)規(guī)則6.2排列于組合6.3容斥原理6.1基本計數(shù)規(guī)則6.1.1加法法則6.1.2乘法法則6.1.1加法法則加法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，當A與B產(chǎn)生的方式不重疊時，“事件A或B”有m+n種產(chǎn)生方式。加法法則使用的條件是事件A與B產(chǎn)生的方式不能重疊。加法法則的推廣：設A1，A2，…，An是n個事件，它們的產(chǎn)生方式分別有P1，P2，…，Pn，當其中任何兩個事件產(chǎn)生的方式都不重疊時，事件“A1或A2或…或An”有P1＋P2＋…＋Pn種產(chǎn)生的方式。例題例6.1.1在下面的程序代碼段被執(zhí)行后，k的值是多少？k:=0fori1:=1ton1k:=k+1fori2:=1ton2k:=k+1forim:=1tonmk:=k+1

解：k的值是n1

+n2

+…+nm。

6.1.2乘法法則乘法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，當A與B產(chǎn)生的方式彼此獨立時，“事件A與B”有mn種產(chǎn)生方式。乘法法則使用的條件是事件A與B產(chǎn)生的方式彼此獨立，即，事件A對產(chǎn)生方式的選擇不影響事件B對產(chǎn)生方式的選擇，反之也對。乘法法則的推廣：設A1，A2，…，An是n個事件，它們的產(chǎn)生方式分別有P1，P2，…，Pn種，當其中任何兩個事件產(chǎn)生的方式都彼此獨立時，事件“A1與A2與…與An”有P1P2…Pn種產(chǎn)生的方式。例題例6.1.2設A為n元集合，B為m元集合，回答下列問題：A上的函數(shù)有多少個？其中雙射函數(shù)有多少個？A到B的函數(shù)有多少個？其中有多少個一對一函數(shù)？A上的自反關系有多少個？A上的對稱關系有多少個？例題（續(xù)）解（1）A上有nn個不同的函數(shù)，可以構成n(n-1)(n-2)…1=n!個雙射函數(shù)。（2）有

mn個A到B的函數(shù).

當n>m時，不存在A到B的一對一函數(shù)。當n<=m時，A到B的一對一函數(shù)有

個。（3）自反關系有

個。（4）有個對稱矩陣。IP地址編碼方案

08162432A類0網(wǎng)絡地址（7位）主機地址（24位）B類10網(wǎng)絡地址（14位）主機地址（16位）C類110網(wǎng)絡地址（21位）主機地址（8位）D類1110組播地址（28位）E類11110保留地址A、B、C

三類在全球范圍內統(tǒng)一分配，D類地址用于在IP網(wǎng)絡中的組播，E類地址保留作研究之用。例題例6.1.3TCP/IP網(wǎng)絡中，A類地址中，全0和全1不做網(wǎng)絡地址，A、B、C三類地址中全0和全1都不作為主機地址。在Internet中有多少個可統(tǒng)一分配的有效的IP地址？解在Internet中有可統(tǒng)一分配的有效的IP地址為A、B、C三類地址，令這三類地址總數(shù)為N，A類、B類、C類的有效IP地址數(shù)分別為NA、NB、NC。由加法法則，N=NA+NB+NC。令Wi和Ci(i

{A,B,C})表示每類地址的網(wǎng)絡地址數(shù)和主機地址數(shù)，由乘法法則，Ni=Wi

Ci(i

{A,B,C})。

例題（續(xù)）A類地址中，全0和全1不做網(wǎng)絡地址，故網(wǎng)絡地址有

個，對每個網(wǎng)絡地址有

個主機地址，因而，

。B類地址，有

個網(wǎng)絡地址，對每個網(wǎng)絡標識有

個主機地址，

。C類地址，有

個網(wǎng)絡地址，對每個網(wǎng)絡標識有

個主機地址，

。在A類、B類和C類地址中，全0和全1都不作為主機標識，主機標識數(shù)需減2。因此N=NA+NB+NC=3720364628。6.2排列與組合6.2.1排列6.2.2組合6.2.3多重集的排列于組合6.2.4二項式定理6.2.1排列

定義6.2.1從n元集S中有序、不重復選取的r個元素稱為S的一個-排列，S的所有-排列的個數(shù)記作P（n，r）。

定理6.2.1設n，r為自然數(shù)，具有n個不同元素的集合S的-排列為特別地，當r＝n時，稱排列為S的全排列，有

定理6.2.1證明證明首先選擇排列中的第一個元素，有n種選擇的方式。然后選擇排列的第二個元素，它只能取自剩下的n－1個元素，有n－1種選法。以此類推，選擇第三個元素，第四個元素，……，第r個元素的方式數(shù)依次為n－2，n－3，…，n－r＋1。根據(jù)乘法法則，總的選法數(shù)為容易看出全排列數(shù)P（n，n）=n！。例題例6.2.1假定有10個運動員參加長跑比賽，第一、二、三名分別得到金、銀、銅牌（假定沒有并列名次出現(xiàn)）。如果比賽可能出現(xiàn)所有可能的結果，那么求頒獎的方式有幾種？解頒獎方式就是10元集的3-排列數(shù)。因此存在P（10，3）=10*9*8=720種可能的頒獎方式。例題例6.1.2m個男孩，n個女孩排成一排，如果女孩不相鄰，有多少種方法？解先排好男孩，這對應于m元集合的全排列問題，有m！種方法。為使得女孩不相鄰，將男孩看作格子分界，將女孩放入格子中間，m個男孩構成了m十1個格子（包含男孩的全排列之外的頭尾兩個位置在內），從中選出n個放入女孩，選法數(shù)是P（m＋1，n）。根據(jù)乘法法則所求的方法數(shù)是m！P（m＋1，n）。例題例6.2.1有一個快遞員要給n個學校派送快遞。假定他必須從指定的某個學校開始，但對其他n-1個學校的派送順序可以按照他想要的任何次序進行。他派送完所有這些學校時，可以有多少種可能的次序？解由于第一個學校是確定的，所以他派送完所有學校的路徑數(shù)是n-1個元素的全排列數(shù)，因此，快遞員有（n-1）!種可能的派送次序。比如當n=8時，共有7！=5040種派送次序，如果要從中找出具有最短距離的路徑，并計算每一條可能路徑的總距離，則要計算5040條路徑。6.2.2組合定義6.2.2從n元集S中無序、不重復選取的r個元素稱為S的一個r-組合，S的所有r-組合的個數(shù)記作C（n，r）。下面的定理是關于C（n，r）的公式。定理6.2.2設n，r為自然數(shù)，

則定理6.2.2證明證明

首先無序地選出r個元素，然后再構造這r個元素的全排列。無序選擇r個元素的方法數(shù)是C（n，r），針對每種選法，能構造P（r，r）=r！個不同的全排列，根據(jù)乘法法則，不同的r-排列數(shù)滿足P（n，r）＝C（n，r）P（r，r）=C（n，r）r！所以

規(guī)定，當

時，C（n，r）=0。推論1推論1

設n，r為正整數(shù)，

，則

。證明左邊=C（n，r）

右邊

因此左邊=右邊，得證。對于一個n元素集合的r-組合數(shù)也有另一種常用的記號，即C（n，r）可寫為

。

這個數(shù)也叫做二項式系數(shù)。推論2推論2

帕斯卡恒等式。設n，r為正整數(shù)，

，則證明利用定理6.2.2得

例題有多少種方式從8個選手的網(wǎng)球隊中選出4個選手外出參加在另一個學校舉行的網(wǎng)球比賽？解根據(jù)定理6.2.2，8個元素集合的一個4-組合是例題從1～300中任取3個數(shù)使得其和能被3整除有多少種方法？解

一個整數(shù)除以3的余數(shù)的可能取值有三個，分別是0,1和2，當一個整數(shù)除以3的余數(shù)為0時，這個整數(shù)可以被3整除。當幾個不能被3整除的整數(shù)除以3的余數(shù)之和為3的倍數(shù)，這幾個數(shù)之和可以被3整除。將1～300中除以3的余數(shù)相同的整數(shù)放在同一個集合，可以得到三個集合，令這三個集合為：

A＝{1，4，…，298}B＝{2，5，…，299}C＝{3，6，…，300}根據(jù)問題的要求，從1～300中任取3個數(shù)使得其和能被3整除的方法可分成以下2類：在A，B，C三個集合中的任意一個集合中任取3個數(shù)，它們之和都能被3整除。在一個集合中任取3個數(shù)，有

種選取方法，根據(jù)加法法則，在三個集合上共有3C(100，3)種選取方法。分別在A，B，C三個集合中各取1個數(shù)，它們除以3的余數(shù)之和為3，這三個數(shù)之和能被3整除。在A，B，C三個集合中各取1個數(shù)，根據(jù)乘法法則共有

種取法。根據(jù)加法法則，總選法數(shù)N＝3C(100，3)＋1003＝14851006.2.3多重集的排列與組合定理6.2.3具有n個元素的集合允許重復的r-排列數(shù)是nr。證明當允許重復時，在r-排列中對r個位置的每一個位置可以取n個元素中的任何一個，根據(jù)乘法法則，當允許重復時有nr個r-排列。例題用英文字母可以構成多少個長度為r的字符串？解

因為有26個英文字母，且每個字母可以被重復使用，由乘法法則可知可以構成26r個長度為r的字符串。定理定理6.2.4具有n個元素的集合允許重復的r-組合數(shù)是C（n+r-1，r）。證明

當允許重復時，n個元素的集合的每個r-組合可以用r個1和n-1個0的序列來表示。這里的0用來分隔r個1，n-1個0將r個1分隔成n段，每段對應集合的一個元素，每段中的1的個數(shù)表示這個元素在r-組合中出現(xiàn)的次數(shù)。例題例6.2.7從盛有蘋果、梨子和橙子的果盆里取4個水果，如果取水果的順序無關，且只關心水果的類型而不管取的是該類型的哪一個水果，且假設每種水果至少有4個，問取4個水果有多少種取法？解

這是3個元素集合的允許重復的4-組合問題。根據(jù)定理6.2.4，有C(3+4-1,4)=15種取法。不重復和允許重復的排列與組合類型是否允許重復公式r-排列不r-組合不r-排列是r-組合是6.2.4二項式定理定理6.2.5（二項式定理）設n是正整數(shù)，對一切x和y，有例題

的展開式是什么？=例題求在

的展開式x12y13的系數(shù)。解由二項式定理令i＝13得到展開式中x12y13的系數(shù)，即6.3容斥原理定理6.3.1（容斥原理）設,,,

是有窮集。那么例題例6.3.1對于4個集合的并集中的元素數(shù)給出一個公式。解應用容斥原理例題求不超過120的素數(shù)個數(shù)。解因為112＝121，不超過120的合數(shù)至少含有2，3，5或者7這幾個素因子之一。先求在1～120之間不能被2，3，5或7整除的整數(shù)。由于2，3，5，7