12基本的組合計(jì)數(shù)公式

離散數(shù)學(xué)第12章根本的組合計(jì)數(shù)公式28九月2023前言組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方…...前言 幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。519372486前言賈憲北宋數(shù)學(xué)家〔約11世紀(jì)〕著有?黃帝九章細(xì)草?、?算法斅古集?斅音“笑〔“古算法導(dǎo)引〞〕都已失傳。楊輝著?詳解九章算法?〔1261年〕中曾引賈憲的“開方作法根源〞圖〔即指數(shù)為正整數(shù)的二項(xiàng)式展開系數(shù)表，現(xiàn)稱“楊輝三角形〞〕和“增乘開方法〞〔求高次冪的正根法〕。前者比帕斯卡三角形早600年，后者比霍納〔WilliamGeogeHorner，1786—1837〕的方法〔1819年〕早770年。前言1666年萊布尼茲所著?組合學(xué)論文?一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論〔Combinatorics〕一詞。前言組合數(shù)學(xué)的蓬勃開展那么是在計(jì)算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地開展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。前言組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。計(jì)數(shù)問題計(jì)數(shù)問題是組合數(shù)學(xué)研究的主要問題之一。西班牙數(shù)學(xué)家AbrahambenMeiribnEzra(1092～1167)和法國數(shù)學(xué)家、哲學(xué)家、天文學(xué)家LevibenGerson(1288～1344)是排列與組合領(lǐng)域的兩位早期研究者。另外，法國數(shù)學(xué)家BlaisePascal還創(chuàng)造了一種機(jī)械計(jì)算器，這種計(jì)算器非常類似于20世紀(jì)40年代在數(shù)字電子計(jì)算機(jī)創(chuàng)造之前使用的一種機(jī)械計(jì)算器。同時(shí)，計(jì)數(shù)技術(shù)在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中是很重要的，特別是在?數(shù)據(jù)結(jié)構(gòu)?、?算法分析與設(shè)計(jì)?等后續(xù)課程中有非常重要的應(yīng)用。

內(nèi)容提要二項(xiàng)式定理與組合恒等式3多項(xiàng)式定理4加法法則與乘法法則1排列與組合2

本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11加法法則和原理法則2排列組合的計(jì)算31離散概率2離散概念的計(jì)算公式及性質(zhì)2二項(xiàng)式定理與組合恒等式計(jì)算

