《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 第二章第二章 鴿巢原理和鴿巢原理和Ramsey定理定理組合存在性定理組合存在性定理lRamsey定理（鴿巢原理為其最簡形式）定理（鴿巢原理為其最簡形式）l偏序集分解定理（偏序集分解定理（Dilworth定理）定理）l相異代表系存在定理（相異代表系存在定理（Hall定理）定理）1928年英國數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟學(xué)家年英國數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟學(xué)家Frank，Ramsey(1903-1930)在倫敦數(shù)學(xué)會上宣讀一篇在倫敦數(shù)學(xué)會上宣讀一篇 “論形式邏輯中的一個問題論形式邏輯中的一個問題”的論文，奠定了的論文，奠定了 Ramsey理論的基礎(chǔ)。理論的基礎(chǔ)。核心思想是：核心思想是：“任何一個足夠大的結(jié)構(gòu)中必定包含任何一個足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則子結(jié)構(gòu)一個給定大小的規(guī)則子結(jié)構(gòu)”20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理第二章第二章 鴿巢原理和鴿巢原理和Ramsey定理定理2.1 鴿巢原理的簡單形式2.2 鴿巢原理的加強形式2.3 Ramsey定理20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理2.1 鴿巢原理的簡單形式鴿巢原理的簡單形式鴿巢原理是組合學(xué)中最簡單、最基本原理也叫抽屜原理抽屜原理(又稱為又稱為重疊原理重疊原理或或狄利克雷狄利克雷(Dirichlet)原理原理）。定理定理2.1.1若把n+1個物體放入n個盒子中，則至少有一個盒子中有2個或更多的物體20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理證明證明 如果每個盒子中至多有一如果每個盒子中至多有一個物體，那么個物體，那么n個盒子中至多有個盒子中至多有n個物體，而我們共有個物體，而我們共有n+1個物個物體，矛盾。體，矛盾。故定理成立。故定理成立。鴿巢原理的鴿巢原理的集合描述形式集合描述形式：設(shè)有限集合設(shè)有限集合A有有n+1個元素，將個元素，將A分劃成分劃成n個不個不相交子集的并，則至少有一個子集含有兩個或相交子集的并，則至少有一個子集含有兩個或兩個以上的元素。兩個以上的元素。定理是用群體的整體性表現(xiàn)出個體的某些特定理是用群體的整體性表現(xiàn)出個體的某些特性，屬于從宏觀到微觀的理論研究成果性，屬于從宏觀到微觀的理論研究成果注意注意 應(yīng)用時要分清物品與盒子以及物體數(shù)與盒子總數(shù)。應(yīng)用時要分清物品與盒子以及物體數(shù)與盒子總數(shù)。這個原理只能用來證明某種安排的這個原理只能用來證明某種安排的存在性存在性，而卻不，而卻不能找到具體滿足要求的安排能找到具體滿足要求的安排 不能被推廣到只存在不能被推廣到只存在n個個(或更少或更少)物體的情形。物體的情形。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.1 證明：13個人中必有兩人的屬相相同。u 幾個例子幾個例子例例2.1.2 有5雙不同的襪子混在一個抽屜里，我們至少從中選出多少只襪子才能保證找到1雙襪子？20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理解解 應(yīng)用定理應(yīng)用定理2.1.1，共有，共有5個盒子，個盒子，每個盒子對應(yīng)每個盒子對應(yīng)1雙襪子。雙襪子。如果選擇如果選擇5+1=6只襪子分別放到它所只襪子分別放到它所屬那雙襪子的盒子中，則必有兩只襪屬那雙襪子的盒子中，則必有兩只襪子落入同一個盒子中，即為一雙襪子。子落入同一個盒子中，即為一雙襪子。因此我們至少從中選出因此我們至少從中選出6只襪子才能只襪子才能保證找到保證找到1雙襪子。雙襪子。本例實際上是知道本例實際上是知道n個盒子，而找個盒子，而找n+1個物體的問題。個物體的問題。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.3對任意給定的對任意給定的52個整數(shù)，個整數(shù)，證明：其中必存在兩個整數(shù)，要么證明：其中必存在兩個整數(shù)，要么兩者的和能被兩者的和能被100整除，要么兩者整除，要么兩者的差能被的差能被100整除。整除。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理1 1、已知：、已知：、已知：、已知：5252個整數(shù)，個整數(shù)，個整數(shù)，個整數(shù)，2 2、目標(biāo)：找被、目標(biāo)：找被、目標(biāo)：找被、目標(biāo)：找被100100整除的兩個數(shù)整除的兩個數(shù)整除的兩個數(shù)整除的兩個數(shù)3 3、解題途徑：把、解題途徑：把、解題途徑：把、解題途徑：把5252個物體放到個物體放到個物體放到個物體放到5151個盒子中，需要構(gòu)個盒子中，需要構(gòu)個盒子中，需要構(gòu)個盒子中，需要構(gòu)造造造造5151個盒子個盒子個盒子個盒子4 4、根據(jù)題干中要求的兩個整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個整數(shù)必須具備的性質(zhì)構(gòu)造盒子盒子盒子盒子5 5、是否能夠被、是否能夠被、是否能夠被、是否能夠被100100整除的關(guān)鍵在余數(shù)，那么一個整數(shù)整除的關(guān)鍵在余數(shù)，那么一個整數(shù)整除的關(guān)鍵在余數(shù)，那么一個整數(shù)整除的關(guān)鍵在余數(shù)，那么一個整數(shù)除以除以除以除以100100的余數(shù)為的余數(shù)為的余數(shù)為的余數(shù)為0 0，1 1，2 2，9999n n 兩個整數(shù)的和可以被兩個整數(shù)的和可以被兩個整數(shù)的和可以被兩個整數(shù)的和可以被100100整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是100100n n 兩個整數(shù)的差可以被兩個整數(shù)的差可以被兩個整數(shù)的差可以被兩個整數(shù)的差可以被100100整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同分析：分析：證明：證明：對于任意一個整數(shù)，它除以對于任意一個整數(shù)，它除以100的余數(shù)的余數(shù)顯然只能有如下顯然只能有如下100種情況，種情況，0，1，2，3，99而現(xiàn)在有任意給定的而現(xiàn)在有任意給定的52個整數(shù)，我們需要構(gòu)個整數(shù)，我們需要構(gòu)造造51個盒子，即對這個盒子，即對這100個余數(shù)進行分組，個余數(shù)進行分組，共共51組：組：0，1，99，2，98，3，97，49，51，50根據(jù)定理根據(jù)定理2.1.1，這，這52個整數(shù)，必有兩個整數(shù)個整數(shù)，必有兩個整數(shù)除以除以100的余數(shù)落入上面的余數(shù)落入上面51組中的同一組中，組中的同一組中，若是若是0或或50則說明它們的和及差都能被則說明它們的和及差都能被100整除；整除；若是剩下的若是剩下的49組的話，因為一組有兩個余數(shù)，組的話，因為一組有兩個余數(shù)，余數(shù)相同則它們的差能被余數(shù)相同則它們的差能被100整除，余數(shù)不同整除，余數(shù)不同則它們的和能被則它們的和能被100整除。整除。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.4 一名象棋大師有一名象棋大師有11周時間準(zhǔn)備周時間準(zhǔn)備一場錦標(biāo)賽，她決定每天至少下一盤一場錦標(biāo)賽，她決定每天至少下一盤棋，為了不能太累一周中下棋的次數(shù)棋，為了不能太累一周中下棋的次數(shù)不能多于不能多于12盤。盤。證明證明：她一定在此期：她一定在此期間的連續(xù)若干天中恰好下棋間的連續(xù)若干天中恰好下棋21盤。盤。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理1、題干提供的信息：一共、題干提供的信息：一共11周周2、約束條件：、約束條件：n n 每每周周最多下最多下12盤棋盤棋n n 每每天天至少下至少下1盤棋盤棋 3、目標(biāo)：連續(xù)若干、目標(biāo)：連續(xù)若干天天共下棋共下棋21盤盤4、解題途徑：構(gòu)造下棋盤數(shù)的部分和、解題途徑：構(gòu)造下棋盤數(shù)的部分和分析：分析：20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理證明:令b1，b2，b77分別為這11周中他每天下棋的次數(shù)，并作部分和a1=b1,a2=b1+b2,，a77=b1+b2+b77.20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理所以有所以有1a1a2a3a771211=132(2.1.1)考慮數(shù)列考慮數(shù)列a1,a2,，a77，a1+21,a2+21,，a77+21,它們都在它們都在1與與132+21=153之間，共有之間，共有154項，項，由定理由定理2.1.1知，其中必有兩項相等知，其中必有兩項相等根據(jù)題意，有bi1(1i77),且bi+bi+1+bi+612(1i71),20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理由（由（2.1.1）式知）式知a1,a2,，a77這這77項互不相等，項互不相等，從而從而a1+21,a2+21,，a77+21這這77項也互不相項也互不相等，所以一定存在等，所以一定存在1i aj，則ai與從aj開始的最長遞減子序列合并，組成的子序列的長度Li=Lj+1 Lj；這與Li=Lj矛盾；反證法。假設(shè)既不存在長度為n+1的遞增子序列，也不存在長度為n+1的遞減子序列即1Lin 且 1Min，其中1in2+1，由集合論的知識知道集合(Li,Mi)的元素數(shù)為n2，根據(jù)定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i j），當(dāng)然Li=Lj，而且Mi=Mj。對于序列中的元素ai,aj，分兩種情況：20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理（2）若ai Mj，這又與Mi=Mj矛盾。所以假設(shè)1Lin 且 1Min不成立。原結(jié)論成立。這個例子的結(jié)論是1935年由數(shù)學(xué)家保羅艾狄胥（Erds）和喬治塞克爾斯（Szekeres）首先給出的，它還有更為有趣的表述：n2+1個人肩并肩地站成一排，則總能選出n+1個人，讓他們向前邁出一步，所形成新一排的身高是遞增或遞減的。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理定理定理2.1.1 鴿巢原理簡單形式鴿巢原理簡單形式若把n+1個物體放入n個盒子中，則至少有一個盒子中有2個或更多的物體思考？把多少個物體放到 n 個盒子中，能保證至少存在一個盒子中包含 r 個以上物體？20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理定理定理2.2.1的推論的推論推論推論2.2.1若若 n(r1)+1個物品個物品放入放入n個盒個盒子子。則則至少有一個至少有一個盒子里含有盒子里含有r個或者更多個或者更多的物品。的物品。證明證明 在定理在定理2.2.1中取中取q1=q2=qn=r即可。即可。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理2.2 鴿巢原理的加強形式鴿巢原理的加強形式定理定理2.2.1 (鴿巢原理的加強形式鴿巢原理的加強形式)2鴿巢原理的加強形式鴿巢原理的加強形式定理定理2.2.1 的證明的證明證明證明:(反證法反證法)對于對于i1，2，n，假設(shè)第，假設(shè)第i個盒子里至個盒子里至多含有多含有qi-1個物品，則個物品，則n個盒子里物品數(shù)的個盒子里物品數(shù)的總和不超過總和不超過 q1+q2+qn n 個個與已知條件與已知條件(q1+q2+qn n+1)矛盾。矛盾。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理 與簡單形式的關(guān)系與簡單形式的關(guān)系 上節(jié)的鴿巢原理的簡單形式是這一原理的特殊情況，即q1=q2=qn=2，有 q1+q2+qnn+1=n+120222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理 推論推論2.2.2 若若設(shè)有設(shè)有n個正整數(shù)個正整數(shù)m1,m2,mn滿足下面的不等式滿足下面的不等式 (m1+mn)/n r1,則則 m1,mn中至少有一個數(shù)中至少有一個數(shù) r證明證明 由上面的不等式得 m1+mn(r1)n+1，由推論2.2.1，存在mi，使得mir。另外一個平均原理：另外一個平均原理：設(shè)有設(shè)有n個正整數(shù)個正整數(shù)m1,m2,mn滿足下面的不等式滿足下面的不等式 (m1+mn)/n r+1,則則 m1,mn中至少有一個數(shù)中至少有一個數(shù)n，若將m個物體放入n個盒子中，則至少有一個盒子中有大于等于 個物體表示取天棚運算是大于等于 的最小正整數(shù) 證明：證明：根據(jù) 的定義有：反證法。假定每個盒子里的物體都小于 個。，則至多是 個，那么n個盒子里的物體總數(shù)n()n =m，與m個物體矛盾。因此原結(jié)論成立。 習(xí)題二 2.1 證明：在一個至少有2人的小組中，總存在兩個人，他們在組內(nèi)所認(rèn)識的人數(shù)相同。證明：假設(shè)沒有人誰都不認(rèn)識：那么每個人認(rèn)識的人數(shù)都為1,n-1，由鴿巢原理知，n個人認(rèn)識的人數(shù)有n-1種，那么至少有2個人認(rèn)識的人數(shù)相同。 假設(shè)有1人誰都不認(rèn)識：那么其他n-1人認(rèn)識的人數(shù)都為1,n-2，由鴿巢原理知，n-1個人認(rèn)識的人數(shù)有n-2種，那么至少有2個人認(rèn)識的人數(shù)相同。假設(shè)至少有兩人誰都不認(rèn)識，則認(rèn)識的人數(shù)為0的至少有兩人。2.2 任取11個整數(shù)，求證其中至少有兩個數(shù)的差是10的整數(shù)倍。證明：對于任意的一個整數(shù)，它除以10的余數(shù)只能有10種情況：0，1，9。現(xiàn)在有11個整數(shù)，由鴿巢原理知，至少有2個整數(shù)的余數(shù)相同，則這兩個整數(shù)的差必是10的整數(shù)倍。2.3 證明：平面上任取5個坐標(biāo)為整數(shù)的點，則其中至少有兩個點，由它們所連線段的中點的坐標(biāo)也是整數(shù)。2.3證明：有5個坐標(biāo)，每個坐標(biāo)只有4種可能的情況：（奇數(shù)，偶數(shù)）；（奇數(shù)，奇數(shù)）；（偶數(shù)，偶數(shù)）；（偶數(shù)，奇數(shù)）。由鴿巢原理知，至少有2個坐標(biāo)的情況相同。又要想使中點的坐標(biāo)也是整數(shù)，則其兩點連線的坐標(biāo)之和為偶數(shù)。因為 奇數(shù)+奇數(shù) = 偶數(shù) ； 偶數(shù)+偶數(shù)=偶數(shù)。因此只需找以上2個情況相同的點。而已證明：存在至少2個坐標(biāo)的情況相同。證明成立。2.4 一次選秀活動，每個人表演后可能得到的結(jié)果分別為“通過”、“淘汰”和“待定”，至少有多少人參加才能保證必有100個人得到相同的結(jié)果？證明： 根據(jù)推論2.2.1，若將3*（100-1）+1=298個人得到3種結(jié)果，必有100人得到相同結(jié)果。2.5 一個袋子里裝了100個蘋果、100個香蕉、100個橘子和100個梨。那么至少取出多少水果后能夠保證已經(jīng)拿出20個相同種類的水果？證明：根據(jù)推論2.2.1，若將4*（20-1）+ 1 = 77個水果取出，必有20個相同種類的水果。2.6 證明：在任意選取的n+2個正整數(shù)中存在兩個正整數(shù)，其差或和能被2n整除。（書上例題2.1.3）證明：對于任意一個整數(shù)，它除以2n的余數(shù)顯然只有2n種情況，即：0，1，2，2n-2，2n-1。而現(xiàn)在有任意給定的n+2個整數(shù)，我們需要構(gòu)造n+1個盒子，即對上面2n個余數(shù)進行分組，共n+1組： 0,1，2n-1,2，2n-2,3,2n-3,，n-1,n+1，n。根據(jù)鴿巢原理，n+2個整數(shù)，必有兩個整數(shù)除以2n落入上面n+1個盒子里中的一個，若是0或n則說明它們的和及差都能被2n整除；若是剩下n-1組，因為一組有兩個余數(shù)，余數(shù)相同則它們的差能被2n整除，不同則它們的和能被2n整除。證明成立。2.7 一個網(wǎng)站在9天中被訪問了1800次，證明：存在連續(xù)的3天，這個網(wǎng)站的訪問量超多600次。證明： 設(shè)網(wǎng)站在9天中訪問數(shù)分別為a1，a2，.，a9 其中a1+a2+.+a9 = 1800， 令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3因為（b1+b2+b3）/3 = 600 由推論2.2.2知，b1，b2，b3中至少有一個數(shù)大于等于600。 所以存在有連續(xù)的三天，訪問量大于等于600次。2.8 將一個矩形分成5行41列的網(wǎng)格，每個格子涂1種顏色，有4種顏色可以選擇，證明：無論怎樣涂色，其中必有一個由格子構(gòu)成的矩形的4個角上的格子被涂上同一種顏色。證明：首先對一列而言，因為有5行，只有4只顏色選擇，根據(jù)鴿巢原理，則必有兩個單元格的顏色相同。另外，每列中兩個單元格的不同位置組合有=10種，這樣一列中兩個同色單元格的位置組合共有10*4=40種情況。 而現(xiàn)在共有41列，根據(jù)鴿巢原理，無論怎樣涂色，則必有兩列相同，也就是必有一個由格子構(gòu)成的矩形的4個角上的格子是同一顏色。2.9 將一個矩形分成(m+1)行列的網(wǎng)格每個格子涂1種顏色，有m種顏色可以選擇，證明：無論怎么涂色，其中必有一個由格子構(gòu)成的矩形的4個角上的格子被涂上同一種顏色。證明： （1）對每一列而言，有（m+1）行，m種顏色，有鴿巢原理，則必有兩個單元格顏色相同。 （2）每列中兩個單元格的不同位置組合有種，這樣一列中兩個同色單元格的位置組合共有 種情況 （3）現(xiàn)在有列，根據(jù)鴿巢原理，必有兩列相同。證明結(jié)論成立。2.10 一名實驗員在50天里每天至少做一次實驗，而實驗總次數(shù)不超過75。證明一定存在連續(xù)的若干天，她正好做了24次實驗。證明：令b1，b2，.，b50 分別為這50天中他每天的實驗數(shù)，并做部分和 a1 = b1，a2 = b1+b2 ，。a50 = b1+b2+.+b50 .由題，bi=1(1=i=50)且a50=75所以 1=a1a2a3a50=75 (*)考慮數(shù)列 a1，a2，.，a50，a1+24，a2+24，a50+24，它們都在1與75+24=99之間。由鴿巢原理知，其中必有兩項相等。由（*）知，a1，a2，.，a50互不相等，從而a1+24，.a50+24 也互不相等，所以一定存在1=ij1,f(1)=2 f(n)可以由f(n)來生成，當(dāng)在f(n)個大圓的基礎(chǔ)上，在球面上再加上第n+1個大圓時，它同前n個大圓共得到2n個交點(因無三個大圓相交于一點)，而每增加一個交點就增加一個新的面，故共增加2n個面。所以有f(n+1)= f(n)+2n。設(shè)P是平面上n個連通區(qū)域D1,D2,Dn的公共交界點，如下圖所示?，F(xiàn)用k種顏色對其著色，要求有公共邊界的相鄰區(qū)域著以不同的顏色，令f(n)表示不同的著色方案。，求它所滿足的遞推關(guān)系。有： f(n)= (k-1)f(n-2)+(k-2)f(n-1) （n4） f(2)=k(k-1) ， f(3)=k(k-1)(k-2)(1) 有D1與Dn-1同色，此時Dn有k-1種方案，可將D1與D n-2看成相鄰區(qū)域，則D1,D2, , Dn-2的著色方案為f(n-2)。(2) D1與Dn-1異色，此時Dn有k-2種方案，可將，則D1,D2, , Dn-1的著色方案為f(n-1)。(k-1)f(n-2)+(k-2)f(n-1)另有：f(n)=k(k-1)n-1-f(n-1) 第七章例n種顏色涂色裝有7顆珠子的手鐲，如果只考慮手鐲的旋轉(zhuǎn)，求有多少種涂色方案？ 解 對象集D1,2,3,4,5,6,7，顏色集是R(1,2,3,n)，D上的置換群Gg0,g1,g2,g6，其中g(shù)i表示旋轉(zhuǎn)360*i/7，因7是質(zhì)數(shù)，所以除(g0)7外，其它(gi)1，(i=1,2,3,4,5,6)，代入Polya公式，得L1/7*n7+6n而四邊形：轉(zhuǎn)180時3.2.2 集合排列和組合的生成集合排列和組合的生成l 排列的生成方法排列的生成方法l(a)鄰位互換法鄰位互換法l(b)字典序法字典序法l 組合的生成方法組合的生成方法l (a)生成集合生成集合I=1,2,n的所有組合的所有組合 字典序字典序 格雷碼格雷碼l (b)生成集合生成集合I=1,2,n的所有的所有r組合組合對稱性，遞推性，單峰性對稱性，遞推性，單峰性二項式定理二項式定理設(shè)n是正整數(shù),則對任意的x,y有：牛頓二項式定理牛頓二項式定理設(shè)設(shè)是一個實數(shù)，則對一切是一個實數(shù)，則對一切x和和y，滿足，滿足 ,有有 多項式定理多項式定理設(shè)設(shè)n是正整數(shù)，則是正整數(shù)，則其中其中稱為多項式系數(shù)稱為多項式系數(shù)，并且是對所有滿足，并且是對所有滿足n1+n2+nt=n 的非負(fù)整數(shù)解的非負(fù)整數(shù)解 n1,n2,nt求求和。和。證明組合恒等式的證明組合恒等式的方法方法：v 代數(shù)方法：代數(shù)方法：通過代入組合數(shù)的值或已知的組合恒通過代入組合數(shù)的值或已知的組合恒等式進行計算或化簡，使等式兩邊相等等式進行計算或化簡，使等式兩邊相等v 二項式定理：二項式定理：v比較展開式中比較展開式中xr的系數(shù)，的系數(shù)，v在展開式中令在展開式中令x和和y為某個特定的值為某個特定的值v利用冪級數(shù)的利用冪級數(shù)的微分或積分微分或積分等數(shù)學(xué)分析的方法等數(shù)學(xué)分析的方法v 數(shù)學(xué)歸納法數(shù)學(xué)歸納法v 組合分析方法組合分析方法：說明等式兩邊都是對同一組合問說明等式兩邊都是對同一組合問題的計數(shù)題的計數(shù) 基本模型基本模型 非降路徑模型應(yīng)用非降路徑模型應(yīng)用l組合恒等式證明組合恒等式證明 限定條件下的非降路徑數(shù)限定條件下的非降路徑數(shù)l應(yīng)用實例應(yīng)用實例3.4.5 非降路徑問題非降路徑問題基本模型描述基本模型描述從從(0,0)點開始點開始,水平向右走一水平向右走一步為步為x,垂直向垂直向上走一步為上走一步為y，則走到則走到(m,n)點點水平向右要走水平向右要走m步步,垂直向上垂直向上要走要走n步步(0,0)(m,n)yx從從(0，0)點到點到(5，6)點的一條非降路徑，規(guī)定水平向點的一條非降路徑，規(guī)定水平向右走一個單元格用右走一個單元格用x表示，垂直向上走一個單元格用表示，垂直向上走一個單元格用y表表示，則此路經(jīng)對應(yīng)于排列示，則此路經(jīng)對應(yīng)于排列xyxxyyyxxyy。反過來，按照。反過來，按照以上規(guī)則，給定排列以上規(guī)則，給定排列xyxxyyyxxyy，就對應(yīng)了如圖所示，就對應(yīng)了如圖所示的非降路徑。的非降路徑。(0,0)(5,6)yx 一般地，一條一般地，一條從從(0,0)點到點到(m,n)點的非降路徑點的非降路徑就就是是多重集多重集mx，ny的一個排列的一個排列。反之，反之，給給定多重集定多重集mx，ny的一個排列就唯的一個排列就唯一地確定了一條從一地確定了一條從(0,0)點到點到(m,n)點的非降路徑。點的非降路徑。(0,0)(m,n)yx(p,q)x(0,0)y(r,s)補充補充1 從從(p,q)點到點到(r,s)點，這里點，這里pr,qn.(0,0)yx(m,n)(-1,1)y=x+1解解 根據(jù)題意，要滿足總是能找出零錢，就意味著對于隊列中每根據(jù)題意，要滿足總是能找出零錢，就意味著對于隊列中每個歌迷而言，她前面的人個歌迷而言，她前面的人(包括她在內(nèi)包括她在內(nèi))中持中持50元的人不少于持元的人不少于持100元的人。顯然是求從元的人。顯然是求從(0，0)到到(m,n)不穿過直線不穿過直線y=x且在且在y=x下下方的非降路徑數(shù)，方的非降路徑數(shù)，歷年試題填空一場演唱會門票為50元一張，排隊買票的歌迷中有n個人手持50元紙幣，n個人手持100元紙幣。假定每個人只能購票1張，售票處沒有準(zhǔn)備零錢，那么售票處不會找不出錢的概率為（）。3.5 集合的分劃與集合的分劃與Stirling數(shù)數(shù)3.5.1 集合的分劃與第二類集合的分劃與第二類Stirling數(shù)數(shù) 定義定義3.5.1 集合S的子集族稱為n元集S的一個k-分劃，如果這個子集族滿足1.每個Si非空；2.當(dāng)ij時，3.其中每個其中每個Si稱稱為為一個分劃一個分劃塊塊，也把，也把這這個個k-分劃分劃記為記為：例例3.5.1 集合A=1,2,3,4有7個2-分劃，它們是 定義定義3.5.2 一個n元集合的全部k-分劃的個數(shù)記為第二類Stirling數(shù)，表示為或 S2(n,k)(1)(2)定理定理3.5.1 第二類第二類Stirling數(shù)數(shù) 滿足如下遞推關(guān)系滿足如下遞推關(guān)系 證明證明 等式左邊等式左邊 是集合是集合的的k-分劃的個數(shù)，這些分劃的個數(shù)，這些k-分劃可以分成兩類分劃可以分成兩類:第第1類：類：an是是A的的k-分劃中的一塊，這時，分劃中的一塊，這時，只需對集合只需對集合A-an進行進行(k1)-分劃，再加上分劃，再加上an這一塊，就構(gòu)成了這一塊，就構(gòu)成了A的的k-分劃，因此，這分劃，因此，這類分劃有類分劃有 個；個；第第2類：類：an不是不是A的的k-分劃中單獨的一塊，分劃中單獨的一塊，此時，先構(gòu)造此時，先構(gòu)造A-an的的k-分劃，共有分劃，共有 種方法。種方法。然后，對于然后，對于A-an的每個的每個k-分劃，將分劃，將an加加到該到該k-分劃的分劃的k個塊中的某一塊，從而構(gòu)成個塊中的某一塊，從而構(gòu)成A的的k-分劃分劃 因此由乘法原理，集合因此由乘法原理，集合A的此類的此類k-分劃共分劃共有有 個個綜上以上，由加法原理綜上以上，由加法原理定理定理3.5.2 第二類第二類Stirling數(shù)滿足下列性質(zhì)：數(shù)滿足下列性質(zhì)：性質(zhì)性質(zhì)(1)性質(zhì)性質(zhì)(2)(1)組合意義組合意義是n元集合 的2-分劃數(shù)，先取出a1,則對于 a2,a3,an，每個元素都有兩種選擇，即與a1在同一塊里或者ai與a1不在同一塊里，不同的選擇就構(gòu)成了集合A的不同的2-分劃，但這里要排除掉a2,a3,an，都與a1在同一塊中的情形(此時不構(gòu)成集合A的2-分劃 由此可知，n元集合A的2-分劃數(shù)為2n-1-1 證明證明 (2)是是n元集合的元集合的(n-1)-分劃，由于分劃中分劃，由于分劃中各各塊塊是非空的，所以每個是非空的，所以每個(n-1)-分劃中必有分劃中必有一一塊為塊為兩個元素，其余各兩個元素，其余各塊塊都恰有一個元都恰有一個元素，所以，素，所以，對對于于n元集合的每個元集合的每個(n-1)-分劃，分劃，只要確定了有兩個元素的那一只要確定了有兩個元素的那一塊塊，整個，整個(n-1)-分劃就確定了分劃就確定了 因此，因此，就是在就是在n元集中元集中選選取取2個元素的個元素的 方法數(shù)方法數(shù) 組合意義組合意義3.5.2 第一類第一類Stirling數(shù)數(shù) 第一類Stirling數(shù)也與集合的分劃相關(guān) 集合有7個2-分劃，但我們要求將每個分劃塊做成圓排列(或者輪換)，則共可構(gòu)成11個不同的圓排列組定義定義3.5.3 一個一個n元集合的全部元集合的全部k-分劃所分劃所形成的不同的圓排列組的個數(shù)，即形成的不同的圓排列組的個數(shù)，即k-圓圓排列分劃數(shù)記為第一類排列分劃數(shù)記為第一類Stirling數(shù)，表示數(shù)，表示為為 或或S1(n,k)性質(zhì)性質(zhì)(1)性質(zhì)性質(zhì)(2)性質(zhì)性質(zhì)(3)性質(zhì)性質(zhì)(4)定理定理3.5.3 第一類Stirling數(shù)滿足如下遞推關(guān)系 證證明明：等式左邊 是將集合的k-圓排列分劃數(shù)，這些圓排列組可以分成兩類：第1類：an單獨構(gòu)成一個圓排列，只需對集合A-an進行(k-1)-圓排列分劃，再加上an這個圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個。第2類：an不是A的k-圓排列分劃中的單獨一個圓排列，此時，先構(gòu)造A-an的k-圓排列分劃，共有 種方法，然后對于A-an的每個k-圓排列分劃，將an插入該k-圓排列分劃的k個圓排列中的某一個圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個。綜上以上分析，由加法原理，有 第一類第一類Stirling數(shù)的三角形數(shù)的三角形1第五章第五章 生成函數(shù)生成函數(shù)n5.1 生成函數(shù)的定義和性質(zhì)生成函數(shù)的定義和性質(zhì)n5.2 組合數(shù)的生成函數(shù)組合數(shù)的生成函數(shù)n5.5 分拆數(shù)的生成函數(shù)分拆數(shù)的生成函數(shù)n5.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)n5.4 Catalan數(shù)列數(shù)列與與Stirling數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)5.2 組合數(shù)的生成函數(shù)組合數(shù)的生成函數(shù)我們在前面幾章中討論過三種不同類型的組合問題：我們在前面幾章中討論過三種不同類型的組合問題：n求求 的的r組合數(shù)；組合數(shù)；n求求 的的r組合數(shù)；組合數(shù)；n求求 的的10組合數(shù)。組合數(shù)。n其中其中:n問題（問題（1）是普通集合的組合問題；）是普通集合的組合問題；n問題（問題（2）轉(zhuǎn)化為不定方程）轉(zhuǎn)化為不定方程 的非負(fù)整數(shù)解的個數(shù)的非負(fù)整數(shù)解的個數(shù)問題；問題；n問題（問題（3）是第四章的例子，利用容斥原理來計數(shù)。它們在解）是第四章的例子，利用容斥原理來計數(shù)。它們在解題方法上各不相同。題方法上各不相同。n下面我們將看到，引入生成函數(shù)的概念后，上述三類組合問下面我們將看到，引入生成函數(shù)的概念后，上述三類組合問題可以統(tǒng)一地處理題可以統(tǒng)一地處理2n定理定理 5.3.1 設(shè)多重集設(shè)多重集 ，則則M的的k-組合數(shù)組合數(shù) ck 對應(yīng)序列對應(yīng)序列 的生成函數(shù)為的生成函數(shù)為 n其中，其中，ck 為為 展開式中展開式中 的系數(shù)。的系數(shù)。3證明證明:令令 中各中各 的項分別對應(yīng)的項分別對應(yīng)各個各個元素的元素的可能取法。例如可能取法。例如，對，對 時時x2表示元素表示元素a2 選取了選取了 2次次，其中，其中依次類推。依次類推。展開式中的項展開式中的項 xk 具有一般形式具有一般形式 其中其中 對此方程的一非負(fù)整數(shù)解對此方程的一非負(fù)整數(shù)解 (滿足條件滿足條件 下下)，相應(yīng)的相應(yīng)的 就對應(yīng)了就對應(yīng)了M的的一個一個k-組合組合因此因此合并同類項后，合并同類項后，xk的系數(shù)就表示了的系數(shù)就表示了M的的k-組合數(shù)組合數(shù)。4n例例5.2.1 利用生成函數(shù)方法求利用生成函數(shù)方法求 的的k-組合數(shù)。組合數(shù)。5解解 設(shè)設(shè) 的的k-組合數(shù)為組合數(shù)為 ，則，則數(shù)列數(shù)列 的生成函數(shù)為：的生成函數(shù)為：其中其中 的系數(shù)就是的系數(shù)就是 M 的的k-組合數(shù)組合數(shù) ，這個結(jié)果顯然與第三章中定理這個結(jié)果顯然與第三章中定理3.3.3是一致的。是一致的。6n推論推論5.2.1 設(shè)設(shè) ，若限定在，若限定在k-組合中元素組合中元素 出現(xiàn)的次數(shù)集合為出現(xiàn)的次數(shù)集合為 ，則從，則從M的的k-組合數(shù)組合數(shù) 對應(yīng)序列對應(yīng)序列 的生成函數(shù)為的生成函數(shù)為7n例例5.2.2 用生成函數(shù)方法求多重集合用生成函數(shù)方法求多重集合 的的10-組合數(shù)。組合數(shù)。解解 將將 的的k-組合數(shù)記為組合數(shù)記為 ，的生的生成函數(shù)是成函數(shù)是所以，所以，的系數(shù)的系數(shù) 為為與第與第4章中用容斥原理得到的結(jié)果相同。章中用容斥原理得到的結(jié)果相同。8n在普通集合在普通集合 的的k-組合中，組合中，或出現(xiàn)或不出現(xiàn)，故其或出現(xiàn)或不出現(xiàn)，故其k-組合數(shù)數(shù)列組合數(shù)數(shù)列 的生成函數(shù)為的生成函數(shù)為 從而從而例例5.2.3 求求 的每個元素至少的每個元素至少取一次的取一次的k-組合數(shù)。組合數(shù)。9n解解 設(shè)設(shè) 的每個元素至少取一的每個元素至少取一次的次的k-組合數(shù)組合數(shù) 對應(yīng)數(shù)列對應(yīng)數(shù)列 的生成函數(shù)為的生成函數(shù)為 為為 的系數(shù)的系數(shù) 。10n例例5.2.4 求方程求方程 的整數(shù)解的個數(shù)。的整數(shù)解的個數(shù)。解：解：設(shè)方程的設(shè)方程的 整數(shù)解數(shù)為整數(shù)解數(shù)為 ，數(shù)列，數(shù)列 對應(yīng)的生成函數(shù)為對應(yīng)的生成函數(shù)為我們所求的是我們所求的是 為為 展開式中展開式中 的系數(shù)的系數(shù)11n例例5.2.5 求方程求方程 x1+2x2=15 的非負(fù)整數(shù)解的個數(shù)。的非負(fù)整數(shù)解的個數(shù)。n解解 設(shè)方程設(shè)方程 x1+2x2=k 的非負(fù)整數(shù)解的個數(shù)為的非負(fù)整數(shù)解的個數(shù)為 ak ,ak的生成函數(shù)為的生成函數(shù)為 因此，因此，a15=8.12n例例5.2.6 假定有足夠多的蘋果、香蕉、橘子和梨，用這假定有足夠多的蘋果、香蕉、橘子和梨，用這4種水果裝成由種水果裝成由k個水果的構(gòu)成水果袋，要求水果袋中個水果的構(gòu)成水果袋，要求水果袋中蘋果數(shù)為偶數(shù)，香蕉數(shù)是蘋果數(shù)為偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多有的倍數(shù)，橘子最多有4個，個，梨的個數(shù)是梨的個數(shù)是0或者或者1，求可以有多少種不同的裝法？，求可以有多少種不同的裝法？n解解 設(shè)有設(shè)有ck種裝法，則數(shù)列種裝法，則數(shù)列ck對應(yīng)的生成函數(shù)對應(yīng)的生成函數(shù)n因此，有因此，有k+1種不同的裝法。種不同的裝法。135.5.1 有序分拆有序分拆定理定理5.5.1 對于對于n的的k有序分拆有序分拆其其k有序分拆數(shù)數(shù)列有序分拆數(shù)數(shù)列 的生成函數(shù)是的生成函數(shù)是這個定理等價于如下分配模型：即把這個定理等價于如下分配模型：即把n個相同的球放入個相同的球放入k個不同的盒子里，第個不同的盒子里，第i個盒的容量為個盒的容量為 ，且使每盒非空，且使每盒非空的方案數(shù)為的方案數(shù)為14n推論推論5.5.1 若對若對n的的k有序分拆的各分量有序分拆的各分量()沒有沒有限制，則其限制，則其k有序分拆數(shù)數(shù)列有序分拆數(shù)數(shù)列 的生成函數(shù)是的生成函數(shù)是 ，且且 155.5.2 無序分拆無序分拆n在在3.6節(jié)中可知無序分拆和有序分拆的區(qū)別在于是否考節(jié)中可知無序分拆和有序分拆的區(qū)別在于是否考慮分拆后的各分量的順序，慮分拆后的各分量的順序，n將將n分拆為分拆為k個分部（每一分部的大小不受限制）的分個分部（每一分部的大小不受限制）的分拆數(shù)等于將拆數(shù)等于將n分拆為最大分部為分拆為最大分部為k（分部個數(shù)不限）的（分部個數(shù)不限）的分拆數(shù)，該分拆數(shù)也記為分拆數(shù)，該分拆數(shù)也記為 16定理定理5.5.2 令令B(n)表示正整數(shù)表示正整數(shù) 的所有分拆數(shù)，的所有分拆數(shù)，Bk(n)表示表示 n的各分部量都不超過的各分部量都不超過 k的分拆數(shù)，則它們相應(yīng)的生成的分拆數(shù)，則它們相應(yīng)的生成函數(shù)分別為函數(shù)分別為(1)(2)(3)17（1）等于不定方程等于不定方程 的非負(fù)整數(shù)解的個數(shù)。因此其分拆數(shù)列的生成函數(shù)為的非負(fù)整數(shù)解的個數(shù)。因此其分拆數(shù)列的生成函數(shù)為 其中展開式中其中展開式中 的系數(shù)即為的系數(shù)即為n的最大分項不超過的最大分項不超過k的分拆個的分拆個數(shù)。數(shù)。18（2）根據(jù)定理根據(jù)定理 3.6.3知，將知，將n分拆為分拆為k個分部（每一分部的大個分部（每一分部的大小不受限制）的分拆數(shù)等于將小不受限制）的分拆數(shù)等于將n分拆為最大分部為分拆為最大分部為k（分部（分部個數(shù)不限）的分拆數(shù)，其分拆數(shù)相當(dāng)于求方程個數(shù)不限）的分拆數(shù)，其分拆數(shù)相當(dāng)于求方程的整數(shù)解的個數(shù)，其生成函數(shù)為的整數(shù)解的個數(shù)，其生成函數(shù)為19其中展開式中其中展開式中 的系數(shù)即為的系數(shù)即為n的最大分項等于的最大分項等于k的分拆個數(shù)的分拆個數(shù)若若 ，則，則 ，因此當(dāng)，因此當(dāng) ，它，它們對應(yīng)的生成函數(shù)的系數(shù)為零，所以們對應(yīng)的生成函數(shù)的系數(shù)為零，所以20容易證明：容易證明：，因此，因此21（3）等于不定方程等于不定方程 的非負(fù)整數(shù)解的個數(shù)。因此其分拆數(shù)列的生成函數(shù)為的非負(fù)整數(shù)解的個數(shù)。因此其分拆數(shù)列的生成函數(shù)為 22推論推論5.5.2 n 的各分部量兩兩互不相同的分拆數(shù)等于的各分部量兩兩互不相同的分拆數(shù)等于 n的的各分部量是奇數(shù)的分拆數(shù)。各分部量是奇數(shù)的分拆數(shù)。證明證明 n的各分部量兩兩互不相同的分拆數(shù)的生成函數(shù)為的各分部量兩兩互不相同的分拆數(shù)的生成函數(shù)為 而而 顯然是顯然是n的各分部量是奇數(shù)的分拆的各分部量是奇數(shù)的分拆 數(shù)數(shù)列的生成函數(shù)，因此結(jié)論成立數(shù)數(shù)列的生成函數(shù)，因此結(jié)論成立.23例例 5.5.1 用用1角、角、2角、角、3角的郵票貼出面值角的郵票貼出面值6角，求有多少種不角，求有多少種不同的方案？同的方案？解解 這是可重復(fù)的無序分拆，相應(yīng)的生成函數(shù)為這是可重復(fù)的無序分拆，相應(yīng)的生成函數(shù)為顯然所求為顯然所求為 的系數(shù)，為的系數(shù)，為7，說明貼出，說明貼出6角面值的方案有角面值的方案有7種。具體為：種。具體為：6=1+1+1+1，6=2+2+2，6=2+2+1+1，6=2+1+1+1+1，6=3+3，6=3+2+1，6=3+1+1+1.例例5.5.1中，若考慮不同面值貼的順序，則有多少種方案。此問題留作習(xí)題中，若考慮不同面值貼的順序，則有多少種方案。此問題留作習(xí)題245.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)25n當(dāng)涉及到與排列有關(guān)的問題時，需要引入指數(shù)型生成當(dāng)涉及到與排列有關(guān)的問題時，需要引入指數(shù)型生成函數(shù)。函數(shù)。n例如例如n 元集合的元集合的k 排列數(shù)為排列數(shù)為 ，n 其對應(yīng)的組合型生成函數(shù)其對應(yīng)的組合型生成函數(shù)為：為：n 沒有簡單的解析表達式，但如果把基底函數(shù)沒有簡單的解析表達式，但如果把基底函數(shù) 改換成改換成 n ，則，則n這啟發(fā)人們引入指數(shù)型生成函數(shù)的概念。這啟發(fā)人們引入指數(shù)型生成函數(shù)的概念。5.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)n定義定義5.3.1 數(shù)列數(shù)列 的指數(shù)型生成函數(shù)定義的指數(shù)型生成函數(shù)定義為形式冪級數(shù)為形式冪級數(shù)記為記為 或者或者26n例如，考慮前面多次提到的數(shù)列例如，考慮前面多次提到的數(shù)列1,1,1，根據(jù)定義，根據(jù)定義5.3.1有有 ，而根據(jù)高等數(shù)學(xué)的知識，而根據(jù)高等數(shù)學(xué)的知識，因此因此n特別地，數(shù)列特別地，數(shù)列 的指數(shù)型生成函數(shù)的指數(shù)型生成函數(shù) 具有與指數(shù)函數(shù)相似具有與指數(shù)函數(shù)相似的性質(zhì)：的性質(zhì)：2728例例5.3.1 求排列數(shù)數(shù)列求排列數(shù)數(shù)列 的指數(shù)型生成函數(shù)的指數(shù)型生成函數(shù)，其其中中 解：解：設(shè)要求的生成函數(shù)為設(shè)要求的生成函數(shù)為Ge(x)，根據(jù)定義，根據(jù)定義5.1.129例例5.3.2 求多重集合求多重集合 的的k-排列數(shù)排列數(shù)bk.解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，根據(jù)定理，根據(jù)定理5.3.1有，有，從而從而 ，與第，與第3章中的結(jié)果是一致的。章中的結(jié)果是一致的。30定理定理 5.3.1 設(shè)設(shè) ,考慮考慮 M 的的k-排列排列若要求在若要求在k-排列中元素排列中元素 出現(xiàn)次數(shù)構(gòu)成的集合為出現(xiàn)次數(shù)構(gòu)成的集合為 (1in)，則，則 k-排列數(shù)排列數(shù) 對應(yīng)數(shù)列對應(yīng)數(shù)列 的生成函數(shù)為的生成函數(shù)為 31證明證明根據(jù)和式的性質(zhì)，上式右端等于根據(jù)和式的性質(zhì)，上式右端等于由多項式系數(shù)的組合學(xué)意義知，由多項式系數(shù)的組合學(xué)意義知，正是元素正是元素 出現(xiàn)出現(xiàn) 次，元素次，元素 出現(xiàn)出現(xiàn) 次次，元素，元素 出現(xiàn)出現(xiàn) 次的次的 k-排列數(shù)。故按所有可能的排列數(shù)。故按所有可能的 求和，即得總的求和，即得總的k-排列數(shù)排列數(shù) 。有了定理定理有了定理定理 5.3.1，我們就可以方便的計算多重集的排列數(shù)，我們就可以方便的計算多重集的排列數(shù)32例例5.3.5 有有3個紅球，個紅球，2個黃球，個黃球，3個藍球，每次從中取出個藍球，每次從中取出4個排成一行，求排列方案數(shù)。個排成一行，求排列方案數(shù)。解解 設(shè)每次取出設(shè)每次取出k個球的排列數(shù)為個球的排列數(shù)為bk，數(shù)列，數(shù)列bk 的指數(shù)型的指數(shù)型生成函數(shù)為生成函數(shù)為Gebk，則有，則有而我們所求的即為而我們所求的即為 為為 的系數(shù)，則取出的系數(shù)，則取出4個球的排個球的排列方案有列方案有70種。種。33例例5.3.3 計算計算M=4r,5g,6b 中中r和和g均出現(xiàn)奇數(shù)次均出現(xiàn)奇數(shù)次 的的10-排列數(shù)。排列數(shù)。解解 顯然根據(jù)要求在所求的顯然根據(jù)要求在所求的10-排列中排列中r可能出現(xiàn)的次數(shù)為可能出現(xiàn)的次數(shù)為1或或3，g出現(xiàn)的次數(shù)為出現(xiàn)的次數(shù)為1或或3或或5。若設(shè)。若設(shè)M的的k-排列數(shù)為排列數(shù)為bk，數(shù)列，數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，則有，則有我們要求的我們要求的 是是 的系數(shù)，為的系數(shù)，為9660.34例例5.3.4 用紅、白、藍三種顏色給用紅、白、藍三種顏色給1行行k列棋盤涂色，并要列棋盤涂色，并要求紅色方格的個數(shù)是偶數(shù)且至少有一個方格為白色，求紅色方格的個數(shù)是偶數(shù)且至少有一個方格為白色，求涂色方案數(shù)求涂色方案數(shù)bk，其中，其中k為正整數(shù)。為正整數(shù)。解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，則有，則有因此，因此，355.4 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)n5.4.1 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)nCatalan數(shù)首先是由數(shù)首先是由Euler在精確計算對凸在精確計算對凸n邊形的不邊形的不同的對角三角形剖分的個數(shù)問題時得到的，它經(jīng)常同的對角三角形剖分的個數(shù)問題時得到的，它經(jīng)常出現(xiàn)在組合計數(shù)問題中。出現(xiàn)在組合計數(shù)問題中。n定義定義:一個凸一個凸n+1 邊形，通過不相交于邊形，通過不相交于n+1邊形內(nèi)部邊形內(nèi)部的對角線把的對角線把n+1邊形拆分成的三角形個數(shù)，記作邊形拆分成的三角形個數(shù)，記作hn稱為稱為Catalan數(shù)數(shù).365.4 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)n5.4.1 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)nCatalan數(shù)首先是由數(shù)首先是由Euler在精確計算對凸在精確計算對凸n邊形的不邊形的不同的對角三角形剖分的個數(shù)問題時得到的，它經(jīng)常同的對角三角形剖分的個數(shù)問題時得到的，它經(jīng)常出現(xiàn)在組合計數(shù)問題中。出現(xiàn)在組合計數(shù)問題中。n定義定義:一個凸一個凸n+1 邊形，通過不相交于邊形，通過不相交于n+1邊形內(nèi)部邊形內(nèi)部的對角線把的對角線把n+1邊形拆分成的三角形個數(shù)，記作邊形拆分成的三角形個數(shù)，記作hn稱為稱為Catalan數(shù)數(shù).37例如五邊形有如下五種拆分方案，所以例如五邊形有如下五種拆分方案，所以h4=538例5.4.1 在一個凸n+1邊形中，可以用(n-2)條不在內(nèi)部相交的對角線將其剖分成(n-1)個三角形，問有多少種不同的分法？解解 令令 表示將一個凸表示將一個凸(n+1)邊形剖為三角形的方法數(shù)，規(guī)定邊形剖為三角形的方法數(shù)，規(guī)定 。當(dāng)當(dāng)n=2時，時，(n+1)邊形就是三角形，不需剖分，故邊形就是三角形，不需剖分，故 當(dāng)當(dāng) 考慮一個凸考慮一個凸(n+1)邊形，它的頂點分別用邊形，它的頂點分別用 表示，如圖表示，如圖5.4.1所示。取邊所示。取邊 ，任取頂點，任取頂點 將將 分別與分別與 之間連線，得三角形之間連線，得三角形T，三角形，三角形T將凸將凸(n+1)邊形分成邊形分成 T，R 1和和R 2 三部分，其中，三部分，其中，R 1為為(k+1)邊形，邊形，R 2為為(n-k+1)邊形。因此，邊形。因此，R 1可以用可以用 種方法剖分，種方法剖分，R 2 可以用可以用 種方法剖分，所以種方法剖分，所以 這正是這正是Catalan數(shù)列的通項公式。數(shù)列的通項公式。3940TR2R1A1An+1Ak+2AkAk+1那么如何求那么如何求 ,本節(jié)用本節(jié)用 的生成函數(shù)的生成函數(shù) 來計算。來計算。解解 得得41 利用牛頓二項式定理，有利用牛頓二項式定理，有因為因為 ，開方應(yīng)該取負(fù)號，故舍去，開方應(yīng)該取負(fù)號，故舍去顯然一個凸顯然一個凸n+1邊形中有邊形中有 種不同的剖分方法。種不同的剖分方法。42 一般地，我們把一般地，我們把 稱為第稱為第k個個Catalan數(shù)，用數(shù)，用Cn表示，有表示，有 對于對于Ck-1和和Ck的形式我們并不陌生，例的形式我們并不陌生，例3.4.6的結(jié)論是從（的結(jié)論是從（0，0）點到）點到（n,n）點的除端點外不接觸直線）點的除端點外不接觸直線y=x的路徑數(shù)為的路徑數(shù)為 ,從從(0,0)點到（點到（n,n）點的除端點外不穿過直線）點的除端點外不穿過直線y=x 的路徑數(shù)為的路徑數(shù)為 如果用如果用Catalan數(shù)表示就是，從（數(shù)表示就是，從（0，0）點到（）點到（n,n）點的除端點外不）點的除端點外不接觸直線接觸直線y=x的路徑數(shù)為的路徑數(shù)為 ，從（，從（0，0）點到（）點到（n,n）點的除端）點的除端點外不穿過直線點外不穿過直線y=x的路徑數(shù)為的路徑數(shù)為 。43Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用1)不同構(gòu)的有不同構(gòu)的有n 條邊的種植樹條邊的種植樹(planted tree)的棵數(shù)是的棵數(shù)是Catalan 數(shù)數(shù)Cn 。2)有有n 片樹葉的有序三度根樹的個數(shù)是片樹葉的有序三度根樹的個數(shù)是Catalan 數(shù)數(shù)Cn-1。3)n 個頂點的不同二元樹的個數(shù)是個頂點的不同二元樹的個數(shù)是Catalan 數(shù)數(shù)Cn。二元樹的定義。二元樹的定義:空空集或一組有限個頂點集或一組有限個頂點,滿足滿足:有一個特定的點稱作有一個特定的點稱作“根點根點”;去去掉這個根點后掉這個根點后,余下的頂點組成兩支子二元樹余下的頂點組成兩支子二元樹:左子樹與右子樹。左子樹與右子樹。4)從點從點(0,0)到點到點(n+1,n+1),除端點外與對角線不相交的除端點外與對角線不相交的(在對角線在對角線一側(cè)的一側(cè)的)非降路徑數(shù)是非降路徑數(shù)是Catalan 數(shù)數(shù)Cn。5)2n 個均勻分布在一個圓周上個均勻分布在一個圓周上,用用n 條不相交的弦將這條不相交的弦將這2n 個點配成個點配成n 對對,則不同的配對方式數(shù)是則不同的配對方式數(shù)是Catalan 數(shù)數(shù)Cn。6)n 個個1 和和n 個個0 組成一組成一2n 位的二進制數(shù)位的二進制數(shù),要求從左到右掃描要求從左到右掃描,1 的累計的累計數(shù)不小于數(shù)不小于0 的累計數(shù)的累計數(shù),滿足這一條件的滿足這一條件的2n 位的二進制數(shù)的個數(shù)是位的二進制數(shù)的個數(shù)是Cn44Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用7)在兩個候選人在兩個候選人A 和和B 的投票選舉中的投票選舉中,共有共有2n 個人投票個人投票,最終結(jié)果是支持最終結(jié)果是支持A 和和B 票數(shù)都是票數(shù)都是n 票。在開票過程中始終使票。在開票過程中始終使A 的票數(shù)不少于的票數(shù)不少于B 的票數(shù)的投票的票數(shù)的投票方案數(shù)是方案數(shù)是Catalan 數(shù)數(shù)Cn。8)有有2n 個人在劇院票房門前準(zhǔn)備買票入場。每張票價是個人在劇院票房門前準(zhǔn)備買票入場。每張票價是50 美分美分,而且此時而且此時票房售票員沒有零錢。這票房售票員沒有零錢。這2n 個人恰好有個人恰好有n 個人有個人有50 美分的錢美分的錢,其余其余n 個人個人只有只有1 美元的錢。如果在任何時候售票員都能找開零錢的美元的錢。如果在任何時候售票員都能找開零錢的2n 個人的排列個人的排列方法數(shù)是方法數(shù)是Catalan 數(shù)數(shù)Cn。9)有有2n 個高低不同的人個高低不同的人,排成兩行排成兩行,使得第一排使得第一排n 個人都比第二排個人都比第二排n 個人高的個人高的排列方法數(shù)是排列方法數(shù)是Catalan 數(shù)數(shù)Cn。10)設(shè)設(shè)a1,a2,an 與與b1,b2,bn 是兩個完全不同的序列是兩個完全不同的序列,則把這兩個序列融合則把這兩個序列融合在一起組成一個新的序列在一起組成一個新的序列，使得后一個序列與前一個序列相對應(yīng)的數(shù)始使得后一個序列與前一個序列相對應(yīng)的數(shù)始終排在前一個序列數(shù)后面的排列的個數(shù)是終排在前一個序列數(shù)后面的排列的個數(shù)是Catalan 數(shù)數(shù)。45Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用11)有有2n 個人圍著圓桌就坐個人圍著圓桌就坐,手臂不相交的握手的方法數(shù)是手臂不相交的握手的方法數(shù)是Catalan 數(shù)數(shù)Cn12)n 個數(shù)相乘個數(shù)相乘,不改變它們的位置不改變它們的位置,只用括號表示不同的相乘順序只用括號表示不同的相乘順序,則構(gòu)成不則構(gòu)成不同的乘積的方法數(shù)同的乘積的方法數(shù)Catalan 數(shù)數(shù)Cn-1。例如：例如：n=4，464748