組合數(shù)學(xué)第一章

組合數(shù)學(xué)第一章第一頁(yè)，共一百四十二頁(yè)，2022年，8月28日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è)，共一百四十二頁(yè)，2022年，8月28日1.1

加法法則與乘法法則[例]北京每天直達(dá)上海的客車有5次，客機(jī)有3次，則每天由北京直達(dá)上海的旅行方式有5+3=8種。第三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1

加法法則與乘法法則[乘法法則] 設(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。第四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1

加法法則與乘法法則[例]某種字符串由兩個(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è)，共一百四十二頁(yè)，2022年，8月28日1.1

加法法則與乘法法則例某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是44=16，而只有43=12種。[要注意題目中隱含的條件或約束]在乘法法則中要注意事件A和事件B的相互獨(dú)立性。第六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1

加法法則與乘法法則例

n=73×112×134，求除盡n的整數(shù)個(gè)數(shù)。第七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1應(yīng)用舉例例某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開(kāi)。現(xiàn)有７人，每人持若干鑰匙。須４人到場(chǎng)，所備鑰匙才能開(kāi)鎖。問(wèn)①至少有多少把不同的鑰匙？②每人至少持幾把鑰匙？解①每３人至少缺１把鑰匙，且每３人所缺鑰匙不同。故至少共有()=35把不同的鑰匙。73第八頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1應(yīng)用舉例任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開(kāi)鎖。故每人至少持(

)＝20把不同的鑰匙。為加深理解，舉一個(gè)較簡(jiǎn)單的例子：４人中３人到場(chǎng)，所求如上。共有(

)=6把不同的鑰匙。每人有(

)=3把鑰匙。（見(jiàn)下頁(yè)圖）６３４２３２第九頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.1應(yīng)用舉例鑰匙１２３４５６

A√√√人B√√√C√√√D√√√第十頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2一一對(duì)應(yīng)例在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問(wèn)要舉行幾場(chǎng)比賽？解

一種常見(jiàn)的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。第十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2一一對(duì)應(yīng)例

(Cayley定理)n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹(shù)的數(shù)目等于n。n-2第十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2一一對(duì)應(yīng)⑦⑥||②—③—①—⑤—④41253逐個(gè)摘去標(biāo)號(hào)最小的葉子，葉子的相鄰頂點(diǎn)(不是葉子，是內(nèi)點(diǎn))形成一個(gè)序列，序列的長(zhǎng)度為n-2例給定一棵有標(biāo)號(hào)的樹(shù)邊上的標(biāo)號(hào)表示摘去葉的順序。(摘去一個(gè)葉子相應(yīng)去掉一條邊)第一次摘掉②，③為②相鄰的頂點(diǎn)，得到序列的第一個(gè)數(shù)3以此類推，得到序列31551,長(zhǎng)度為7－2=5這是由樹(shù)形成序列的過(guò)程。第十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日排列與組合定義從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無(wú)重排列。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r=n時(shí)稱為全排列。一般不說(shuō)可重即無(wú)重。第十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日排列與組合定義從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合。組合的個(gè)數(shù)用C(n,r)表示，

第十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日排列組合舉例例把八位同學(xué)分成四組，每組兩人，有多少種方案？第十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日排列組合舉例例某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？第一個(gè)人可以有6種進(jìn)站的方式，也就是從6個(gè)入口的任意一個(gè)站進(jìn)站，那么第二個(gè)人也可以有6種選擇入口的方法，但是假如他和第一個(gè)人選擇的入口是相同的話，就有誰(shuí)在前的情況，所以第二個(gè)人就有了7種進(jìn)站方案；同理，第三個(gè)人進(jìn)站的話就有8種進(jìn)站方案，這樣算下去，那么第九個(gè)人就有14種進(jìn)站的方法。根據(jù)乘法原理，這9個(gè)人的進(jìn)站方案共有：6×7×8×...×14=726485720種。

第十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日?qǐng)A周排列在一圓周上討論排列問(wèn)題，即將一排列排到一圓周上，稱之為圓周排列問(wèn)題。n個(gè)元素的r圓周排列方案數(shù)：Q(n,r)=P(n,r)/r第十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日?qǐng)A周排列例5個(gè)男生，3個(gè)女生圍一桌而坐，若要求男生B1不和女生G1相鄰而坐，有多少種方案？若要求女生不相鄰，又有多少種方案？第十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日?qǐng)A周排列例有12對(duì)夫妻平分為兩桌，圍圓桌而坐，問(wèn)共有幾種方案？第二十頁(yè)，共一百四十二頁(yè)，2022年，8月28日售票問(wèn)題某場(chǎng)電影的票價(jià)為50元，如果某窗口排隊(duì)的購(gòu)票者中，分別有n和m位手持50元和100元面值。問(wèn)該窗口能正常完成售票（即不出現(xiàn)沒(méi)錢找零的情形）的概率是多少？第二十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的排列多重集是元素可多次出現(xiàn)的集合，通常把含有k中不同元素的多重集S記作

