盧開澄組合數(shù)學(xué)-組合數(shù)學(xué)第一章

前言組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方…...第一頁(yè)第二頁(yè)，共123頁(yè)。前言 幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。519372486第二頁(yè)第三頁(yè)，共123頁(yè)。前言

賈憲

北宋數(shù)學(xué)家（約11世紀(jì)）著有《黃帝九章細(xì)草》、《算法斅古集》斅音“笑（“古算法導(dǎo)引”）都已失傳。楊輝著《詳解九章算法》（1261年）中曾引賈憲的“開方作法本源”圖（即指數(shù)為正整數(shù)的二項(xiàng)式展開系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。第三頁(yè)第四頁(yè)，共123頁(yè)。前言1666年萊布尼茲所著《組合學(xué)論文》一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。第四頁(yè)第五頁(yè)，共123頁(yè)。前言 組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。第五頁(yè)第六頁(yè)，共123頁(yè)。前言本學(xué)期主要講組合分析（計(jì)數(shù)和枚舉）以及組合優(yōu)化的一部分（線性規(guī)劃的單純形解法）。組合分析是組合算法的基礎(chǔ)。第六頁(yè)第七頁(yè)，共123頁(yè)。前言 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。第七頁(yè)第八頁(yè)，共123頁(yè)。第一章 排列組合1.1加法法則與乘法法則第八頁(yè)第九頁(yè)，共123頁(yè)。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è)，共123頁(yè)。1.1加法法則與乘法法則[例]某班選修企業(yè)管理的有18人，不選的有10人，則該班共有18+10=28人。[例]北京每天直達(dá)上海的客車有5次，客機(jī)有3次，則每天由北京直達(dá)上海的旅行方式有5+3=8種。第十頁(yè)第十一頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.1加法法則與乘法法則例某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是44=16，而只有43=12種。在乘法法則中要注意事件A和事件B的相互獨(dú)立性。第十三頁(yè)第十四頁(yè)，共123頁(yè)。1.1加法法則與乘法法則例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ù)有10個(gè),不含1的四位數(shù)有9個(gè),含1的4位數(shù)為兩個(gè)的差:10－9=3439個(gè)4444第十四頁(yè)第十五頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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í)稱為全排列。一般不說可重即無(wú)重。可重排列的相應(yīng)記號(hào)為

-

P(n,r),P(n,r)。l第十六頁(yè)第十七頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。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!=(

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

n!———r!(n-r)!第十九頁(yè)第二十頁(yè)，共123頁(yè)。1.2排列與組合例有5本不同的日文書，7本不同的英文書，10本不同的中文書。1)取2本不同文字的書；2)取2本相同文字的書；3)任取兩本書第二十頁(yè)第二十一頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.2排列與組合例某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？[解]一進(jìn)站方案表示成：100其中“0”表示人，“1”表示門框，其中“0”是不同元，“1”是相同元。給“1”n個(gè)門只用n-1個(gè)門框。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。第二十三頁(yè)第二十四頁(yè)，共123頁(yè)。1.2排列與組合[解法1]標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。故若設(shè)x為所求方案，則

x·5!=14!∴x=14!/5!=726485760第二十四頁(yè)第二十五頁(yè)，共123頁(yè)。1.2排列與組合[解法2]在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，在確定人的位置，有9！種選擇。故C(14,5)·9!即所求第二十五頁(yè)第二十六頁(yè)，共123頁(yè)。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è)，共123頁(yè)。1.3Stirling近似公式組合計(jì)數(shù)的漸進(jìn)值問題是組合論的一個(gè)研究方向。Stirling公式給出一個(gè)求n!的近似公式，它對(duì)從事計(jì)算和理論分析都是有意義的。第二十七頁(yè)第二十八頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.3Stirling近似公式2)stirling公式y(tǒng)y=lnx

0123n-1nx第三十二頁(yè)第三十三頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.3Stirling近似公式令βn=e,limβn=β.將(1-3-8)代入(1-3-3),整理得 β=2π.所以 n!~2πn(－)n→∞1-bn√√nen第三十六頁(yè)第三十七頁(yè)，共123頁(yè)。1.4模型轉(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)。第三十七頁(yè)第三十八頁(yè)，共123頁(yè)。1.4模型轉(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...x第三十八頁(yè)第三十九頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.4模型轉(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)的格路。第四十一頁(yè)第四十二頁(yè)，共123頁(yè)。1.4模型轉(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).....第四十二頁(yè)第四十三頁(yè)，共123頁(yè)。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-1mmn-mmnnm+n-1mn-mn第四十三頁(yè)第四十四頁(yè)，共123頁(yè)。1.4模型轉(zhuǎn)換若條件改為可接觸但不可穿過，則限制線要向下或向右移一格，得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è)，共123頁(yè)。1.4模型轉(zhuǎn)換例CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈：H|H—C—H|HH|H—C—H|H—C—H|HH|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷第四十五頁(yè)第四十六頁(yè)，共123頁(yè)。1.4模型轉(zhuǎn)換H|H—C—H|H—C—H|H—C—H|H—C—H|HH|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.第四十六頁(yè)第四十七頁(yè)，共123頁(yè)。1.4模型轉(zhuǎn)換例在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問要舉行幾場(chǎng)比賽？解

