1

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

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

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

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

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

r個(gè)相同的球

/\———————

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

\/————————

\/

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

1≤a1≤a2≤…≤

ai

≤…≤ar≤n,與下面的數(shù)列對(duì)應(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個(gè)，不允許重復(fù)且不存在i,i+1兩個(gè)相鄰的數(shù)同時(shí)出現(xiàn)于一個(gè)組合中的組合定理1.4

從A={1,2,…,n}中取r個(gè)作不相鄰的組合，其個(gè)數(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ù)列對(duì)應(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)點(diǎn)到(m,n)點(diǎn)、沿格子線走的最短路徑數(shù)N。

一條到達(dá)點(diǎn)(m,n)的路徑對(duì)應(yīng)一個(gè)由m個(gè)x，n個(gè)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個(gè)組合的全體可以分為兩組：

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)過(guò)P1點(diǎn)的有C(n-1,k),經(jīng)過(guò)P2點(diǎn)的有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個(gè)組合的全體可以分為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).證明：考慮如下問(wèn)題，把Nn={1,2,…,n}分為甲、乙、丙三組，使得甲組恰有r個(gè)，乙組恰有k-r個(gè)，丙組恰有n-k個(gè)，其分法種數(shù)可以用兩種方法計(jì)算。方法1：從Nn中取k個(gè)，余下的n-k個(gè)放在丙組；再?gòu)娜〕龅膋個(gè)中撥出r個(gè)分在甲組，余下的k-r個(gè)分在乙組，分法種數(shù)有C(n,k)C(k,r)。方法2：從Nn中取r個(gè)分在甲組，再?gòu)挠嘞碌膎-r個(gè)中取出k-r個(gè)分在乙組，最后剩下的n-k個(gè)分在丙組，分法種數(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撲克問(wèn)題每張撲克牌都有兩種標(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)兩對(duì)同值的方案數(shù)是多少？(3)兩個(gè)牌友A和B，各取五張，分別有兩對(duì)相同的數(shù)值，問(wèn)這樣的狀態(tài)有多少種？19有限制的路徑問(wèn)題從(0,0)點(diǎn)到達(dá)(m,n)點(diǎn)，其中m<n。要求中間所經(jīng)過(guò)的路徑上的點(diǎn)(x,y)恒滿足x<y。問(wèn)有多少不同的路徑？售票問(wèn)題一場(chǎng)音樂(lè)會(huì)票價(jià)50元，排隊(duì)的顧客中有n位持50元的鈔票，m位持100元的鈔票。售票處沒(méi)有準(zhǔn)備零錢。試問(wèn)有多少