{n1?a1,n2?a2,…,nk?ak}第二十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的排列設(shè)多重集S={n1?a1,n2?a2,…,nk?ak}，且對(duì)i=1,2,…k，都有ni≥r，則S的r-排列數(shù)為kr.例：求不多于四位的二進(jìn)制數(shù)的個(gè)數(shù)解：24=16第二十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的排列設(shè)多重集S={n1?a1,n2?a2,…,nk?ak}，且有n=n1+n2+…+nk，則S的排列數(shù)為

第二十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的排列例：用兩面紅旗，三面黃旗依次懸掛在一根旗桿上，問(wèn)可以組成多少種不同的標(biāo)志？解：N=(5!)/(2!3!)=10.第二十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的組合設(shè)多重集S={n1?a1,n2?a2,…,nk?ak}，且對(duì)i=1,2,…k，都有ni≥r，則S的r-組合數(shù)為C(k+r-1,r).證明：一一對(duì)應(yīng)法第二十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日多重集的組合例：試問(wèn)(x+y+z)4有多少項(xiàng)？解：(x+y+z)4

=(x+y+z)(x+y+z)(x+y+z)(x+y+z)相當(dāng)于多重集{4?x,4?y4?z}的4-組合，于是N=C(3+4-1,4)=15.第二十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日不相鄰的組合所謂不相鄰的組合，是指從A={1,2,…,n}取r個(gè)不相鄰的數(shù)的組合，即不存在含有相鄰兩個(gè)數(shù)j和j+1的組合。例如，對(duì)n=7,r=3,有組合{1,3,5},{1,3,6},{1,3,7},{1,4,6},{1,4,7},{1,5,7},{2,4,6},{2,4,7},{2,5,7},{3,5,7}第二十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日不相鄰的組合定理：從A={1,2,…,n}中取r個(gè)作不相鄰的組合，其組合數(shù)為C(n-r+1,r)。證明：一一對(duì)應(yīng)法第二十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日線性方程整數(shù)解的個(gè)數(shù)問(wèn)題已知線性方程x1+x2+…+xn=b，n和b都是整數(shù)，求此方程的非負(fù)整數(shù)解的個(gè)數(shù)。定理：上述方程非負(fù)整數(shù)解的個(gè)數(shù)為C(n+b-1，b)第三十頁(yè)，共一百四十二頁(yè)，2022年，8月28日組合意義的解釋例：從(0,0)到(m,n)的最短路徑的數(shù)量。例：C(n,r)=C(n,n-r)例：C(n,r)=C(n-1,r)+C(n-1,r-1)第三十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日組合意義的解釋例(楊輝三角)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)第三十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日組合意義的解釋例：

C(n,l)C(l,r)=C(n,r)C(n-r,l-r)(l≥r)第三十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日組合意義的解釋例：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)第三十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日2)“含0”和“含1”不可直接套用。0019含1但不含0。在組合的習(xí)題中有許多類似的隱含的規(guī)定，要特別留神。不含0的1位數(shù)有9個(gè)，2位數(shù)有9個(gè)，3位數(shù)有9個(gè)，4位數(shù)有9個(gè)不含0小于10000的正整數(shù)有9+9+9+9=(9－1)/(9－1)=7380個(gè)含0小于10000的正整數(shù)有9999－7380=2619個(gè)2342345第三十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合定義從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無(wú)重排列。排列的全體組成的集合用P(n,r)表示。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r=n時(shí)稱為全排列。一般不說(shuō)可重即無(wú)重。可重排列的相應(yīng)記號(hào)為