一種常見的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。第四十七頁(yè)第四十八頁(yè)，共123頁(yè)。1.4模型轉(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)的樹是唯一的。第四十八頁(yè)第四十九頁(yè)，共123頁(yè)。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)的樹邊上的標(biāo)號(hào)表示摘去葉的順序。(摘去一個(gè)葉子相應(yīng)去掉一條邊)第一次摘掉②，③為②相鄰的頂點(diǎn)，得到序列的第一個(gè)數(shù)3以此類推，得到序列31551,長(zhǎng)度為7－2=5這是由樹形成序列的過程。第四十九頁(yè)第五十頁(yè)，共123頁(yè)。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è)序列排在一起31551111233455567第五十頁(yè)第五十一頁(yè)，共123頁(yè)。1.4模型轉(zhuǎn)換

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推導(dǎo)：將上下兩個(gè)序列同時(shí)去掉上行序列的第一個(gè)元素3(用黃色表示)，去掉下行序列的第一個(gè)無(wú)重復(fù)的元素2(用紅色表示)。生成一條邊(②—③)。依此類推，減到下面剩最后兩個(gè)元素，這兩個(gè)元素形成最后一條邊。最后形成樹。第五十一頁(yè)第五十二頁(yè)，共123頁(yè)。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è)樹。b中每去掉一個(gè)元，a’中去掉2個(gè)元。第五十二頁(yè)第五十三頁(yè)，共123頁(yè)。1.4模型轉(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’第五十三頁(yè)第五十四頁(yè)，共123頁(yè)。1.4模型轉(zhuǎn)換證由一棵n個(gè)頂點(diǎn)的樹可得到一個(gè)長(zhǎng)度為n－2的序列，且不同的樹對(duì)應(yīng)的序列不同*，因此|T

|≤n。

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

就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。全排列的生成算法第五十五頁(yè)第五十六頁(yè)，共123頁(yè)。1.5全排列的生成算法這里介紹全排列算法四種：(A)字典序法(B)遞增進(jìn)位制數(shù)法(C)遞減進(jìn)位制數(shù)法(D)鄰位對(duì)換法第五十六頁(yè)第五十七頁(yè)，共123頁(yè)。1.5.1字典序法對(duì)給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后。第五十七頁(yè)第五十八頁(yè)，共123頁(yè)。1.5.1字典序法[例]字符集{1,2,3},較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321?！?/p>

一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。第五十八頁(yè)第五十九頁(yè)，共123頁(yè)。1.5.1字典序法1）生成給定全排列的下一個(gè)排列所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。第五十九頁(yè)第六十頁(yè)，共123頁(yè)。1.5.1字典序法[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個(gè)了。否則找出第一次出現(xiàn)下降的位置。第六十頁(yè)第六十一頁(yè)，共123頁(yè)。1.5.1字典序法求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è)，共123頁(yè)。1.5.1字典序法在[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è)，共123頁(yè)。1.5.1字典序法一般而言，設(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è)，共123頁(yè)。1.5.1字典序法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,先于得的排列的個(gè)數(shù)：2×2!+2×2!前7位是,先于得的排列的個(gè)數(shù)：1×1!+1×1!297191前8位固定，則最后一位也隨之固定將8!,7!,…,1!前面的系數(shù)抽出，放在一起得到此數(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ù)是計(jì)算排列839647521的序號(hào)的中間環(huán)節(jié)，我們稱之為中介數(shù)。※這是一個(gè)很有用的概念。第六十四頁(yè)第六十五頁(yè)，共123頁(yè)。1.5.1字典序法一般而言,對(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è)，共123頁(yè)。1.5.1字典序法由中介數(shù)推出排列的算法[例]由推算出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è)過程比較麻煩(這醞釀著改進(jìn)的可能)，該算法從左到右依次推出P1,P2,…,P9。下述算法依次定出1,2,3,…,9的位置。第六十六頁(yè)第六十七頁(yè)，共123頁(yè)。1.5.1字典序法方法2-1：中未出現(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由推算出839647521第六十七頁(yè)第六十八頁(yè)，共123頁(yè)。1.5.1字典序法方法2-2：已定出上標(biāo)‘●’，找左起第一個(gè)0，下標(biāo)‘__’由推算出839647521

●72641=61531210________12

●●●●61531210-11111110=504201003●●●●50420100-10000000=404201004●●●●●40420100-10110000=303101005●●●●●●●●30310100-10110100=202000006●●●●●●●●●●20200000-10100000=101000007●●●●●●●●●●●●10100000-10100000=08●●●●●●●000000009以上兩種從中介數(shù)求排列的算法都比較麻煩。給定一排列與下一個(gè)排列各自的中介數(shù)→進(jìn)位鏈（中介數(shù)的后繼）→遞增進(jìn)位制數(shù)第六十八頁(yè)第六十九頁(yè)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.2遞增進(jìn)位制數(shù)法在字典序法中由中介數(shù)求排列比較麻煩，我們可以通過另外定義遞增進(jìn)位制數(shù)加以改進(jìn)。為方便起見，令ai+1=kn-I，i=1,2,…,n-1(k1k2…kn-1)↑=(anan-1…a2)↑ai：i的右邊比i小的數(shù)字的個(gè)數(shù)第七十二頁(yè)第七十三頁(yè)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.2遞增進(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è)，共123頁(yè)。1.5.3遞減進(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è)，共123頁(yè)。1.5.4鄰位對(duì)換法遞減進(jìn)位制數(shù)法的中介數(shù)進(jìn)位不頻繁，求下一個(gè)排列在不進(jìn)位的情況下很容易。這就啟發(fā)我們，能不能設(shè)計(jì)一種算法，下一個(gè)排列總是上一個(gè)排列某相鄰兩位對(duì)換得到的。遞減進(jìn)位制數(shù)字的換位是單向的，從右向左，而鄰位對(duì)換法的換位是雙向的。第七十七頁(yè)第七十八頁(yè)，共123頁(yè)。1.5.4鄰位對(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è)，共123頁(yè)。1.5.4鄰位對(duì)換法[例]839647521→836947521●→[解]2的右邊有1個(gè)數(shù)字(奇數(shù))比2小,2上加一個(gè)點(diǎn)?！瘛?的右邊有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è)，共123頁(yè)。1.5.4鄰位對(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)寫成an，bn第八十頁(yè)第八十一頁(yè)，共123頁(yè)。1.5.4鄰位對(duì)換法已知(10121372)↓求排列。9的位置由b9和a8的奇偶性決定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1?！鷅8奇→9，b6+b7偶→8，b6奇→7，→→

