組合數(shù)學(xué)第一章3學(xué)習(xí)資料

復(fù)習(xí)題有8人圍圓桌就餐，問有多少種就座方式？如果有兩人不愿坐在一起，又有多少種就座方式？例某車站有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種選擇。

故所求方案為14!/5!=726485760引例在100名選手之間進(jìn)行淘汰賽（即一場(chǎng)的比賽結(jié)果，失敗者退出比賽），最后產(chǎn)生一名冠軍，問要舉行幾場(chǎng)比賽？證明：第1輪要進(jìn)行50場(chǎng)比賽，留下50名選手；第2輪要進(jìn)行25場(chǎng)比賽，留下25名選手；第3輪要進(jìn)行25場(chǎng)比賽，1名輪空，留下13名選手；第4輪要進(jìn)行6場(chǎng)比賽，1名輪空，留下7名選手；第5輪要進(jìn)行3場(chǎng)比賽，1名輪空，留下4名選手；第6輪要進(jìn)行2場(chǎng)比賽，留下2名選手；最后一場(chǎng)決賽，產(chǎn)生1名冠軍。根據(jù)加法法則，共需要進(jìn)行50+25+12+6+3+2+1=99場(chǎng)比賽。其實(shí)，最后產(chǎn)生1名冠軍需要淘汰99人，一場(chǎng)比賽淘汰1人，兩者一一對(duì)應(yīng)，需要99場(chǎng)比賽進(jìn)行。1.3模型轉(zhuǎn)換“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。如我們說A集合有n個(gè)元素|A|=n，無非是建立了將A中元與[1,n]元一一對(duì)應(yīng)的關(guān)系。在組合計(jì)數(shù)時(shí)往往借助于一一對(duì)應(yīng)實(shí)現(xiàn)模型轉(zhuǎn)換。1.3模型轉(zhuǎn)換例

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.3模型轉(zhuǎn)換

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.1.3模型轉(zhuǎn)換例(Cayley定理)n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹的數(shù)目等于n。n-2生長(zhǎng)點(diǎn)不是葉子,每個(gè)生長(zhǎng)點(diǎn)是[1,n]中的任一元.有n種選擇。兩個(gè)頂點(diǎn)的樹是唯一的。1.3模型轉(zhuǎn)換⑦⑥||②—③—①—⑤—④41253逐個(gè)摘去標(biāo)號(hào)最小的葉子，葉子的相鄰頂點(diǎn)(不是葉子，是內(nèi)點(diǎn))形成一個(gè)序列，序列的長(zhǎng)度為n-2例給定一棵有標(biāo)號(hào)的樹邊上的標(biāo)號(hào)表示摘去葉的順序。(摘去一個(gè)葉子相應(yīng)去掉一條邊)第一次摘掉②，③為②相鄰的頂點(diǎn)，得到序列的第一個(gè)數(shù)3以此類推，得到序列31551,長(zhǎng)度為7－2=5這是由樹形成序列的過程。1.4模型轉(zhuǎn)換由序列形成樹的過程：由序列31551得到一個(gè)新序列111233455567生成的過程是首先將31551排序得到11355，因?yàn)樾蛄?1551的長(zhǎng)度為5，得到按升序排序的序列1234567，序列的長(zhǎng)度為5+2(即n+2)，然后將11355按照大小插入到序列1234567中，得到111233455567然后將兩個(gè)序列排在一起315511112334555671.4模型轉(zhuǎn)換

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推導(dǎo)：將上下兩個(gè)序列同時(shí)去掉上行序列的第一個(gè)元素3(用黃色表示)，去掉下行序列的第一個(gè)無重復(fù)的元素2(用紅色表示)。生成一條邊(②—③)。依此類推，減到下面剩最后兩個(gè)元素，這兩個(gè)元素形成最后一條邊。最后形成樹。1.3模型轉(zhuǎn)換上述算法描述：給定序列b=(b1b2…bn-2)設(shè)a=(123…n-1n)將b的各位插入a,得a’,對(duì)()做操作。a’是2n-2個(gè)元的可重非減序列。ba’操作是從a’中去掉最小無重元，設(shè)為a1,再?gòu)腷和a’中各去掉一個(gè)b中的第一個(gè)元素，設(shè)為b1，則無序?qū)?a1,b1)是一條邊。重復(fù)這一操作，得n-2條邊，最后a’中還剩一條邊，共n-1條邊，正好構(gòu)成一個(gè)樹。b中每去掉一個(gè)元，a’中去掉2個(gè)元。1.3模型轉(zhuǎn)換由算法知由樹T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一對(duì)應(yīng)。由序列確定的長(zhǎng)邊過程是不會(huì)形成回路的。因任意長(zhǎng)出的邊(u,v)若屬于某回路，此回路中必有一條最早生成的邊，不妨就設(shè)為(u,v)，必須使u,v都在長(zhǎng)出的邊中重復(fù)出現(xiàn)，但照算法u,v之一從下行消失，不妨設(shè)為u，從而不可能再生成與u有關(guān)的邊了，故由()得到的邊必構(gòu)成一個(gè)n個(gè)頂點(diǎn)的樹。ba’1.3模型轉(zhuǎn)換例簡(jiǎn)單格路問題|(0,0)→(m,n)|=()從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少條路徑？m+nmy(m,n)...0...x1.3模型轉(zhuǎn)換無論怎樣走法，在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元的無重全排列。1.3模型轉(zhuǎn)換設(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)設(shè)c≥a,d≥b,則由(a,b)到(c,d)的簡(jiǎn)單格路數(shù)為|(a,b)(c,d)|=()(m+n)!m+nm+nm!n!mn(c-a)+(d-b)c-a(c,d)(a,b)1.3模型轉(zhuǎn)換例在上例的基礎(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)的格路。1.3模型轉(zhuǎn)換容易看出從(0,1)到(m,n)接觸x=y的格路與(1,0)到(m,n)的格路(必穿過x=y)一一對(duì)應(yīng)yy=x(m,n)0(1,0)x(0,1)..yx-y=1(m,n)x(0,0)(1,-1).....1.3模型轉(zhuǎn)換故所求格路數(shù)為()－()=———－———=————(—－—)=——()=(1－—)()=——()m+n-1m+n-1mm-1(m+n-1)!(m+n-1)!(m+n-1)!11m!(n-1)!(m-1)!n!(m-1)!(n-1)!mnm+n-1m+n-1mm

n-mmnnm+n-1m

n-mn1.3模型轉(zhuǎn)換若條件改為可接觸但不可穿過，則限制線要向下或向右移一格，得x－