-P(n,r),P(n,r)。l第三十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合定義從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合。組合的全體組成的集合用C(n,r)表示，組合的個(gè)數(shù)用C(n,r)表示，對(duì)應(yīng)于可重組合

-有記號(hào)C(n,r),C(n,r)。第三十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合從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記n(n-1)······(n-r+1)第三十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合若球不同，盒子相同，則是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。故有

C(n,r)·r!=P(n,r),C(n,r)=P(n,r)/r!=[n]r/r!=(

)=易見(jiàn)P(n,r)=nnrr

n!———r!(n-r)!第三十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合例有5本不同的日文書(shū)，7本不同的英文書(shū)，10本不同的中文書(shū)。1)取2本不同文字的書(shū)；2)取2本相同文字的書(shū)；3)任取兩本書(shū)第四十頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合解

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第四十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合例從[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)+100=485100+1000000=14851003第四十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合例某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？其中“0”表示人，“1”表示門框，其中“0”是不同元，“1”是相同元。給“1”n個(gè)門只用n-1個(gè)門框。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。第四十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合[解法1]標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。故若設(shè)x為所求方案，則

x·5!=14!∴x=14!/5!=726485760第四十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合[解法2]在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，在確定人的位置，有9！種選擇。故C(14,5)·9!即所求第四十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.2排列與組合[解法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種選擇。

9故所求方案為[6]第四十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式組合計(jì)數(shù)的漸進(jìn)值問(wèn)題是組合論的一個(gè)研究方向。Stirling公式給出一個(gè)求n!的近似公式，它對(duì)從事計(jì)算和理論分析都是有意義的。第四十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式1)Wallis公式令I(lǐng)k=∫sinxdx.顯然I0=,I1=1.k≥2時(shí)，Ik=－cosxsinx|+∫(k－1)cosxsinxdx=0+(k－1)∫(1－sinx)sinxdx=(k－1)(Ik－2－Ik)kπ－

2k-1π－20π－20π－20π－202k-22k-2故

Ik=——Ik-2(1-3-1)k-1k第四十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式令n!!=1·3·5·…·(n-2)·n，n是奇數(shù)。2·4·6·…·(n-2)·n，n是偶數(shù)。(1-3-2)由(1-3-1)，———I1,k是奇數(shù)

Ik=———I0,k是偶數(shù)(k-1)!!k!!(k-1)!!k!!當(dāng)x∈(0,π/2)時(shí)，sinx<sinx因而I2k+1<I2k<I2k-1,k=1,2,…。k+1k第四十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式由(1-3-2)————<————·—<————，(2k)!!(2k-1)!!π(2k-2)!!(2k+1)!!(2k)!!2(2k-1)!!1<——————<——1.π—2[——](2k)!!(2k-1)!!1·——2k+12k+12k2k→∞第五十頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式所以lim=,(2k)!!(2k-1)!!1·——2k+12[——]π—2k→∞lim

=,(2k)!!(2k)!!(2k)!1·——2k+12[————]π—2k→∞lim=。(1-10-3)2(k!)(2k)!1·——2k+12[——]π—2k→∞2k2第五十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式2)stirling公式y(tǒng)y=lnx

0123n-1nx第五十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式令A(yù)n=∫lnxdx=xlnx|－∫dx=nlnn－n+1

(1-3-4)tn=－ln1+ln2+…+ln(n－1)+－lnn =ln(n!)－－lnn(1-3-5)tn的幾何意義是由x軸,x=n,以及連接(1,0),(2,ln2),…,(n－1,ln(n－1)),(n,lnn)諸點(diǎn)而成的折線圍成的面積。nnn111112 212第五十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式Tn=－+ln2+…+ln(n－1)+－lnn(1-3-6)1182Tn是由三部分面積之和構(gòu)成的。一是曲線y=lnx在x=k點(diǎn)的切線和x軸，以及x=k－－,x=k－－包圍的梯形，當(dāng)k分別為2,3,…,n-1時(shí)的面積之和；一是由y=lnx在x=1點(diǎn)的切線，x=3/2線，以及x軸圍城的梯形；另一是由y=lnn,x=n－－,x=n及x軸包圍的矩形面積。因而有