b4+b5奇→6，b4奇→5第八十一頁(yè)第八十二頁(yè)，共123頁(yè)。1.5.4鄰位對(duì)換法序號(hào)=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2=203393←→(10121372)↓第八十二頁(yè)第八十三頁(yè)，共123頁(yè)。1.5.4鄰位對(duì)換法第八十三頁(yè)第八十四頁(yè)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.6組合的生成例

用兩種方法計(jì)算[1,n]的無(wú)重不相鄰組合C’(n,r)的計(jì)數(shù)問題解法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è)，共123頁(yè)。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è)，共123頁(yè)。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è)，共123頁(yè)。1.7可重組合C(n,r)的計(jì)數(shù)問題相當(dāng)于r相同的球放入n個(gè)互異的盒子，每盒球的數(shù)目不同的方案的計(jì)數(shù)。而后一問題又可轉(zhuǎn)換為r個(gè)相同的球與n-1個(gè)相同的盒壁的排列的問題。易知所求計(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-1rr個(gè)相同的球/\———————————————／\0…010…01…10…0

\/————————\/n-1個(gè)相同的盒壁第九十頁(yè)第九十一頁(yè)，共123頁(yè)。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.則b1b2…br滿足1≤b1＜b2＜…＜br≤n+r-1

b1b2…br∈C(n+r-1,r)f：a1a2…ar→b1b2…br顯然f是單射，f：b1b2…br→a1a2…ar－－-1第九十一頁(yè)第九十二頁(yè)，共123頁(yè)。1.7可重組合ai=bi-i+1,i=1,2,…,r.a1a2…ar∈C(n,r)f是單射C(n,r)≤C(n+r-1,r)f是單射C(n,r)≥C(n+r-1,r)∴C(n,r)=C(n+r-1,r)第二個(gè)證明可說一種“拉伸壓縮”技巧。不可謂不巧妙。但仍不如第一證明來(lái)的明快，由此可見組合證明的功效。———-1—第九十二頁(yè)第九十三頁(yè)，共123頁(yè)。1.8若干等式及其組合意義組合意義或組合證明，含意強(qiáng)弱的不同。承認(rèn)組合證明與其他證明有相同的“合法性”。第九十三頁(yè)第九十四頁(yè)，共123頁(yè)。1.8若干等式及其組合意義1.C(n,r)=C(n,n-r)(1.7.1)

從[1,n]去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。故C(n,r)=C(n,n-r)第九十四頁(yè)第九十五頁(yè)，共123頁(yè)。1.8若干等式及其組合意義2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.7.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-1)種方案共有C(n-1,r)+C(n-1,r-1)中方案，故 C(n,r)=C(n-1,r)+C(n-1,r-1)第九十五頁(yè)第九十六頁(yè)，共123頁(yè)。1.8若干等式及其組合意義楊輝三角除了(0,0)點(diǎn)，都滿足此遞推式 0<r≤n,n<0<r C(n,r)= 1, r=0 0, 0≤n<r,r<0≤n n<0且r<0C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1){(0,0)→(m,n)} ={(0,0)→(m,n-1)}∪{(0,0)→(m-1,n)}(-1)()|r|-1|n|-1n+r[n]r——r!第九十六頁(yè)第九十七頁(yè)，共123頁(yè)。1.8若干等式及其組合意義3.(

)+()+()+…+()=()(1.7.3)[1]可從(7.2)推論，也可做一下組合證明從[1,n+r+1]取a1a2…anan+1， 設(shè)a1＜a2＜…＜an＜an+1， 可按a1的取值分類：a1=1,2,3,…r,r+1.a1=1,a2…an+1取自[2,n+r+1]有()種取法nn+1n+2n+rn+r+1nnnnnn+rna1=2,a2…an+1取自[3,n+r+1]有()種取法n+r-1n………a1=r,a2…an+1取自[r+1,n+r+1]有()種取法n+1na1=r+1,a2…an+1取自[r+2,n+r+1]有()種取法nn也可看做按含1不含1，含2不含2,…,含r不含r的不斷分類第九十七頁(yè)第九十八頁(yè)，共123頁(yè)。1.8若干等式及其組合意義[2]從(0,0)到(n+1,r),過且僅過一條帶箭頭的邊,而過這些邊的路徑有(從下到上)(),(),…,()故有.(

)+()+()+…+()=()nn+1n+rnnnnn+1n+2n+rn+r+1nnnnnr(n+1,r)

