組合與圖論-數(shù)學(xué)第一講

前言組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方…...幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。519372486前言1666年萊布尼茲所著《組合學(xué)論文》一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。組合數(shù)學(xué)研究的中心問題是按一定規(guī)則將一些事物安排成各式各樣模式的問題。包括安排的存在問題、計(jì)數(shù)問題、構(gòu)造問題以及給出了優(yōu)化標(biāo)準(zhǔn)后如何求出最優(yōu)安排問題。前言

組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。第一章 排列與組合1.1加法法則與乘法法則.

[加法法則] 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。集合論語(yǔ)言： 若|A|=m,|B|=n,AB=,則|AB|=m+n。第一章 排列與組合[例]某班選修企業(yè)管理的有18人，不選的有10人，則該班共有

18+10=28人。[例]北京每天直達(dá)上海的客車有5次，客機(jī)有3次，則每天由北京直達(dá)上海的旅行方式有5+3=8種。第一章 排列與組合[乘法法則] 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有m·n種產(chǎn)生方式。集合論語(yǔ)言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},則|AB|=m·n。第一章 排列與組合[例]某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自{a，b，c，d，e}，第二個(gè)字符可選自{1，2，3}，則這種字符串共有53=15個(gè)。[例]從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32=6條道路。第一章 排列與組合例某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則方案數(shù)就不是44=16，而只有43=12種。在乘法法則中要注意事件A和事件B的相互相容性。第一章 排列與組合例1)求小于10000的含1的正整數(shù)的個(gè)數(shù)

2)求小于10000的含0的正整數(shù)的個(gè)數(shù)1)小于10000的不含1的正整數(shù)可看做4位數(shù),但0000除外.

故有9×9×9×9－1＝6560個(gè).

含1的有：9999－6560=3439個(gè)另:全部4位數(shù)有104

個(gè),不含1的四位數(shù)有94個(gè),含1的4位數(shù)為兩個(gè)的差:104－94=3439個(gè)第一章 排列與組合2)“含0”和“含1”不可直接套用。0019含1但不含0。在組合的習(xí)題中有許多類似的隱含的規(guī)定，要特別留神。

不含0的1位數(shù)有9個(gè)，2位數(shù)有92個(gè)，3位數(shù)有93個(gè)，4位數(shù)有94個(gè)不含0小于10000的正整數(shù)有9+92+93+94=(95－1)/(9－1)=7380個(gè)含0小于10000的正整數(shù)有

9999－7380=2619個(gè)第一章 排列與組合1.2排列與組合定義：從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的排列。其排列的個(gè)數(shù)記為P(n,r)表示。nr

若取出r個(gè)元素而不考慮次序，則稱從n個(gè)不同元中取r個(gè)元的組合。其組合的個(gè)數(shù)記為C(n,r)或（）第一章 排列與組合規(guī)定：從n個(gè)不同元中取n個(gè)的排列稱為n的全排列第一章 排列與組合我們有下列排列與組合的計(jì)數(shù)公式：特別地，對(duì)于全排列有P(n,n)=n!。第一章 排列與組合從n個(gè)中取r個(gè)的排列的典型例子是從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè)。第1個(gè)盒子有n種選擇，第2個(gè)有n-1種選擇，······，第r個(gè)有n-r+1種選擇。故有P(n,r)=n(n-1)···(n-r+1)有時(shí)也用[n]r記P(n,r)第一章 排列與組合若球不同，盒子相同，則是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。故有C(n,r)·r!=P(n,r),nrn!———r!(n-r)!C(n,r)=P(n,r)/r!=[n]r/r!=()=第一章 排列與組合例有5本不同的日文書，7本不同的英文書，10本不同的中文書。

1)取2本不同文字的書；

2)取2本相同文字的書；

3)任取兩本書請(qǐng)問有多少種不同的取法？解：1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()5+7+102第一章 排列與組合例從[1,300]中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？解：將[1,300]分成3類：

A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡3(mod3)}={3,6,9,…,300}.要滿足條件，有四種解法：

