1、第七章第七章 組合數學組合數學v組合數學的兩個重要問題：組合數學的兩個重要問題：計數、枚舉v在計算機科學中的應用：在計算機科學中的應用：算法的時間復雜性分析、密碼學、IP地址某些算法7.1基本的計數原則基本的計數原則v 加法原理加法原理：完成一個任務有兩類方式，分別各有m和n種方法，則完成該任務的方法數是m+n A1A2=A1+A2（A1A2=）v 加法原理可推廣到多類方式或多個集合的情況v 注意加法原理中，各類方式或各個集合之間的不交要求v 乘法原理乘法原理：一個任務的實施可以分解為兩個獨立的步驟，分別各有m和n種方法，則完成該任務的方法數是m*n A1A2=A1*A2v 例例8 計數函數。

2、從一個n元集到一個m元集存在多少個函數？ 解 一個函數對于定義域中m個元素中的每個元素都要選擇倍域中n個元素中的一個元素來對應。因此，由乘積法則存在n*n*n= nm個從m元集到n元集的函數。v 例例9 一對一函數。 從一個m元素集合到一個n元素集合存在多少個一對一函數？ 解 首先注意到當mn時沒有從m元集到n元集的一對一函數。現在令mn。假設定義域中的元素是a1 ,a2 , ,am。有n種方式選擇函數在a1的值。因為函數是一對一的，可以有n-1種方式選擇函數在a2的值。一般地，有n-k+1種方式選擇函數在ak的值。由乘積法則，從一個m元素集合到一個n元素集合存在著n(n-1)(n-2)（n-

3、m+1）個一對一函數。v 例例10 IP地址的計算地址的計算 因特網上的計算機有多少不同的有效IPv4地址？ 解 令X是因特網上計算機的有效地址數，XA , XB 和XC 分別表示A類、B類和C類的有效地址數。由求和法則，X= XA + XB + XC。（接下頁）（接上頁） 為了找到XA , 由于1111111是無效的，故存在27 -1=127個A類的網絡標識。對于每個網絡標識，存在224-2=16 777 214個主機標識，這是由于全0和全1組成的主機標識是無效的。因此，XA =127*16 777 214=2 130 706 178。為了找到XB 和 XC ，首先注意到存在214=16 3

4、84個B類網絡標識和212=2 097 152個C類網絡標識。對每個B類網絡標識存在著216-2=65 534個主機標識，而對每個C類網絡標識，存在28-2=254個主機標識，這也是考慮到全0和全1是無效的主機標識。因而, XB =1 073 709 056，XC=532 676 608。我們可以斷言IPv4有效地址的總數是: X= XA + XB + XC=2 130 706 178+1 073 709 056+532 676 608=3 737 091 842。7.2基本（不可重復）的排列與組合問題基本（不可重復）的排列與組合問題v 集合的集合的r-排列：排列：集合中的r個元素的有序序列

