1

《圖論與組合優(yōu)化》第三講

可重組合與組合恒等式2允許重復(fù)的排列---多重集的排列多重集—元素可以多次出現(xiàn)的集合，即元素可以重復(fù)。我們把某個元素ai出現(xiàn)的次數(shù)ni(ni=0,1,2,…)叫做該元素的重復(fù)數(shù)，通常把含有k種不同元素的多重集S記作3

可重排列定義從一個多重集中有序選取的r個元素叫做S的一個r-(可重)排列。當(dāng)時也叫做S的一個排列.4定理設(shè)多重集則的r-(可重)排列數(shù)是rk5例求4位數(shù)的二進制數(shù)的個數(shù)解：所求的標(biāo)志數(shù)是多重集{2紅旗，3黃旗}的排列數(shù)，故N=5!/(2!*3!)=10例用兩面紅旗，三面黃旗依次懸掛在一根旗桿上，問可以組成多少種不同的標(biāo)志？

6允許重復(fù)的組合----可重組合允許重復(fù)(可重)的組合是指從中取r個元素,

允許重復(fù)，即允許.允許重復(fù)的組合個數(shù)記作C(n,r)定理1.2從中取r個作可重的組合，其個數(shù)為C(n+r-1,r)7定理1.2證明C(n,r)的計數(shù)問題相當(dāng)于r相同的球放入n個互異的盒子，每個盒子中球數(shù)不加限制的方案的計數(shù)。而后一問題又可轉(zhuǎn)換為r個相同的球與n-1個相同的盒壁的排列的問題。易知所求計數(shù)為=C(n+r-1,r)(n-1+r)!————r!(n-1)!

r個相同的球

/\———————

————————／\0…010…01…10…0

\/————————

\/

n-1個相同的盒壁8設(shè)a1a2…ar∈C(n,r)

1≤a1≤a2≤…≤

ai

≤…≤ar≤n,與下面的數(shù)列對應(yīng)相加0<1<2<…<i-1<…<r-1即bi=ai+i-1,i=1,2,…,r.則b1b2…br滿足1≤b1＜b2＜…＜br≤n+r-1

b1b2…br∈C(n+r-1,r)f：a1a2…ar→b1b2…br顯然f是雙射所以C(n,r)=C(n+r-1,r)－-1定理1.2證明－91.8.2不相鄰的組合

不相鄰的組合是指從序列{1,2,…,n}中取r個，不允許重復(fù)且不存在i,i+1兩個相鄰的數(shù)同時出現(xiàn)于一個組合中的組合定理1.4

從A={1,2,…,n}中取r個作不相鄰的組合，其個數(shù)為C(n-r+1,r)10任給a1a2…ar∈C’(n,r),

a1＜

a2＜

…＜

ar≤n且

ai+1-ai≥2,i=1,2,…,r-1與下面的數(shù)列對應(yīng)相減0<1<2<…<i-1<…<r-1得1≤b1＜

b2＜

…＜

br

≤

n-r+1，其中

bi=ai-i+1,i=1,2,…,rbi+1-bi≥1.b1b2…br∈C(n-r+1,r)令f：a1a2…ar→b1b2…br

C’(n,r)=C(n-r+1,r)定理1.4的證明11組合恒等式

如圖，求從(0,0)點到(m,n)點、沿格子線走的最短路徑數(shù)N。

一條到達點(m,n)的路徑對應(yīng)一個由m個x，n個y組成的排列xxxyyxyxxyyxxyyxxxy12若干組合等式(1)C(n,r)=C(n,n-r)

(2)C(n,k)=C(n-1,k)+C(n-1,k-1)

證明1：從{1,2,…,n}中取k個組合的全體可以分為兩組：

A1組：含有元素n，|A1|=C(n-1,k-1)A2組：不含元素n，|A2|=C(n-1,k)13(2)C(n,k)=C(n-1,k)+C(n-1,k-1)

證明2：考慮如圖棋盤從(0,0)到(k,n-k)的最短路條數(shù)為C(n,k)，其中經(jīng)過P1點的有C(n-1,k),經(jīng)過P2點的有C(n-1,k-1)。14四.若干組合等式(2)C(n,r)=C(n-1,r)+C(n-1,r-1)

(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).證明1：由（2）可得。15(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).證明2：從{1,2,…,n+r+1}中取r個組合的全體可以分為r+1組：A1：不含1，|A1|=C(n+r,r)A2：含1但不含2，|A2|=C(n+r-1,r-1)A3：含1,2，但不含3，|A3|=C(n+r-2,r-2)………Ar：含1,2,…,r-1，但不含r，|Ar|=C(n+1,1)Ar+1：由12…r組成的組合，|Ar+1|=C(n,0)16(4)C(n,k)C(k,r)=C(n,r)C(n-r,k-r),(k>r).證明：考慮如下問題，把Nn={1,2,…,n}分為甲、乙、丙三組，使得甲組恰有r個，乙組恰有k-r個，丙組恰有n-k個，其分法種數(shù)可以用兩種方法計算。方法1：從Nn中取k個，余下的n-k個放在丙組；再從取出的k個中撥出r個分在甲組，余下的k-r個分在乙組，分法種數(shù)有C(n,k)C(k,r)。方法2：從Nn中取r個分在甲組，再從余下的n-r個中取出k-r個分在乙組，最后剩下的n-k個分在丙組，分法種數(shù)有C(n,r)C(n-r,k-r)。17(5)C(m,0)+C(m,1)+…+C(m,m)=2m.

(x+y)m=xm+C(m,1)xm-1y+C(m,2)xm-2y2+…+ym(6)C(n,0)-C(n,1)+C(n,2)-…+(-1)^nC(n,n)=0.(7)C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0),r<min(m,n).(8)C(m+n,m)=C(m,0)C(n,0)+C(m,1)C(n,1)+…+C(m,m)C(n,m),mn.18撲克問題每張撲克牌都有兩種標(biāo)志，一種是花色{????}，另一種標(biāo)志是數(shù)值

{2,3,4,5,6,7,8,9,10,J,Q,K,A}共52張。(1)從52張撲克牌中取出5張，使其中兩張的值相同，另外3張的值也相同，有多少種方案？(2)取出5張撲克牌，出現(xiàn)兩對同值的方案數(shù)是多少？(3)兩個牌友A和B，各取五張，分別有兩對相同的數(shù)值，問這樣的狀態(tài)有多少種？19有限制的路徑問題從(0,0)點到達(m,n)點，其中m<n。要求中間所經(jīng)過的路徑上的點(x,y)恒滿足x<y。問有多少不同的路徑？售票問題一場音樂會票價50元，排隊的顧客中有n位持50元的鈔票，m位持100元的鈔票。售票處沒有準(zhǔn)備零錢。試問有多少