1)3個(gè)數(shù)同屬于A;2)3個(gè)數(shù)同屬于B3)3個(gè)數(shù)同屬于C;4)A,B,C各取一數(shù).故共有3C(100,3)=1485100第一章 排列與組合定義：從n個(gè)不同元素中允許重復(fù)地取r個(gè)元素作排列，稱為n元可重r-排列，其排列數(shù)為nr例：由數(shù)字1，2，3可組成多少個(gè)兩位數(shù)？并寫出這些兩位數(shù)。解：這是三元可重2-排列問題。其排列數(shù)為32=9。這些兩位數(shù)為11,12,13,21,22,23,31,32,33。n1個(gè)a1,n2個(gè)a2,…nk個(gè)ak的全排列的個(gè)數(shù)為:第一章 排列與組合定義：從n個(gè)不同元素中取r個(gè)元素圍成一圈，稱為從n個(gè)不同元中取r個(gè)元的圓排列，其排列數(shù)記為K(n,r)。我們有：123r-1r這是因?yàn)閞個(gè)不同的線排列（即一般的排列）對(duì)應(yīng)于一個(gè)圓排列。第一章 排列與組合例：4個(gè)女生和4個(gè)男生圍圓桌相間而坐，試問有多少種不同的入座方式？解：先讓女生入座，這是一個(gè)4的圓排列問題。有K（4，4）×4!=4！/4×4!=3！×4!。例:由四種顏色的珠子各一顆，可以做成多少種不同的項(xiàng)鏈？解：注意項(xiàng)鏈可以翻轉(zhuǎn)。第一章 排列與組合定義：從n個(gè)不同元中允許重復(fù)地取r個(gè)元的組合，稱為n元可重r-組合，其組合數(shù)記為F(n,r)。用集合描述為：重集{∞·a1,∞·a2,…∞·an}的r-組合數(shù)為F(n,r)。結(jié)論：F(n,r)=C(n+r-1,r)，其中n,r均為正整數(shù)。證明要點(diǎn)：設(shè)a1,a2,…ar是從1,2,…,n中任取的一個(gè)可重r-組合，不妨設(shè)：1≤a1≤a2≤…≤ar≤n從而有：1≤a1<a2+1

<a3+2<

…<ar+r-1

≤n+r-1第一章 排列與組合例:某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？[解]一進(jìn)站方案表示成：00011001010100其中“0”表示人，“1”表示門框，其中“0”是不同元，“1”是相同元。給“1”n個(gè)門只用n-1個(gè)門框。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。第一章 排列與組合[解法1]標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。故若設(shè)x為所求方案，則

x·5!=14!∴x=14!/5!=726485760[解法2]在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，在確定人的位置，有9！種選擇。故C(14,5)·9!即所求第一章 排列與組合[解法3]把全部選擇分解成若干步，使每步宜于計(jì)算。不妨設(shè)9個(gè)人編成1至9號(hào)。1號(hào)有6種選擇；2號(hào)除可有1號(hào)的所有選擇外，還可（也必須）選擇當(dāng)與1號(hào)同一門時(shí)在1號(hào)的前面還是后面，故2號(hào)有7種選擇；3號(hào)的選擇方法同2號(hào)，故共有8種。以此類推，9號(hào)有14種選擇。故所求方案為6×7×8×…×14種。第一章 排列與組合1.3模型轉(zhuǎn)換“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。如我們說A集合有n個(gè)元素|A|=n，無(wú)非是建立了將A中元與[1,n]元一一對(duì)應(yīng)的關(guān)系.在組合計(jì)數(shù)時(shí)往往借助于一一對(duì)應(yīng)實(shí)現(xiàn)模型轉(zhuǎn)換。比如要對(duì)A集合計(jì)數(shù)，但直接計(jì)數(shù)有困難,于是可設(shè)法構(gòu)造一易于計(jì)數(shù)的B，使得A與B一一對(duì)應(yīng)。第一章 排列與組合例在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問要舉行幾場(chǎng)比賽？解一種常見的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。第一章 排列與組合

H|H—C—H|H—C—H|H—C—H|H—C—H|H