5、A=n，A的r-排列數P(n, r)=n(n-1)(n-r+1)=v 集合的集合的r-組合：組合：集合的r個元素的子集 A=n，A的r-組合數C(n, r)= P(n, r)/n!= C(n, r)= C(n, n-r)!(!rnn)!( !rnrnv關于二項式系數：注意它們的組合意義 C(n+1, k)= C(n, k-1)+C(n, k) （帕斯卡恒等式） C(m+n, r)= （范德蒙恒等式） （二項式定理） nknknC02),(rkknCkrmC0),(),(nkkknnyxknCyx0),()(nkkknC00),() 1(7.3可重復的排列和組合問題可重復的排列和組合問題v 定理

6、定理2 A=n，A的允許重復（重復次數沒有限制）的r-組合數是C(n+r-1, r)證明：證明：當允許重復時n元素集合的每個r-組合可以用n-1條豎線和r顆星的表表示。這n-1條豎線是用來標記n個不同的單元。每當集合的第i個元素出現在組合中，第i個單元就包含一顆星。例如，4元素集合的一個6-組合用3條豎線和6顆星來表示。這里* | * | | * * *代表了恰包含2個第一元素、1個第二元素、0個第三元素和3個第四元素的組合。 正如我們已經看到的，包含n-1條豎線和r顆星的每一個不同的表對應于n元素集合的允許重復的一個r-組合。這種表的個數是C(n+r-1, r)，因為每個表對應于從包含r顆星

7、和n-1條豎線的n-1+r個位置中取r個位置來訪r顆星的一種選擇。v 例例5 設一家甜點店有四種不同類型的甜點，那么從中選6塊甜點有多少種不同的方式 ？假定只關心甜點的類型，而不管是哪一塊甜點或者選擇的次序。解 選擇6塊甜點的方式數是具有4類元素集合的6-組合數。由定理2，這等于C(4+6-1, 6)=C(9,6)由于C(9,6)=C(9,3)=(9*8*7) / (1*2*3) = 84選擇6塊甜點的不同方式數有84種。v 例例6 方程x1+x2+x3=11有多少個解？其中x1,x2和x3是非負整數。解 為計數解的個數，注意到一個解對應了從3元素集合中選11個元素的方式，以使得x1選自第一類

8、，x2選自第二類，x3 選自第三類。因此，解的個數等于3元素集合允許重復的11-組合數。由定理2存在C(3+11-1, 11)=C(13,11)=C(13,2)=(13*12) / (1*2)=78個解。 v 例例7 在下面的偽碼被執行后k的值是什么？ k:=0for i1:=1 to nfor i2:=1 to i1for im :=1 to im-1k:=k+1解： k的初值是0，且對于一組滿足 1imim-1 i1n的整數i1 ，i2 ， im ，每次執行這個嵌套循環時k的值就加1. 這種整數的組數是從1,2, ,n中允許重復地選擇m個整數的方式數.(因為一旦這組整數選定以后，如果按非降

9、序排列它們,這就唯一地確定了一組對im , im-1, , i1的賦值。相反，每個這樣的賦值對應了一個唯一的無序集合。）所以由定理2得出在代碼被執行后k=C (n+m-1, m)。v 定理定理3 n1個1類物體，n2個2類物體，nk個k類物體，n=ni 這n個物體的全排列數是證明：證明：分別確定每類物體的排列位置，再用乘法原則 為確定排列數，首先注意到可以用C(n, n1)中方式在n個位置中方類型1的n1個物體，剩下n- n1個空位。然后用C(n-n1,n2)種方式來放類型2的物體，剩下n-n1- n2個空位。繼續放類型3的物體，類型k-1的物體，直到最后可用C(n-n1-n2- - nk-1

10、,nk)種方式放類型k的物體。因此，由乘積法則，不同排列的總數是 C(n,n1) C(n-n1 ,n2)C(n-n1-n2- - nk-1,nk) = * * * =!21knnnn)!nn( !11nn)!nn( !)!n(2121nnn ! 0 !)!n-n(k1k1nn !21knnnnv 定理定理4 n=ni個不同物體，放入k個盒子，第1個盒子n1個，第2個盒子n2個，第k個盒子nk個，方法數是證明：先對n個物體（任意）排序。為第i個盒子設計ni個相同的標記，對這n個標記做全排，根據全排列的結果分配物體入盒子v 例例11 有多少種方式把52張標準的撲克牌發給4個人使得每人5張牌？ 解 我們將使用乘積法則求解這個問題。開始，第一個人得到5張牌可以有C(52,5)種方式。第二個人得到5張牌可以有C(47,5)種方式，因為只剩下47張牌。第三個人得到5張牌可以有C(42,5)種方式。最后，第四個人得到5張牌可以有C(37,5)種方式。因此，發給4個人5張牌的方式總數是 C(52,5) C(47,5) C(42,5) C(37,5)= *=!21knnnn! 5 !47!52! 5 !42!47! 5 !37!42! 5 !32!37!32! 5 ! 5 ! 5!52習題習題 1.從集合1,