組合數(shù)學(xué)的研究內(nèi)容組合存在性組合計數(shù)組合枚舉組合優(yōu)化本書的內(nèi)容基本的組合計數(shù)公式遞推方程與生成函數(shù)第四部分組合數(shù)學(xué)1第十二章基本的組合計數(shù)公式主要內(nèi)容加法法則與乘法法則排列與組合二項式定理與組合恒等式多項式定理212.1加法法則與乘法法則加法法則乘法法則分類處理與分步處理3加法法則加法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或B”有m+n種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式不重疊適用問題：分類選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2種產(chǎn)生方式，…,事件Ak有pk

種產(chǎn)生的方式，則“事件A1或A2或…Ak”有p1+p2+…+pk

種產(chǎn)生的方式.4乘法法則乘法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與B”有mn種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式彼此獨立適用問題：分步選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2種產(chǎn)生方式，…,事件Ak有pk

種產(chǎn)生的方式，則“事件A1與A2與…Ak”有p1p2…pk

種產(chǎn)生的方式.5分類處理與分步處理分類處理：對產(chǎn)生方式的集合進行劃分，分別計數(shù)，然后使用加法法則分步處理：一種產(chǎn)生方式分解為若干獨立步驟，對每步分別進行計數(shù)，然后使用乘法法則分類與分步結(jié)合使用

先分類，每類內(nèi)部分步先分步，每步又分類6實例：關(guān)系計數(shù)例1設(shè)A為n元集，問(1)A上的自反關(guān)系有多少個？(2)A上的對稱關(guān)系有多少個？(3)A上的反對稱關(guān)系有多少個？(4)A上的函數(shù)有多少個？其中雙射函數(shù)有多少個？.(2)考慮對稱關(guān)系的矩陣.i行j列(i≠j)的元素rij=rji.能夠獨立選擇0或1的位置有(n2n)/2個.加上主對角線的n個位置，總計(n2+n)/2個位置，每個位置2種選擇，根據(jù)乘法法則，構(gòu)成矩陣的方法數(shù)是(1)在自反關(guān)系矩陣中，主對角線元素都是1，其他位置的元素可以是1，也可以是0，有2種選擇.這種位置有n2n個，根據(jù)乘法法則，自反關(guān)系的個數(shù)7解答(3)非主對角線位置分成(n2n)/2組，每組包含元素rij和rji.根據(jù)反對稱的性質(zhì)，rij與rji的取值有以下3種可能：

rij=1,rji=0；rij=0,rji=1；rij=rji=0.所有這些位置元素的選擇方法數(shù)為.再考慮到主對角線元素的選取，由乘法法則總方法數(shù)為(4)設(shè)A={x1,x2,…,xn}，任何A上的函數(shù)f:AA具有下述形式：f={<x1,y1>,<x2,y2>,…,<xn,yn>}其中每個yi（i=1,2,…,n）有n種可能的選擇，根據(jù)乘法法則，有nn個不同的函數(shù).若f是雙射的，那么y1確定以后，y2只有n1種可能的取值,…,yn只有1種取值.構(gòu)成雙射函數(shù)的方法數(shù)是n(n1)(n2)…1=n!.8A0netid(7位)hosted(24位)B10netid(14位)hostid(16位)C110netid(21位)hostid(8位)D1110(28位)E11110(27位)例2：Ipv4網(wǎng)址計數(shù)32位地址網(wǎng)絡(luò)標(biāo)識+主機標(biāo)識(1)A類：最大網(wǎng)絡(luò)；B類：中等網(wǎng)絡(luò)；C：小網(wǎng)絡(luò)；D：多路廣播；E：備用(2)限制條件：1111111在A類中的netid部分無效hostid部分不允許全0或全1

9

netidhostidA類：0+7位，24位B類：10+14位，16位C類：110+21位，8位限制條件：1111111在A類中的netid部分無效hostid部分不允許全0或全1A類：netid271,hosted2242，

NA＝12716777214＝2130706178B類：netid214,hosted2162，

NB＝1638465534＝1073709056C類：netid221,hosted282,

NC＝2097152254＝532676608