H|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4異丁烷這說明對(duì)應(yīng)CnH2n+2的枝鏈?zhǔn)怯?n+2個(gè)頂點(diǎn)的一棵樹，其中n個(gè)頂點(diǎn)與之關(guān)聯(lián)的邊數(shù)為4；其它2n+2個(gè)頂點(diǎn)是葉子。對(duì)于這樣結(jié)構(gòu)的每一棵樹，就對(duì)應(yīng)有一種特定的化合物。從而可以通過研究具有上述性質(zhì)的樹找到不同的碳?xì)浠衔顲nH2n+2.第一章 排列與組合例簡(jiǎn)單格路問題|(0,0)→(m,n)|=().從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少條路徑？m+nmy(m,n)...O...x第一章 排列與組合無(wú)論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個(gè)x表示x方向上的一步，一個(gè)字母y表示y方向上的一步。則(0,0)→(m,n)的每一條路徑可表示為m個(gè)x與n個(gè)y的一個(gè)有重排列。將每一個(gè)有重排列的x與y分別編號(hào)，可得m!n!個(gè)m+n元的無(wú)重全排列。第一章 排列與組合設(shè)所求方案數(shù)為P(m+n；m，n)則P(m+n；m，n)·m!·n!=(m+n)!故P(m+n;m,n)=———=()=()=C(m+n,m)(c,d)(a,b)(m+n)!m!n!m+nnm+nm(c-a)+(d-b)c-a設(shè)c≥a,d≥b,則由(a,b)到(c,d)的簡(jiǎn)單格路數(shù)為|(a,b)(c,d)|=()第一章 排列與組合例：在上例的基礎(chǔ)上若設(shè)m<n，求(0,1)點(diǎn)到(m,n)點(diǎn)不接觸對(duì)角線x=y的格路的數(shù)目(“接觸”包括“穿過”)從(0,1)點(diǎn)到(m,n)點(diǎn)的格路，有的接觸x=y，有的不接觸。對(duì)每一條接觸x=y的格路，做(0,1)點(diǎn)到第一個(gè)接觸點(diǎn)部分關(guān)于x=y的對(duì)稱格路，這樣得到一條從(1,0)到(m,n)的格路。第一章 排列與組合容易看出從(0,1)到(m,n)接觸x=y的格路與(1,0)到(m,n)的格路(必穿過x=y)一一對(duì)應(yīng)y

y=x(m,n)O(1,0)x(0,1)..故所求格路數(shù)為()－()。m+n-1m+n-1mm-1第一章 排列與組合若條件改為可接觸但不可穿過，則限制線要向下或向右移一格，得x－y=1，(0,0)關(guān)于x－y=1的對(duì)稱點(diǎn)為(1,-1).格路也是一種常用模型m+nm+nmm-1(m+n)!(m+n)!m!n!(m-1)!(n+1)!m+nmn+1-mn+1所求格路數(shù)為

()－()=———

－————

=———()yx-y=1(m,n)x(0,0)(1,-1).....第一章 排列與組合例

CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈：

H|H—C—H|H

H|H—C—H|H—C—H|H

H|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷第一章 排列與組合1.4全排列的生成算法

就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。全排列的生成算法有許多種，我們僅介紹其中一種--序數(shù)法第一章 排列與組合1.4.1全排列的生成--序數(shù)法任一自然數(shù)n都可以唯一確定一個(gè)p進(jìn)制數(shù),反之也然。類似地，有第一章 排列與組合同理所以即第一章 排列與組合不難證明，從0到n!-1的任一個(gè)整數(shù)m都可唯一地表示為：所以從0到n!-1的n!個(gè)整數(shù)與滿足上式的序列(an-1,an-2,…a2,a1)一一對(duì)應(yīng)。然后我們?cè)購(gòu)?an-1,an-2,…a2,a1)建立與全排列的一一對(duì)應(yīng)關(guān)系。第一章 排列與組合例：m＝4000，即n1＝4000第一章 排列與組合現(xiàn)從序列(an-1,an-2,…a2,a1)得到生成排列，為了方便起見,不妨今n個(gè)對(duì)象分別是1,2,…n.建立起對(duì)應(yīng)的規(guī)則如下：設(shè)序列(an-1,an-2,…a2,a1)對(duì)應(yīng)某個(gè)排列(p)=p1p2,…,pn，其中ai可以看作是排列(p)中數(shù)i+1所在位置后面比i+1小的數(shù)的個(gè)數(shù)，也就是排列(p)中從數(shù)i+1開始向右統(tǒng)計(jì)小于或等于i的數(shù)的個(gè)數(shù)。第一章 排列與組合以排列4213為例，4后面比它小的數(shù)的個(gè)數(shù)(即a3)為3;3后面比它小的數(shù)的個(gè)數(shù)(即a2)等于0;2后面比它小的數(shù)的個(gè)數(shù)(即a1)為1；排列中比1小的數(shù)是沒有的．故得(p)=(4213)←→(a3a2a1)＝(301)我們稱a3a2a1為中介數(shù)。第一章 排列與組合1.5組合的生成算法組合的生成不如排列生成困難．今以從1、2、3、4、5、6取3個(gè)的組合為例:(1)123，(2)124，(3)125，(4)126，