tn<An<Tn

(1-3-7)121212第五十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式令bn=An

－tn.序列b1,b2,…是單調(diào)增，而且有上界，故有極限，令limbn=b1由(1-3-4),(1-3-5)得 bn=nlnn－n+1－ln(n!)+－lnn

=

lnn－n+1－ln(n!)+－lnn

ln(n!)=1－bn+lnn－lnn

－lne∴n!=en(－)

(1-3-8)0<An－tn<Tn－tn=－18n→∞12n√√nn1-bn√nen第五十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.3Stirling近似公式令βn=e,limβn=β.將(1-3-8)代入(1-3-3),整理得 β=2π.所以 n!~2πn(－)n→∞1-bn√√nen第五十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。如我們說(shuō)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)。第五十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換例簡(jiǎn)單格路問(wèn)題|(0,0)→(m,n)|=()從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少條路徑？m+nmy(m,n)...0...x第五十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換無(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ú)重全排列。第五十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(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)第六十頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換例在上例的基礎(chǔ)上若設(shè)m<n，求(0,1)點(diǎn)到(m,n)點(diǎn)不接觸對(duì)角線x=y的格路的數(shù)目(“接觸”包括“穿過(guò)”)從(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)的格路。第六十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換容易看出從(0,1)到(m,n)接觸x=y的格路與(1,0)到(m,n)的格路(必穿過(guò)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).....第六十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(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-mn第六十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換若條件改為可接觸但不可穿過(guò)，則限制線要向下或向右移一格，得x－y=1，(0,0)關(guān)于x－y=1的對(duì)稱點(diǎn)為(1,-1).所求格路數(shù)為()－()=——－————=———()m+nm+nmm-1(m+n)!(m+n)!n+1-mm!n!(m-1)!(n+1)!

n+1m+nm格路也是一種常用模型第六十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(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丙烷第六十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(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異丁烷這說(shuō)明對(duì)應(yīng)CnH2n+2的枝鏈?zhǔn)怯?n+2個(gè)頂點(diǎn)的一棵樹(shù)，其中n個(gè)頂點(diǎn)與之關(guān)聯(lián)的邊數(shù)為4；其它2n+2個(gè)頂點(diǎn)是葉子。對(duì)于這樣結(jié)構(gòu)的每一棵樹(shù)，就對(duì)應(yīng)有一種特定的化合物。從而可以通過(guò)研究具有上述性質(zhì)的樹(shù)找到不同的碳?xì)浠衔顲nH2n+2.第六十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換例在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問(wèn)要舉行幾場(chǎng)比賽？解

一種常見(jiàn)的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。第六十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換例

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

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推導(dǎo)：將上下兩個(gè)序列同時(shí)去掉上行序列的第一個(gè)元素3(用黃色表示)，去掉下行序列的第一個(gè)無(wú)重復(fù)的元素2(用紅色表示)。生成一條邊(②—③)。依此類推，減到下面剩最后兩個(gè)元素，這兩個(gè)元素形成最后一條邊。最后形成樹(shù)。第七十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換上述算法描述：給定序列b=(b1b2…bn-2)設(shè)a=(123…n-1n)將b的各位插入a,得a’,對(duì)()做操作。a’是2n-2個(gè)元的可重非減序列。ba’操作是從a’中去掉最小無(wú)重元，設(shè)為a1,再?gòu)腷和a’中各去掉一個(gè)b中的第一個(gè)元素，設(shè)為b1，則無(wú)序?qū)?a1,b1)是一條邊。重復(fù)這一操作，得n-2條邊，最后a’中還剩一條邊，共n-1條邊，正好構(gòu)成一個(gè)樹(shù)。b中每去掉一個(gè)元，a’中去掉2個(gè)元。第七十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換由算法知由樹(shù)T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一對(duì)應(yīng)。由序列確定的長(zhǎng)邊過(guò)程是不會(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)的樹(shù)。ba’第七十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.4模型轉(zhuǎn)換證由一棵n個(gè)頂點(diǎn)的樹(shù)可得到一個(gè)長(zhǎng)度為n－2的序列，且不同的樹(shù)對(duì)應(yīng)的序列不同*，因此|T