N＝NA+NB+NC＝3737091842解答10選取問題：設(shè)n元集合S，從S中選取r個元素.根據(jù)是否有序,是否允許重復(fù),將該問題分為四個子類型不重復(fù)選取重復(fù)選取有序選取集合的排列多重集的排列無序選取集合的組合多重集的組合12.2排列與組合11定義12.1設(shè)S為n元集，(1)從S中有序選取的r個元素稱為S的一個r排列，S的不同r排列總數(shù)記作P(n,r),r=n的排列是S的全排列.(2)從S中無序選取的r個元素稱為S的一個r組合，S的不同r組合總數(shù)記作C(n,r)集合的排列定理1.1

設(shè)n,r為自然數(shù)，規(guī)定0!=1，則12下面考慮nr的情況.(1)排列的第一個元素有n種選擇的方式.排列的第二個元素有n1種選法,…,第r個元素的方式數(shù)n

r+1.根據(jù)乘法法則，總的選法數(shù)為

n(n

1)(n2)…(n

r+1)=(2)分兩步構(gòu)成r排列.首先無序地選出r個元素，然后再構(gòu)造這r個元素的全排列.無序選擇r個元素的方法數(shù)是C(n,r)；針對每種選法，能構(gòu)造r!個不同的全排列.根據(jù)乘法法則，不同的r排列數(shù)滿足P(n,r)=C(n,r)r!組合數(shù)C(n,r)也稱為二項式系數(shù)，記作證明13推論設(shè)n,r為正整數(shù)，則(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)推論例3證明C(n,r)=C(n,nr)證設(shè)S={1,2,…,n}是n元集合，對于S的任意r組合A={a1,a2,…,ar}，都存在一個S的nr組合SA與之對應(yīng).顯然不同的r組合對應(yīng)了不同的nr組合，反之也對，因此S的r組合數(shù)恰好與S的nr組合數(shù)相等.公式(3)

稱為Pascal公式，也對應(yīng)了楊輝三角形證明方法：公式代入并化簡，組合證明14楊輝三角111121133114641510101161520515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=615多重速集的酸排列義與組友合定義12史.2多重裁集S={n1a1,n2a2,秩…,nkak}，n=n1+n2+…nk表示S中元制素的族總數(shù).(1橋)從S中有識序選螺取的r個元控素稱枝為多魚重集S的一圈個r排列.r=n的排換列稱暈為S的全排摩列(2黑)從S中無士序選千取的r個元施素稱造作多釋重集S的一當(dāng)個r組合注意腿：多重憶集中掉元素滋的重錯復(fù)度凱，0仁<ni+∞少,當(dāng)ni＝+∞，表趕示ai重復(fù)稍選取嶼的次坐數(shù)沒褲有限樣制S的子循集X={x1a1,x2a2,秧…,xkak},其中0xi+∞16多重煎集的圖排列饞計數(shù)定理12行.2設(shè)S={n1a1,n2a2,妥…,nkak}為多駕重集槍，(1抖)S的全季排列治數(shù)是(2鍵)若rni，i=1翻,2柴,…諸,k，那贊么S的r排列階數(shù)是kr證明(1)有C(n,n1)種方法放a1，有C(nn1,n2)種方法放a2,…,最后有C(nn1n2…nk1,nk)方法放ak.根據(jù)乘法法則,

(2)r個位置中的每個位置都有k種選法，由乘法法則得kr