(5)134，(6)135，(7)136，(8)145，

(9)146，(10)156，(11)234，(12)235，(13)236，(14)245，(15)246，(16)256，(17)345，(18)346，(19)356，(20)456．第一章 排列與組合

從中可得規(guī)律：（1）最后一位數(shù)最大可達(dá)n，倒數(shù)第2位最大可達(dá)n-1，…，依此類推倒數(shù)第k位(k≤r)不得超過n-k+1．若r個(gè)元素的組合用c1c2…cr來(lái)表示，不妨假定c1<c2<…<cr

其中ck＜n-r+k

，k＝1,2,…,r。(2)當(dāng)存在cj＜n-r+j時(shí)，其中下標(biāo)的最大者設(shè)為i，即i＝max{j|cj

＜n-r+j}，則作ci←ci+1。與之相應(yīng)地作ci+1←ci+1，ci+2←ci+1+1，…，cr←cr-1+1第一章 排列與組合于是我們可得到一般的算法：(1)求滿足不等式ci＜n-r+i的最大的下標(biāo)i，即i＝max{j|cj＜n-r+j}，(2)ci←ci+1。(3)從i+1位開始途徑修改：cj←cj-1+1，j=i+1,i+2,…r大家可以思考，從n個(gè)不同元中選r個(gè)的可重組合的生成？第一章 排列與組合1.6若干等式及其組合意義組合意義或組合證明:含意強(qiáng)弱的不同。承認(rèn)組合證明與其他證明有相同的“合法性”。1.C(n,r)=C(n,n-r)

(1.6.1)※從[1,n]去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。第一章 排列與組合2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.6.2)※從[1,n]取a1,a2,…,ar.設(shè)1≤a1＜a2＜…＜ar≤n,對(duì)取法分類： a1=1,有C(n-1,r-1)種方案

a1>1,有C(n-1,r)種方案 共有C(n-1,r)+C(n-1,r-1)中方案，第一章 排列與組合3.(

)+()+()+…+()=()(1.6.3)nn+1n+2n+rn+r+1nnnnra1=2,a2…an+1取自[3,n+r+1]有()種取法n+r-1n………a1=r,a2…an+1取自[r+1,n+r+1]有()種取法n+1n也可看做按含1不含1，含2不含2,…,含r不含r的不斷分類※[1]可從(6.2)推論，也可做一下組合證明從[1,n+r+1]取a1a2…anan+1，設(shè)a1＜a2＜…＜an

＜an+1，可按a1的取值分類：a1=1,2,3,…r,r+1.a1=r+1,a2…an+1取自[r+2,n+r+1]有()種取法nnn+rna1=1,a2…an+1取自[2,n+r+1]有()種取法第一章 排列與組合①選政治局,再選常委,n個(gè)中央委員選出l名政治局委員,再?gòu)钠渲羞x出r名常委②選常委,再選非常委政治局委員兩種選法都無(wú)遺漏,無(wú)重復(fù)地給出可能的方案，應(yīng)該相等。nlnn-rlrrl-r4.()()=()()(1.6.4)第一章 排列與組合mkm-k

mmkk=0證1(x+y)

=∑(

)x

y,令x=y=1,得(1.6.5)5.()+()+…+()=2,m≥0,(1.6.5)mmmm01m組合證

[1,m]的所有方案.每一元素都可取或不取兩種狀態(tài)，由乘法原理可知所有狀態(tài)數(shù)為2m.

而這些可分解為從m個(gè)元素中分別取0個(gè),1個(gè)，2個(gè)，…，m個(gè)組合的總和。第一章 排列與組合例某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有７人，每人持若干鑰匙。須４人到場(chǎng)，所備鑰匙才能開鎖。問①至少有多少把不同的鑰匙？②每人至少持幾把鑰匙？解①每３人至少缺１把鑰匙，且每３人所缺鑰匙不同。故至少共有()=35把不同的鑰匙。73任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖。故每人至少持(

)＝20把不同的鑰匙。６３一般地某保密裝置安裝了一個(gè)電子鎖.須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有n人，每人有一把鑰匙。必須m人(m<n)到場(chǎng)，才能用鑰匙開鎖。問怎么分配鎖的特征和每個(gè)的鑰匙上的特征?

既然鎖比任意m-1把鑰匙多一個(gè)特征，而任意兩個(gè)m-1把鑰匙組