|≤n。*對(duì)n用歸納法可證反之，由一個(gè)長(zhǎng)度為n－2的序列(每個(gè)元素為1~n的一個(gè)整數(shù))，可得到一棵樹(shù)，且不同的序列對(duì)應(yīng)的樹(shù)是不同的，因此 n≤|T||T|=n#n-2n-2n-2第七十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.5全排列的生成算法

就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。全排列的生成算法第七十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.5全排列的生成算法這里介紹全排列算法四種：(A)字典序法(B)遞增進(jìn)位制數(shù)法(C)遞減進(jìn)位制數(shù)法(D)鄰位對(duì)換法第七十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法

對(duì)給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后。第七十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法[例]字符集{1,2,3},較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321?！?/p>

一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。第七十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法1）生成給定全排列的下一個(gè)排列所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒(méi)有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。第七十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒(méi)有下一個(gè)了。否則找出第一次出現(xiàn)下降的位置。第八十頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法求839647521的下一個(gè)排列7521

74＜7

4<5

5

4>2

2

4>1

1

在后綴7521中找出比4大的數(shù)75找出其中比4大的最小數(shù)55

4、5

對(duì)換8396

72154后綴變?yōu)?421將此后綴翻轉(zhuǎn)1247接上前綴83965得到839651247即839647521的下一個(gè)。[例]為后綴大于4的用橙色表示小于4的用綠色表示

找出比右邊數(shù)字小的第一個(gè)數(shù)4第八十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法在[1,n]的全排列中,nn-1…321是最后一個(gè)排列,其中介數(shù)是(n-1,n-2,...,3,2,1)其序號(hào)為n-1∑k×k!k=1另一方面可直接看出其序號(hào)為n!-1

n-1n-1于是n!-1=∑k×k!

即

n!=∑k×k!+1

k=1k=1第八十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法一般而言，設(shè)P是[1,n]的一個(gè)全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i|Pi<Pi+1},k=max{i|Pi>Pj}對(duì)換Pj，Pk，將Pj+1…Pk-1PjPk+1…Pn翻轉(zhuǎn)，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個(gè)第八十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法2)計(jì)算給定排列的序號(hào)839647521的序號(hào)即先于此排列的排列的個(gè)數(shù)。將先于此排列的排列按前綴分類。前綴先于8的排列的個(gè)數(shù)：7×8!第一位是8,先于83得的排列的個(gè)數(shù)：2×7!前2位是83,先于839得的排列的個(gè)數(shù)：6×6!先于此排列的的排列的個(gè)數(shù)：7×8!+2×7!+6×6!前3位是839,先于8396得的排列的個(gè)數(shù)：4×5!+4×5!前4位是8396,先于83964得的排列的個(gè)數(shù)：2×4!+2×4!前5位是83964,先于839647得的排列的個(gè)數(shù)：3×3!+3×3!前6位是839647,先于8396475得的排列的個(gè)數(shù)：2×2!+2×2!前7位是8396475,先于83964752得的排列的個(gè)數(shù)：1×1!+1×1!297191前8位固定，則最后一位也隨之固定將8!,7!,…,1!前面的系數(shù)抽出，放在一起得到72642321此數(shù)的特點(diǎn)：

7：8的右邊比8小的數(shù)的個(gè)數(shù)2：3的右邊比3小的數(shù)的個(gè)數(shù)6：9的右邊比9小的數(shù)的個(gè)數(shù)4：6的右邊比6小的數(shù)的個(gè)數(shù)2：4的右邊比4小的數(shù)的個(gè)數(shù)3：7的右邊比7小的數(shù)的個(gè)數(shù)2：5的右邊比5小的數(shù)的個(gè)數(shù)1：2的右邊比2小的數(shù)的個(gè)數(shù)72642321是計(jì)算排列839647521的序號(hào)的中間環(huán)節(jié)，我們稱之為中介數(shù)。※這是一個(gè)很有用的概念。第八十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法一般而言,對(duì)于[1,9]的全排列中介數(shù)首位的取值為0—8，第2位的取值為0—7，以此類推，第8位的取值為0、1。從而序號(hào)可表示為：