17多重扁集的保組合定理12鑰.3多重篩集S={n1a1,n2a2,涂…,nkak}，0<ni+∞當(dāng)rni,質(zhì)S的r組合鑄數(shù)為N=C(k+菜r1,r),證明貪一個r組合星為{x1a1,x2a2,神…,xkak}，其中x1+x2+詠…檢+xk=r,xi為非膜負整室數(shù).這個猜不定猛方程翠的非凍負整狗數(shù)解蛇對應(yīng)由于下紡述排累列1…熟1麗0炒1…芽1烤0僚1…生1圓0爪……寄0倒1糞…1x1個x2個x3個xk個r個1，k1個0的全兼排列氧數(shù)為18例3排列26個字絕母，還使得a與b之間版恰有7個字氧母，揉求方站法數(shù).解膛固瞇定a和b,中間旋選7個字余母，卻有2P(2卻4,諒7)種方腹法，將它己看作越大字兼母與戲其余17個字序母全撿排列乏有18！種節(jié)，共N=么2P(2稿4,貼7)茶1敵8!組合窩計數(shù)險的應(yīng)瓶用解相當(dāng)于2n不同的球放到n個相同的盒子，每個盒子2個，放法為例4把2n個人則分成n組，喬每組2人，序有多順少分該法？19解管使孤用一炕一對乏應(yīng)的糾思想糖求解貍這個芽問題.a1,a2,獨…,ak：k個不紀相鄰藥的數(shù),屬于乒集合{1員,徑2,傷…矛,n}b1,b2,戀…,bk：k個允傘許相隊鄰的后數(shù),屬于銀集合{1基,濕…,n(k1)趴}對應(yīng)穿規(guī)則或是bi=ai(i1)途.i=1練,赴2,帝…安,k因此N聚=矮C(nk+1,k)例5從S={盼1,巨2顏,蘋…出,n}中選溉擇k個不眾相鄰友的數(shù)例，有交多少僑種方咐法？一一踏對應(yīng)條的技跑巧20主要背內(nèi)容二項禍?zhǔn)蕉ㄗ嚼斫M合兼恒等變式非降兔路徑泰問題12諸.3二項劉式定舍理與胖組合爐恒等話式21二項么式定昌理定理12頂.4設(shè)n是正栽整數(shù)車，對脹一切x和y證明方法:數(shù)學(xué)歸納法、組合分析法.證當(dāng)乘積被展開時其中的項都是下述形式：xiyni,i=0,1,2,…,n.而構(gòu)成形如xiyni的項，必須從n個和(x+y)中選i個提供x，其它的ni個提供y.因此，xiyni的系數(shù)是，定理得證.

22二項識式定微理的是應(yīng)用解由二項式定理令i=13得到展開式中x12y13的系數(shù)，即

例6求在(2x－3y)25的展惱開式爽中x12y13的系玻數(shù).23組合印恒等臉式：厭遞推捷式證明掃方法乞：公宿式代蕉入、妹組合雹分析應(yīng)用填：1式用刃于化調(diào)簡2式用肚于求杠和時愛消去鵝變系未數(shù)3式用域于求吵和時批拆項雖（兩裝項之辨和或淺者差孝），鑰然后尋合并24組合偽恒等屈式：釣基本鑼求和樂式證明鐮公式4.方法硬：二圈項式子定理喚或者氣組合什分析.設(shè)S={征1,擇2,怎…,n}，下勵面計素數(shù)S的所亂有子傭集.一種赤方法紡就是巡壽分類義處理共，n元集賺合的k子集串個數(shù)種是根據(jù)午加法膀法則敏，子治集總攔數(shù)是另一塌種方鄉(xiāng)豐法是蠟分步虎處理爽，為繩構(gòu)成S的子苗集A，每視個元悔素有2種選倦擇，拴根據(jù)欲乘法斗法則炮，子呢集總撞數(shù)是2n.25恒等考式求擁和:變系些數(shù)和證明匙方法甚：二項厚式定提理、惑級數(shù)腐求導(dǎo)其他悲組合攤恒等繪式代奏入26證明招公式627證明咳公式728恒等牛式:變上夢項求抄和證明組合分析.令S={a1,a2,…,an+1}為n+1元集合.等式右邊是S的k+1子集數(shù).考慮另一種分類計數(shù)的方法.將所有的k+1元子集分成如下n+1類：第1類：含a1,剩下k個元素取自{a2,…,an+1}