組合問題的處理技巧一一對(duì)應(yīng)數(shù)學(xué)歸納法上下界逼近一一對(duì)應(yīng)與上下界逼近例1在允許移動(dòng)被切割的物體的情況下，最少用多少次切割可以將333的立方體切成27個(gè)單位邊長的立方體？中間的小立方體的6個(gè)面都是切割產(chǎn)生的面，每次切割至多產(chǎn)生一個(gè)面，至少需要6次切割。存在一種切割方法恰好用6次切割。例2100個(gè)選手淘汰賽，為產(chǎn)生冠軍至少需要多少輪比賽？方法1：50+25+12+6+3+2+1=99方法2：比賽次數(shù)與淘汰人數(shù)之間存在一一對(duì)應(yīng)，總計(jì)淘汰99人，因此至少需要99場(chǎng)比賽.12.1加法法那么與乘法法那么開胃食品主食飲料種類價(jià)格(元)種類價(jià)格種類價(jià)格玉米片(Co)2.15漢堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85魚排(F)3.15可樂(C)0.75啤酒(B)0.75表1乘法法那么如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…，第t步有nt種不同的選擇，那么完成這項(xiàng)工作所有可能的選擇種數(shù)為：例1Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計(jì)算機(jī)系統(tǒng)，通過以含惡意宏的字處理文檔為附件的電子郵件傳播。當(dāng)字處理文檔被翻開時(shí)，宏從用戶的地址本中找出前50個(gè)地址，并將病毒轉(zhuǎn)發(fā)給他們。用戶接收到這些被轉(zhuǎn)發(fā)的附件并將字處理文檔翻開后，病毒會(huì)自動(dòng)繼續(xù)轉(zhuǎn)發(fā)，不斷往復(fù)擴(kuò)散。病毒非?？焖俚剞D(zhuǎn)發(fā)郵件，將被轉(zhuǎn)發(fā)的郵件臨時(shí)存儲(chǔ)在某個(gè)磁盤上，當(dāng)磁盤占滿后，系統(tǒng)將會(huì)死鎖甚至崩潰。問經(jīng)過四次轉(zhuǎn)發(fā)，共有多少個(gè)接收者？解根據(jù)Melissa病毒的擴(kuò)散原理，經(jīng)過四次轉(zhuǎn)發(fā)，共有50×50×50×50+50×50×50+50×50+50+1=6377551個(gè)接收者。例2在一幅數(shù)字圖像中，假設(shè)每個(gè)像素點(diǎn)用8位進(jìn)行編碼，問每個(gè)點(diǎn)有多少種不同的取值。分析用8位進(jìn)行編碼可分為8個(gè)步驟：選擇第一位，選擇第二位，…，選擇第八位。每一個(gè)位有兩種選擇，故根據(jù)乘法原理，8位編碼共有2×2×2×2×2×2×2×2=28=256種取值。解每個(gè)點(diǎn)有256(=28)種不同的取值。加法法那么假定X1,X2,…,Xt均為集合，第i個(gè)集合Xi有ni個(gè)元素。如{X1,X2,…,Xt}為兩兩不相交的集合，那么可以從X1,X2,…,Xt中選出的元素總數(shù)為：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt個(gè)元素。例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六個(gè)人組成的委員會(huì)，要選出一個(gè)主席、一個(gè)秘書和一個(gè)出納員?！?〕共有多少種選法？〔2〕假設(shè)主席必須從Alice和Ben種選出，共有多少種選法？〔3〕假設(shè)Egbert必須有職位，共有多少種選法？〔4〕假設(shè)Dolph和Francisco都有職位，共有多少種選法？例3解〔1〕根據(jù)乘法法那么，可能的選法種數(shù)為6×5×4=120；〔2〕[法一]根據(jù)題意，確定職位可分為3個(gè)步驟：確定主席有2種選擇；主席選定后，秘書有5個(gè)人選；主席和秘書都選定后，出納有4個(gè)人選。根據(jù)乘法法那么，可能的選法種數(shù)為2×5×4=40；[法二]假設(shè)Alice被選為主席，共有5×4=20種方法確定其他職位；假設(shè)Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法法那么，共有20＋20=40種選法；例3解(續(xù))(3)[法一]將確定職位分為3步：確定Egbert的職位,有3種方法；確定余下的較高職位人選,有5個(gè)人選；確定最后一個(gè)職位的人選,有4個(gè)人選。根據(jù)乘法法那么，共有3×5×4=60種選法；[法二]根據(jù)(1)的結(jié)論，如果Egbert為主席，有20種方法確定余下的職位；假設(shè)Egbert為秘書，有20種方法確定余下的職位；假設(shè)Egbert為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據(jù)加法法那么，共有20＋20＋20=60種選法；例3解(續(xù))〔4〕將給Dolph、Francisco和另一個(gè)人指定職位分為3步：給Dolph指定職位，有3個(gè)職位可選；給Francisco指定職位，有2個(gè)職位可選；確定最后一個(gè)職位的人選，有4個(gè)人選。根據(jù)乘法法那么，共有3×2×4=24種選法。12.2排列與組合Zeke、Yung、Xeno和Wilma四個(gè)候選人競(jìng)選同一職位。為了使選票上人名的次序不對(duì)投票者產(chǎn)生影響，有必要將每一種可能的人名次序打印在選票上。會(huì)有多少種不同的選票呢？從某個(gè)集合中有序的選取假設(shè)干個(gè)元素的問題，稱為排列問題。排列問題定義12.1〔1〕從含n個(gè)不同元素的集合S中有序選取的r個(gè)元素叫做S的一個(gè)r-排列，不同的排列總數(shù)記為P(n,r)。如果r=n，那么稱這個(gè)排列為S的一個(gè)全排列，簡(jiǎn)稱為S的排列。顯然，當(dāng)r>n時(shí)，P(n,r)=0。例1從含3個(gè)不同元素的集合S中有序選取2個(gè)元素的排列總數(shù)。解從含3個(gè)元素的不同集合S中有序選取2個(gè)元素的排列總數(shù)為6種。如果將這3個(gè)元素記為A、B和C，那么6個(gè)排列為AB,AC,BA,BC,CB,CA。定理12.1對(duì)滿足r≤n的正整數(shù)n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)注意：n個(gè)不同元素的排列共有n！種，其中