n-1∑ki(n-i)!i=1ki：Pi的右邊比Pi小的數(shù)的個(gè)數(shù)i=1,2,…,n-1第八十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法由中介數(shù)推出排列的算法[例]由72642321推算出839647521方法1：P1P2P3P4P5P6P7P8P9_________P1=88→7+1=82+1=3→P2=336+1=7，但3已在P3左邊出現(xiàn)，↑7+1=8，但8已在P3左邊出現(xiàn)，↑8+1=9→P3=994+1=5，但3已經(jīng)在P4左邊出現(xiàn)，5+1=6→P4=66↑2+1=3，但3已經(jīng)在P5左邊出現(xiàn)，3+1=4→P4=443+1=4，但3,4已經(jīng)在P6左邊出現(xiàn)，4+1+1=6，但6已經(jīng)在P6左邊出現(xiàn)，

6+1=7→P6=772+1=3，但3已經(jīng)在P7左邊出現(xiàn)，3+1=4，但4已經(jīng)在P7左邊出現(xiàn)，

4+1=5→P7=551+1=2→P8=2

→P9=121這個(gè)過(guò)程比較麻煩(這醞釀著改進(jìn)的可能)，該算法從左到右依次推出P1,P2,…,P9。下述算法依次定出1,2,3,…,9的位置。第八十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法方法2-1：72642321中未出現(xiàn)0，1在最右邊中介數(shù)右端加一個(gè)0擴(kuò)成9位，先定1，每定一位，其左邊未定位下加一點(diǎn)，從（位－位下點(diǎn)數(shù)=0）的位中選最左的。726423210定1的位置1●●●●●●●●22●●●●●●●33●44●●●55●●●●66●●77●●8899由72642321推算出839647521第八十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日字典序法方法2-2：已定出上標(biāo)‘●’，找左起第一個(gè)0，下標(biāo)‘__’由72642321推算出839647521

●72642321-11111111=61531210________12

●●●●61531210-11111110=504201003●●●●50420100-10000000=404201004●●●●●40420100-10110000=303101005●●●●●●●●30310100-10110100=202000006●●●●●●●●●●20200000-10100000=101000007●●●●●●●●●●●●10100000-10100000=000000008●●●●●●●000000009以上兩種從中介數(shù)求排列的算法都比較麻煩。給定一排列與下一個(gè)排列各自的中介數(shù)→進(jìn)位鏈（中介數(shù)的后繼）→遞增進(jìn)位制數(shù)第八十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法1)由排列求中介數(shù)在字典序法中，中介數(shù)的各位是由排列數(shù)的位決定的.中介數(shù)位的下標(biāo)與排列的位的下標(biāo)一致。

在遞增進(jìn)位制數(shù)法中，中介數(shù)的各位是由排列中的數(shù)字決定的。即中介數(shù)中各位的下標(biāo)與排列中的數(shù)字(2—n)一致。第八十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法可看出n-1位的進(jìn)位鏈。右端位逢2進(jìn)1，右起第2位逢3進(jìn)1，…，右起第i位逢i+1進(jìn)1，i=1,2,…,n-1.這樣的中介數(shù)我們稱為遞增進(jìn)位制數(shù)。上面是由中介數(shù)求排列。第九十頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法由序號(hào)（十進(jìn)制數(shù)）求中介數(shù)（遞增進(jìn)位制數(shù)）如下：

m=m1,0≤m≤n!-1m1=2m2+kn-1,0≤kn-1≤1m2=3m3+kn-2,0≤kn-2≤2

…………….

mn-2=(n-1)mn-1+k2,0≤k2≤n-2mn-1=k1,0≤k1≤n-1

p1p2…pn←→(k1k2…kn-1)↑←→m第九十一頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法在字典序法中由中介數(shù)求排列比較麻煩，我們可以通過(guò)另外定義遞增進(jìn)位制數(shù)加以改進(jìn)。為方便起見(jiàn)，令ai+1=kn-I，i=1,2,…,n-1(k1k2…kn-1)↑=(anan-1…a2)↑ai：i的右邊比i小的數(shù)字的個(gè)數(shù)第九十二頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法在這樣的定義下，有839647521←→(67342221)↑(67342221)↑+1=(67342300)↑←→8496175236×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1=279905第九十三頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法由(anan-1…a2)↑求p1p2…pn。從大到小求出n,n-1,…,2,1的位置_..._n__…_