...(0,0)nn+1第九十八頁(yè)第九十九頁(yè)，共123頁(yè)。1.8若干等式及其組合意義[3]可重組合. [1,n+2]的C(n+2,r)模型()不含1,含1個(gè)1,含2個(gè)1,…,含r個(gè)1C(),C(),C(),…,C()(),(),(),…,()n+r+1rn+1n+1n+1n+1rr-1r-20n+rn+r-1n+r-2nrr-1r-20第九十九頁(yè)第一百頁(yè)，共123頁(yè)。1.8若干等式及其組合意義4.()()=()()(1.7.4)①選政治局,再選常委,n個(gè)中央委員選出l名政治局委員,再?gòu)钠渲羞x出r名常委②選常委,再選非常委政治局委員兩種選法都無(wú)遺漏,無(wú)重復(fù)地給出可能的方案，應(yīng)該相等。nlnn-rlrrl-r第一百頁(yè)第一百零一頁(yè)，共123頁(yè)。1.8若干等式及其組合意義5.

()+()+…+()=2,m≤0,(1.7.5)證1(x+y)

=∑(

)x

y,令x=y=1,得(1.7.5)組合證1[1,m]的所有方案.每一子集都可取k[1,m]或不取.這樣有2個(gè)方案.另可有0-子集(空集),1-子集,…,m-子集.組合證2從(0,0)走m步有2種走法,都落在直線x+y=m上,而到(m,0),(m-1,1),(m-2,2),…,(2,m-2),(1,m-1),(0,m)各點(diǎn)的走法各有(

),(

),(

),…,(

),(),()種mmmm01m

mkm-k

mmkk=0mmmmmmmm012m-2m-1m第一百零一頁(yè)第一百零二頁(yè)，共123頁(yè)。1.8若干等式及其組合意義6.()-()+()-…±()=0(1.7.6)證1

在(x+y)=∑()xy中令x=1,y=-1即得.nnnn012nnn-kknknk=0第一百零二頁(yè)第一百零三頁(yè)，共123頁(yè)。1.8若干等式及其組合意義證2

在[1,n]的所有組合中,含1的組合←→不含1的組合.有1—1