例2A,B,C,D,E,F組成的排列中，〔1〕有多少含有DEF的子串？〔2〕三個(gè)字母D、E和F相連的有多少種？解(1)將DEF看成一個(gè)對(duì)象，根據(jù)定理，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24種；〔2〕根據(jù)題意，滿足該條件的排列分為兩步：第一步確定D,E和F三個(gè)字母的全排列，有3！種排列，第二步將已排序的D,E和F看成一個(gè)整體，與A,B和C共4個(gè)元素構(gòu)造出A,B,C,D,E,F的全排列，有4！種排列。又根據(jù)乘法原理，滿足條件的排列總數(shù)有3！×4！=144。例36個(gè)人圍坐在圓桌上，有多少種不同的坐法？通過轉(zhuǎn)圈得到的坐法視為同一種坐法。解6個(gè)人圍坐在圓桌上，有120種不同的坐法。AEFBDCn個(gè)人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個(gè)人中選出r個(gè)人為圓桌而坐稱為環(huán)形r-排列。推論1含n個(gè)不同元素的集合的環(huán)形r-排列數(shù)Pc(n,r)是例4求滿足以下條件的排列數(shù)。(1)10個(gè)男孩和5個(gè)女孩站成一排，無兩個(gè)女孩相鄰。(2)10個(gè)男孩和5個(gè)女孩站成一圓圈，無兩個(gè)女孩相鄰.解(1)根據(jù)定理，10個(gè)男孩的全排列為10!，5個(gè)女孩插入到10個(gè)男孩形成的11個(gè)空格中的插入方法數(shù)為P(11,5)。根據(jù)乘法法那么，10個(gè)男孩和5個(gè)女孩站成一排，沒有兩個(gè)女孩相鄰的排列數(shù)為：10!×P(11,5)=〔10!×11!)/6!。例4解〔續(xù)〕〔2〕根據(jù)定理，10個(gè)男孩站成一個(gè)圓圈的環(huán)排列數(shù)為9！，5個(gè)女孩插入到10男孩形成的10個(gè)空中的插入方法數(shù)為P(10,5)。根據(jù)乘法原理，10個(gè)男孩和5個(gè)女孩站成一個(gè)圓圈，沒有兩個(gè)女孩相鄰的排列法為：9!×P(10,5)=〔9!×10!)/5!。組合問題定義12.1〔2〕從含有n個(gè)不同元素的集合S中無序選取的r個(gè)元素叫做S的一個(gè)r-組合，不同的組合總數(shù)記為C(n,r)。當(dāng)n≥r=0時(shí)，規(guī)定C(n,r)=1。顯然，當(dāng)r>n時(shí)，C(n,r)=0。定理12.1〔2〕對(duì)滿足0<r≤n的正整數(shù)n和r有，即

證明先從n個(gè)不同元素中選出r個(gè)元素，有C(n,r)種選法，再把每一種選法選出的r個(gè)元素做全排列，有r！種排法。定理12.1〔2〕〔續(xù)〕根據(jù)乘法法那么，n個(gè)元素的r排列數(shù)為：即

例5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；各有13種點(diǎn)數(shù)，分別為A,2—10,J,Q,K。試求滿足以下條件的組合數(shù)。〔1〕手中持有5張牌稱為一手牌，一手牌共有多少種可能的組合？〔2〕一手牌中的5張都是同一花色，共有多少種可能的組合？〔3〕一手牌中有3張牌點(diǎn)數(shù)相同，另外兩張牌點(diǎn)數(shù)相同，共有多少種可能的組合？例5解〔1〕一手牌可能的組合數(shù)等于從52張牌中選出5張的可能組合數(shù)，有C(52,5)種可能的組合；〔2〕選同一花色的5張牌分兩步進(jìn)行：一選花色，有C(4,1)種，二在選定的花色中選5張牌，有C(13,5)種。據(jù)乘法原理，有C(4,1)×C(13,5)種；例5解〔續(xù)〕〔3〕該組合問題需四步完成：一選第一個(gè)點(diǎn)數(shù)，有C(13,1)種；二選第二個(gè)點(diǎn)數(shù)，有C(12,1)種：三選第一點(diǎn)數(shù)的3張牌，有C(4,3)種；四選第二點(diǎn)數(shù)的2張牌，有C(4,2)種。根據(jù)乘法法那么，共有C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744種選法。集合的排列定義12.1從n元集S中有序、不重復(fù)選取的r個(gè)元素稱為S的一個(gè)r排列，S的所有r排列的數(shù)目記作P(n,r)定理12.1證明使用乘法法那么推論1S的環(huán)排列數(shù)=集合的組合定義12.1

從n元集S中無序、不重復(fù)選取的r個(gè)元素稱為S