an個(gè)空格n的右邊有an個(gè)空格。n-1的右邊有an-1個(gè)空格?！?的右邊有a2個(gè)空格。最后一個(gè)空格就是1的位置。\____________/

V第九十四頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞增進(jìn)位制數(shù)法_________

67342221↓↓↓↓↓↓↓↓

a9a8a7a6a5a4a3a2★\____________________/

V

6個(gè)空格9★\____________________________/

V

7個(gè)空格8★★★★★★\________/

V

3個(gè)空格765431\________________/

V

4個(gè)空格\____/

V

2個(gè)空格1個(gè)空格

序號(hào)

nm=∑ak(k-1)!

k=22第九十五頁(yè)，共一百四十二頁(yè)，2022年，8月28日遞減進(jìn)位制數(shù)法在遞增進(jìn)位制數(shù)法中，中介數(shù)的最低位是逢2進(jìn)1，進(jìn)位頻繁，這是一個(gè)缺點(diǎn)。把遞增進(jìn)位制數(shù)翻轉(zhuǎn),就得到遞減進(jìn)位制數(shù)。(anan-1…a2)↑→(a2a3…an-1an)↓839647521→(12224376)↓

nnm=∑akn!/k!=n!∑ak/k!

k=2k=2(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989

※※

求下一個(gè)排列十分容易第九十六頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法遞減進(jìn)位制數(shù)法的中介數(shù)進(jìn)位不頻繁，求下一個(gè)排列在不進(jìn)位的情況下很容易。這就啟發(fā)我們，能不能設(shè)計(jì)一種算法，下一個(gè)排列總是上一個(gè)排列某相鄰兩位對(duì)換得到的。遞減進(jìn)位制數(shù)字的換位是單向的，從右向左，而鄰位對(duì)換法的換位是雙向的。第九十七頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法這個(gè)算法可描述如下：對(duì)1—n-1的每一個(gè)偶排列，n從右到左插入n個(gè)空檔(包括兩端)，生成1—n的n個(gè)排列。對(duì)1—n-1的每一個(gè)奇排列，n從左到右插入n個(gè)空檔，生成1—n的n個(gè)排列。對(duì)[2,n]的每個(gè)數(shù)字都是如此。第九十八頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法[例]839647521→836947521●→[解]2的右邊有1個(gè)數(shù)字(奇數(shù))比2小,2上加一個(gè)點(diǎn)。●●3的右邊有2個(gè)數(shù)字(偶數(shù))比3小,3上不加點(diǎn)。4的右邊有2個(gè)數(shù)字(偶數(shù))比4小,4上不加點(diǎn)。5的右邊有2個(gè)數(shù)字(偶數(shù))比5小,5上不加點(diǎn)。6的右邊有2個(gè)數(shù)字(偶數(shù))比6小,6上不加點(diǎn)。7的右邊有3個(gè)數(shù)字(奇數(shù))比7小,7上加一個(gè)點(diǎn)。8的右邊有7個(gè)數(shù)字(奇數(shù))比8小,8上加一個(gè)點(diǎn)。1—8上共有3個(gè)(奇數(shù))點(diǎn)，9上箭頭向右。P=839647521→()↓b2b3b4b5b6b7b8b9101213722上箭頭向左，2右邊有1個(gè)數(shù)字比2小，b2=13上箭頭向右，3左邊有0個(gè)數(shù)字比3小，b3=04上箭頭向右，4左邊有1個(gè)數(shù)字比4小，b4=15上箭頭向右，5左邊有2個(gè)數(shù)字比5小，b5=26上箭頭向右，6左邊有1個(gè)數(shù)字比6小，b6=17上箭頭向左，7右邊有3個(gè)數(shù)字比7小，b7=38上箭頭向左，8右邊有7個(gè)數(shù)字比8小，b8=79上箭頭向右，9左邊有2個(gè)數(shù)字比9小，b9=2839647521的中介數(shù)為10121372←→→→→→→←第九十九頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法ak(p)：p中1—k排列的序號(hào)，ak(p)的奇偶性與1—k排列的奇偶性相同。a9(p)=9×a8(p)+b9(p)=9×(8×a7(p)+b8(p))+b9(p)※※an(p)，bn(p)簡(jiǎn)寫(xiě)成an，bn第一百頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法已知(10121372)↓求排列。9的位置由b9和a8的奇偶性決定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。→←→b8奇→9，b6+b7偶→8，b6奇→7，→→

b4+b5奇→6，b4奇→5第一百零一頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法序號(hào)=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2=203393←→(10121372)↓第一百零二頁(yè)，共一百四十二頁(yè)，2022年，8月28日鄰位對(duì)換法第一百零三頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成設(shè)從[1,n]中取r元的組合全體為C(n,r).C1C2…Cr∈C(n,r).不妨設(shè)C1＜C2＜…＜Cri≤Ci≤(n－r+i),i=1,2,…,r令j=max{i|Ci＜n－r+i}.則C1C2…Cr的下一個(gè)組合為C1C2…Cj-1(Cj+1)(Cj+2)…(Cj+r－j+1)這等于給C(n,r)的元素建立了字典序。12…r的序號(hào)為0，n-r+1n-r+2…n的序號(hào)為()－1____________

nr第一百零四頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成例在C(10,4)中4679的序號(hào)是首位小于4的組合的個(gè)數(shù)；首位是4，第2位小于6的組合的個(gè)數(shù)；前2位是46，第3位小于7的組合的個(gè)數(shù)；前3位是467，第4位小于9的組合的個(gè)數(shù)之和。反之，也可以由序號(hào)求組合。第一百零五頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成A(m,l)：[1,m]的l-組合(或l-子集)。第1個(gè)組合：{1,2,…,l-1,l}.最后1個(gè)組合：{1,2,…,l-1,m}A(n,k)=A(n-1,k)，A(n-1,k-1)○{n}A：將有序集A(或線性表)的順序逆轉(zhuǎn)的有序集。A○n：將A中每個(gè)元素(是集合)都與{n}求并的有序集__×__×____第一百零六頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成例

用兩種方法計(jì)算[1,n]的無(wú)重不相鄰組合C’(n,r)的計(jì)數(shù)問(wèn)題解法1

0…010…010…010…010…0其中不可含11/\——————————————————————/\共n位r個(gè)1\/——————————————\/①以1結(jié)尾：r-1個(gè)10與n-1-2(r-1)個(gè)0的排列

r-1+[n-1-2(r-1)]=n-r這樣的排列有(n-r)!——————=(r-1)!(n-2r+1)!()n-rr-1第一百零七頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成②以0結(jié)尾：r個(gè)10與n-2r個(gè)0的排列r+n-2r=n-r這樣的排列有()個(gè)(

)+(

)=(

)

f(a1a2…ar)=b1b2…brn-rrn-rn-rn-r+1r-1rr第一百零八頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.6組合的生成解法２任給a1a2…ar∈C’(n,r),

a1＜

a2＜

…＜

ar令f：a1a2…ar→b1b2…brbi=ai-i+1,i=1,2,…,r.1≤b1＜

b2＜

…＜

br≤n-r+1,

b1b2…br∈C(n-r+1,r)C’(n,r)=C(n-r+1,r)第一百零九頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.7可重組合C(n,r)的計(jì)數(shù)問(wèn)題相當(dāng)于r相同的球放入n個(gè)互異的盒子，每盒球的數(shù)目不同的方案的計(jì)數(shù)。而后一問(wèn)題又可轉(zhuǎn)換為r個(gè)相同的球與n-1個(gè)相同的盒壁的排列的問(wèn)題。易知所求計(jì)數(shù)為=C(n+r-1,r)即C(n,r)=()=C(n-1,r)+C(n,r-1) 不含“１”至少含一個(gè)“１”(n-1+r)!————r!(n-1)!n+r-1r

r個(gè)相同的球/\———————————————／\0…010…01…10…0

\/————————\/

n-1個(gè)相同的盒壁第一百一十頁(yè)，共一百四十二頁(yè)，2022年，8月28日1.7可重組合另證設(shè)a1a2…ar∈C(n,r)

1≤a1≤a2≤…≤ar≤n,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,…,r.