第2類：不含a1,含a2,剩下k個元素取自{a3,…,an+1}……不含a1,a2,疾…,an,含an+1,剩下k個元權(quán)素取司自空槽集由加忌法法遠則公研式得戀證29恒等俗式:乘積梯轉(zhuǎn)換弄式證明方法：組合分析.n元集中選取r個元素，然后在這r個元素中再選k個元素.不同的r元子集可能選出相同的k子集，例如{a,b,c,d,e}{a,b,c,d

}{b,c,d}{b,c,d,e}{b,c,d}重復(fù)度為：應(yīng)用：將變下限r(nóng)變成常數(shù)k，求和時提到和號外面.30恒等凡式:積之壘和關(guān)系證明思乞路：跌考慮鋤集合A={a1,a2,…移,am}，B={b1,b2,…烏,bn}.等式右桌邊計島數(shù)了株從這瘡兩個保集合奏中選心出r個元貨素的胃方法.將這些選公法按犁照含蹤蝶有A中元斑素的蘆個數(shù)k進行斯分類汁，k=0畫,1曉,…科,r.然后牙使用葬加法楊法則.31組合辦恒等哨式解奪題方鈴法小遲結(jié)證明姿方法途：已知嘴恒等汽式帶睡入二項名式定蒸理冪級響數(shù)的吸求導(dǎo)亞、積躲分歸納書法組合拴分析求和尸方法商：Pa虜sc禮al公式級數(shù)劍求和觀察奇和的濾結(jié)果汁，然夠后使陵用歸沸納法馬證明利用溫已知既的公棕式32非降冬路徑焰的計事數(shù)(0五,0意)到(m,集n)的非蛾降路綢徑數(shù)腿：C(m+扛n,m)(a,慘b)到(m,隙n)的非柜降路陽徑數(shù)侄：等于(0坐,0妄)到(ma,nb)的非仿降路視徑數(shù)(a,影b)經(jīng)過(c,罩d)到(m,深n)的非齊降路因徑數(shù)同：乘得法法統(tǒng)則(m,n)(0,0)33從(0漫,0椅)到(n,蘋n)不接蓬觸對概角線劣的非關(guān)降路冊徑數(shù)NN1：從(0佳,0具)到(n,壟n)下不拒接觸前對角線非娛降路歷徑數(shù)N2：從(1輸,0緊)到(n,充n1)下不徑接觸瞧對角線非近降路敞徑數(shù)N0:從(1復(fù),0漁)到(n,勢n1)的非狠降路帳徑數(shù)N3:從(1援,0怨)到(n,魂n1)接觸符對角漠線的非降映路徑賞數(shù)關(guān)系:N=2N1=2N2=2犧[N0N3](0,0)(1,0)(n,n-1)(n,n)限制收條件鎮(zhèn)的非依降路私徑數(shù)34N3:從(1盯,0處)到(n,墨n1)接觸凱對角很線的非降孔路徑的數(shù)N4:從(0另,1蜂)到(n,候n1)無限充制條勺件的非降拜路徑吐數(shù)關(guān)系:N3=N4一一猴對應(yīng)(1,0)(0,1)(n,n-1)(0,0)(n,n)35例7A={勵1,腦2,晨…,m},B={餅1,箭2,約…,n}，N1:B上單弄調(diào)遞沖增函齒數(shù)個數(shù)是(1銅,1括)到(n+1獲,n)的非惜降路箏徑數(shù)N:B上單挺調(diào)函印數(shù)個叉數(shù)N=2N1N2:A到B單調(diào)佩遞增趣函數(shù)籮個數(shù)是潤從(1如,1梳)到(m+1王,n)的非愛降路跨徑數(shù)N:A到B單調(diào)謝函數(shù)令數(shù)，N=2N2嚴格抓單調(diào)光遞增遠函數(shù)搭、遞律減函押數(shù)個扶數(shù)都非是C(n,懂m)(1,f(1))(2,f(2))(n,f(n))(n+1,n)(1,1)應(yīng)用:單調(diào)夢函數(shù)嘆計數(shù)36棧輸片出的暗計數(shù)例8將1,賞2憂,今…潮,n按照壟順序狐輸入鈔棧，梯有多釘少個院不同踐的輸出序喊列？分析扎：將捆進棧肺、出犯棧分水別記香作x,榆y把,出棧醒序列鞭是n個x，n個y的排支列，排列傾中任發(fā)何前晉綴的x個數(shù)叫不少念于y的個扔數(shù)，等于商從(0逆,0約)到(n,搜n)的不雹穿過珠對角字線的成非降縣路徑報數(shù)37輸入蚊：1,2,3,4,5,輸出：3,2,4,1,5進,進,進,出,出,進,出,出,進,出議x,x,x,y撒,y抱,x,y鞠,y乞,x,y12534棧輸劑出的想計數(shù)38棧輸彩出的謙計數(shù)從(0走,0跪)到(n,充n)的穿過對承角線四的非邪降路弟徑從(-暮1,庸1)到(n,稍n)的非降汁路徑從(0降,0版)到(n,乓n)的非緞降路徑峰總數(shù)倉為C(賠2n,慌n)條，從(-師1,消1)到(n,最n)的非秧降路徑喊數(shù)為C(蒜2n,n-1添)條，(n,n)(0,0)(-1,0)(-1,1)39A=守{1控,討2,見…票,m},B=糧{1負,債2,揉…牌,n}f:AB函數(shù)暢計數(shù)角小結(jié)40.定理12轎.6設(shè)n為正堆整數(shù)凱，xi為實夜數(shù)，i=1塘,壇2,倉…墻,t.求和透是對柴滿足含方程n1+n2+…衰+nt=n的一量切非奔負整質(zhì)數(shù)解步求在n個因式中選n1個因式貢獻x1,從剩下nn1個因式選n2個因式貢獻x2,…,從剩下的nn1n2…nt1個因式中選nt個因式貢獻xt.證明展開式中的項是如下構(gòu)成的:12納.4多項責(zé)式定理41推論推論1多項拔式展晶開式懶中不朗同的廈項數(shù)綢為方爬程的非藥負整劃數(shù)解法的個兄數(shù)C(n+釣t1,n)推論2例9求(2x13x2+5x3)6中x13x2x32的系階數(shù).解流由飾多項扛式定姻理得42多項哀式系粒數(shù)組合激意義多項殊式系敵數(shù)多重攝集S={n1a1,n2a2,錢…,ntat}的全宏排列如數(shù)n個不待同的截球放演到t個不符同的旬盒子述使得防第一轎個盒贏子含n1個球滲，第灶二個鉤盒子砍含n2個球測，…，第t個盒紀子含nt個球豆的方還案數(shù)符號43第十宰二章示習(xí)蹲題課主要控內(nèi)容基本簡計數(shù)計數(shù)疑法則截：加楚法法劣則、銹乘法收法則計數(shù)珠模型期：選望取問諒題、馬非降篩路徑孫問題趙、方友程的北非負獸整數(shù)解問踏題處理妹方法挨：分掘類處蘇理、孫分步際處理唯、一歪一對豈應(yīng)思斯想計數(shù)足符號組合慢數(shù)或斷二項擇式系智數(shù)C(m,慎n)：組倆合恒聲等式排列夾數(shù)P(m,室n)多項消式系寺數(shù)二項距式定暢理與總多項賴式定席理44基本押要求能夠秘熟練按使用待加法牧法則聲與乘訓(xùn)法法區(qū)則熟悉謊和應(yīng)輕用基閘本的年組合逃計數(shù)收模型情：選取煉問題不等婆方程濾的解非降陰路徑熟悉朽二項公式定趁理與歉多項月式定仙理能證白明組桶合恒村等式目并對糕二項菠式系稅數(shù)進獵行求樸和了解竊多項檔式系纖數(shù)及善其相惱關(guān)公容式45練習(xí)1：基本須的組您合計云數(shù)1.求14迅00的不歌同的提正因揪子個企數(shù).解14的00的素要因子牽分解棋式是14詳00疼=餅2352714漆00的任歡何正倍因子概都具擊有下繭述形侵式：2i5j7k，其痕中0六i3,享0j2,暫0k1.根據(jù)蔬乘法氏法則卷，14炭00的正敘因子仗數(shù)是i,j,k的選診法數(shù)N=(村1+普3)責(zé)(1裝+2株)(偵1+倡1)秀=2細4.46練習(xí)2：基序本的取組合辜計數(shù)2．把10個不旱同的錦球放脈到6個不擺同的帖盒子灑里，丑允許裹空盒燥，且尿前2個盒雙子球報的總鏟數(shù)至柱多是4，問腫有多燃少種乓方法速？解根據(jù)閉前兩程個盒史子含幣球數(shù)k對放近法分器類，孟其中k=0詠,1晃,2艙,3使,4晶.對于睡給定蜓的k，再餐分步剩處理墊計算斤放球圖的方青法數(shù)摔：①黑從10個球研中選揮放入騾前兩悅個盒尚子的k個球繩，有C(1盤0,k)選法廈；②脾把選賠好的k個球滔分到2個盒別子里夢，每頁個球預(yù)可以災(zāi)有2種選下?lián)?，?k種分節(jié)法；③梳剩