的一個(gè)r

組合，S的所有r組合的數(shù)目記作C(n,r)定理12.1推論2設(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)證明方法方法1：公式代入并化簡(jiǎn)方法2：組合證明實(shí)例：證明

C(n,r)=C(n,n

r)證設(shè)S={1,2,…,n}是n元集合，對(duì)于S的任意r-組合A={a1,a2,…,ar}，都存在一個(gè)S的n

r組合S

A與之對(duì)應(yīng).顯然不同的r組合對(duì)應(yīng)了不同的n

r組合，反之也對(duì)，因此S的r組合數(shù)恰好與S的(n

r)組合數(shù)相等.C(n,r)=C(n

1,r

1)+C(n

1,r)稱為Pascal公式，也對(duì)應(yīng)了楊輝三角形，

兩種證明方法都適用.楊輝三角根本計(jì)數(shù)公式的應(yīng)用解分類選取A={1,4,…,298}B={2,5,…,299}C={3,6,…,300}分別取自A,B,C:各C(100,3)A,B,C各取1個(gè)〔分步處理〕：C(100,1)3N=C(100,3)+1003=1485100例1

從1—300中任取3個(gè)數(shù)使得其和能被3整除有多少種方法？根本計(jì)數(shù)公式的應(yīng)用(續(xù))解:1000!=1000999998…21將上面的每個(gè)因子分解，假設(shè)分解式中共有i個(gè)5,j個(gè)2，那么min(i,j)就是0的個(gè)數(shù).1,…,1000中有500個(gè)是2的倍數(shù)，j>500;200個(gè)是5的倍數(shù)，40個(gè)是25的倍數(shù)〔多加40個(gè)5〕，8個(gè)是125的倍數(shù)〔再多加8個(gè)5〕，1個(gè)是625的倍數(shù)〔再多加1個(gè)5〕i=200+40+8+1=249.min(i,j)=249.例2

求1000！的末尾有多少個(gè)0？根本計(jì)數(shù)公式的應(yīng)用(續(xù))例3

設(shè)A為n元集，問(1)A上的自反關(guān)系有多少個(gè)？(2)A上的反自反關(guān)系有多少個(gè)？(3)A上的對(duì)稱關(guān)系有多少個(gè)？(4)A上的反對(duì)稱關(guān)系有多少個(gè)？(5)A上既不對(duì)稱也不是反對(duì)稱的關(guān)系有多少個(gè)？多重集的排列定理12.2

多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk

=n

證明：分步選取.先放a1,有C(n,n1)種方法；再放a2,有C(n

n1,n2)種方法,...,放ak,有C(n

n1

n2

…

nk

1,nk)種方法

(2)若r

ni

時(shí)，每個(gè)位置都有

k種選法，得

kr.多重集的組合定理12.3

多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

+∞當(dāng)r

ni,S的r組合數(shù)為N=C(k+r

1,r),證明一個(gè)r組合為{x1

a1,x2

a2,…,xk

ak}，其中

x1+x2+…+xk

=r,xi為非負(fù)整數(shù).這個(gè)不定方程的非負(fù)整數(shù)解對(duì)應(yīng)于下述排列1…101…101…10……01…1

x1個(gè)x2個(gè)

x3個(gè)xk個(gè)r個(gè)1，k

1個(gè)0的全排列數(shù)為實(shí)例例5

排列26個(gè)字母，使得a與b之間恰有7個(gè)字母，求方法數(shù).解：設(shè)盒子的球數(shù)依次記為x1,x2,…,xn,那么滿足x1+x2+…+xn=r，x1,x2,…,xn為非負(fù)整數(shù)N=C(n+r1,r)例4

r

個(gè)相同的球放到n個(gè)不同的盒子里，每個(gè)盒子球數(shù)不限，求放球方法數(shù).解：固定a和b,中間選7個(gè)字母，有2P(24,7)種方法，將它看作大字母與其余17個(gè)字母全排列有18！種，共

N=2P(24,7)18!實(shí)例(續(xù))例6(1)10個(gè)男孩，5個(gè)女孩站成一排，假設(shè)沒有女孩相鄰，有多少種方法？(2)如果站成一個(gè)圓圈，有多少種方法？解:(1)

P(10,10)P(11,5)(2)

P(10,10)P(10,5)/10解：相當(dāng)于2n不同的球放到n個(gè)相同的盒子，每個(gè)盒子2個(gè)，放法為例7

把2n個(gè)人分成n

組，每組2人，有多少分法？實(shí)例(續(xù))解使用一一對(duì)應(yīng)的思想求解這個(gè)問題.a1,a2,…,ak：k個(gè)不相鄰的數(shù),屬于集合{1,2,…,n}b1,b2,…,bk：k個(gè)允許相鄰的數(shù),屬于集合{1,…,n(k1)}對(duì)應(yīng)規(guī)那么是bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8

從S={1,2,…,n}中選擇k個(gè)不相鄰的數(shù)，有多少種方法？12.3二項(xiàng)式定理與組合恒等式12.3.1二項(xiàng)式定理12.3.2組合恒等式12.3.3非降路徑問題二項(xiàng)式定理定理12.4設(shè)n是正整數(shù)，對(duì)一切x和y

證明方法:數(shù)學(xué)歸納法、組合分析法.證當(dāng)乘積被展開時(shí)其中的項(xiàng)都是下述形式：xiyn

i,i=0,1,2,…,n.而構(gòu)成形如xiyn

i的項(xiàng)，必須從n個(gè)和(x+y)中選i個(gè)提供x，其它的n

i個(gè)提供y.因此，xiyn

i的系數(shù)是，定理得證.

二項(xiàng)式定理的應(yīng)用例1

求在(2x－3y)25的展開式中x12y13的系數(shù).解由二項(xiàng)式定理令i=13得到展開式中x12y13的系數(shù)，即

組合恒等式——遞推式證明方法：公式代入、組合分析應(yīng)用：1式用于化簡(jiǎn)2式用于求和時(shí)消去變系數(shù)3式用于求和時(shí)拆項(xiàng)〔兩項(xiàng)之和或者差〕，然后合并組合恒等式——變下項(xiàng)求和證明公式4.方法：二項(xiàng)式定理或者組合分析.設(shè)S={1,2,…,n}，下面計(jì)數(shù)S的所有子集.

一種方法就是分類處理，n元集合的k子集個(gè)數(shù)是根據(jù)加法法那么，子集總數(shù)是另一種方法是分步處理，為構(gòu)成S的子集A，每個(gè)元素有2種選擇，根據(jù)乘法法那么，子集總數(shù)是2n.恒等式求和——變系數(shù)和證明方法：二項(xiàng)式定理、級(jí)數(shù)求導(dǎo)其他組合恒等式代入證明公式6(二項(xiàng)式定理+求導(dǎo))證明公式7(恒等式代入)恒等式——變上項(xiàng)求和證明組合分析.令S={a1,a2,…,an+1}為n+1元集合.等式右邊是S的k+1子集數(shù).考慮另一種分類計(jì)數(shù)的方法.將所有的k+1元子集分成如下n+1類：第1類：含a1,剩下k個(gè)元素取自{a2,…,an+1}

第2類：不含a1,含a2,剩下k個(gè)元素取自{a3,…,an+1}……不含a1,a2,…,an,含an+1,剩下k個(gè)元素取自空集由加法法那么公式得證恒等式——乘積轉(zhuǎn)換式證明方法：組合分析.n元集中選取

r個(gè)元素，然后在這r個(gè)元素中再選

k個(gè)元素.不同的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，求和時(shí)提到和號(hào)外面.恒等式——積之和關(guān)系證明思路：考慮集合A={a1,a2,…,am}，B={b1,b2,…,bn}.等式右邊計(jì)數(shù)了從這兩個(gè)集合中選出r個(gè)元素的方法.將這些選法按照含有A中元素的個(gè)數(shù)k進(jìn)行分類，k=0,1,…,r.然后使用加法法那么.組合恒等式解題方法小結(jié)證明方法：恒等式帶入二項(xiàng)式定理冪級(jí)數(shù)的求導(dǎo)、積分歸納法組合分析

求和方法：Pascal公式級(jí)數(shù)求和觀察和的結(jié)果，然后使用歸納法證明利用的公式非降路徑問題根本計(jì)數(shù)模型限制條件下的非降路徑數(shù)非降路徑模型的應(yīng)用證明恒等式單調(diào)函數(shù)計(jì)數(shù)棧的輸出根本計(jì)數(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ù)：乘法法那么限制條件的非降路徑數(shù)從(0,0)到(n,n)不接觸對(duì)角線的非降路徑數(shù)NN1：從(0,0)到(n,n)下不接觸對(duì)角線非降路徑數(shù)N2：從(1,0)到(n,n

1)下不接觸對(duì)角線非降路徑數(shù)N0:從(1,0)到(n,n

1)

的非降路徑數(shù)N3:從(1,0)到(n,n

1)

接觸對(duì)角線的非降路徑數(shù)關(guān)系:N=2N1=2N2=2[N0

N3]一一對(duì)應(yīng)N3:從(1,0)到(n,n

1)接觸對(duì)角線的非降路徑數(shù)N4:從(0,1)到(n,n

1)無限制條件的非降路徑數(shù)關(guān)系:N3=N4

應(yīng)用——證明恒等式例2

證明證：計(jì)數(shù)(0,0)到(m+n

r,r)的非降路徑數(shù)按照k分類，再分步.(0,0)到(m

k,k)路徑數(shù)，(m

k,k)到(m+n

r,r)的路徑數(shù)應(yīng)用——單調(diào)函數(shù)計(jì)數(shù)例3A={1,2,…,m},B={1,2,…,n}，N1:B上單調(diào)遞增函數(shù)個(gè)數(shù)是(1,1)到(n+1,n)的非降路徑數(shù)N:B上單調(diào)函數(shù)個(gè)數(shù)

N=2N1N2:A到B單調(diào)遞增函數(shù)個(gè)數(shù)是從(1,1)到(m+1,n)的非降路徑數(shù)N

:A到B的單調(diào)函數(shù)個(gè)數(shù)，N

=2N2

嚴(yán)格單調(diào)遞增函數(shù)、遞減函數(shù)個(gè)數(shù)都是C(n,m)

函數(shù)計(jì)數(shù)小結(jié)A={1,2,…,m},B={1,2,…,n}f:A

B應(yīng)用——棧輸出的計(jì)數(shù)例4將1,2,…,n按照順序輸入棧,有多少個(gè)不同的輸出序列？解：將進(jìn)棧、出棧分別記作x,y,出棧序列是n個(gè)x，n個(gè)y的排列，排列中任何前綴的x

個(gè)數(shù)不少于y的個(gè)數(shù).等于從(0,0)到(n,n)的不穿過對(duì)角線的非降路徑數(shù).實(shí)例：n=5

x,x,x,y,y,x,y,y,x,y

進(jìn),進(jìn),進(jìn),出,出,進(jìn),出,出,進(jìn),出

3,2,4,1,5應(yīng)用——棧輸出的計(jì)數(shù)(續(xù))N:堆棧輸出個(gè)數(shù)N

:(0,0)到(n,n)不穿過對(duì)角線的非降路徑數(shù)N0:(0,0)到(n,n)的非降路徑總數(shù)N1:(0,0)到(n,n)的穿過對(duì)角線的非降路徑數(shù)N2:(

1,1)到(n,n)的非降路徑數(shù).關(guān)系：N=N=N0

N1,N1=N28.4.1多項(xiàng)式定理8.4.2多項(xiàng)式系數(shù)12.4多項(xiàng)式定理多項(xiàng)式定理.定理12.5

設(shè)n為正整數(shù)，xi為實(shí)數(shù)，i=1,2,…,t.求和是對(duì)滿足方程n1+n2+…+nt=n的一切非負(fù)整數(shù)解求在n個(gè)因式中選n1個(gè)因式貢獻(xiàn)x1,從剩下n

n1個(gè)因式選n2個(gè)因式貢獻(xiàn)x2,…,從剩下的n

n1

n2

…

nt

1個(gè)因式中選nt個(gè)因式貢獻(xiàn)xt.證明展開式中的項(xiàng)是如下構(gòu)成的:推論推論1

多項(xiàng)式展開式中不同的項(xiàng)數(shù)為方程的非負(fù)整數(shù)解的個(gè)數(shù)

C(n+t

1,n)推論2

例1

求(2x1

3x2+5x3)6中x13x2x32的系數(shù).解由多項(xiàng)式定理得多項(xiàng)式系數(shù)組合意義多項(xiàng)式系數(shù)多重集S={n1

a1,n2

a2,…,nt

at}的全排列數(shù)

n個(gè)不同的球放到

t個(gè)不同的盒子使得第一個(gè)盒子含n1個(gè)球，第二個(gè)盒子含n2個(gè)球，…，第t個(gè)盒子含nt

個(gè)球的方案數(shù)多項(xiàng)式系數(shù)(續(xù))恒等式推論2定理12.5組合證明補(bǔ)充計(jì)數(shù)問題的應(yīng)用例17個(gè)科學(xué)工作者從事一項(xiàng)機(jī)密的技術(shù)研究，他們的工作