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

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT n n 多重集概念多重集概念n n 多重集的排列多重集的排列n n多重集多重集 r-排列排列n n全排列全排列n n多重集的組合多重集的組合n n多重集多重集r-組合組合3.3 多重集多重集n n將將r個相同的個相同的球放入球放入n個不同的盒子個不同的盒子中中，則，則不同的放法不同的放法為多重集的為多重集的r組合組合數(shù)數(shù) n n思考思考：結(jié)論成立的條件？n n 若若M中每個元素的重復(fù)度大于等于中每個元素的重復(fù)度大于等于r，則，則結(jié)論仍然成立。結(jié)論仍然成立。n n思考思考：分配問題模型（小球裝盒子）分配問題模型（小球裝盒子）？例例3.3.5 從從4個個a，4個個b，4個個c，4個個d中無中無序選取序選取10個字母，如果每個字母至少包含個字母，如果每個字母至少包含兩個，則有多少種取法兩個，則有多少種取法解 這個問題實際上是求多重集的10-組合數(shù)，且10-組合中每個字母至少包含兩個。顯然，這個問題等價于方程x1+x2+x3+x4=10，其滿足條件x12，x22，x32，x42的整數(shù)解個數(shù)。進(jìn)行代換，令y1=x1-2，y2=x2-2，y3=x3-2，y4=x4-2，則y10，y20，y30，y40，且y1+y2+y3+y4=2。根據(jù)定理3.3.3，其非負(fù)整數(shù)解數(shù)為 ，因此共有10種取法。例例3.3.6 求集合求集合S=1,2,n的的r-組合數(shù)，其組合數(shù)，其中要求中要求r-組合中任意兩個元素在組合中任意兩個元素在S中都不是中都不是相鄰的。相鄰的。如當(dāng)如當(dāng)n=5，r=3時，時，S=1,2,3,4,5,6，1,3,5是滿足條件的是滿足條件的3-組合，而組合，而1,2,6是不滿足條是不滿足條件的件的3-組合，因為組合，因為1,2在在S中是相鄰的。中是相鄰的。分析分析1（1）問題求問題求普通集合的普通集合的r-組合數(shù)組合數(shù)（2）要求要求對于任一對于任一 r-組合相鄰元素在組合相鄰元素在S中不相鄰中不相鄰（3）問題表示問題表示：任一：任一 r-組合組合 ，不妨，不妨 設(shè)為設(shè)為 ，那么就是要求，那么就是要求 （4）關(guān)心的是選取的相鄰元素之間的關(guān)系）關(guān)心的是選取的相鄰元素之間的關(guān)系解解 方法方法1 考慮考慮S的任意一個的任意一個r-組合組合 ，不，不妨設(shè)妨設(shè) 我們把我們把1,2,n這這n個數(shù)按從小到大的順序排成一個序列，其個數(shù)按從小到大的順序排成一個序列，其中我們只把標(biāo)識出來，其余數(shù)字用中我們只把標(biāo)識出來，其余數(shù)字用“”表示。表示。在序列中每個ji后面用以豎線“|”標(biāo)記，則設(shè)第1個豎線前面的數(shù)字個數(shù)為x1，第1個豎線與第2個豎線間的數(shù)字個數(shù)為x2，第r個豎線前面的數(shù)字個數(shù)為xr+1。根據(jù)題意，因為 中任意兩個數(shù)都彼此不相鄰，所以滿足：x11，x22，xr2，xr+10，因為一共有n個數(shù)字，所以x1+x2+x3+xr+xr+1=n。這這 樣樣 原原 問問 題題 要要 求求 的的r-組組 合合 數(shù)數(shù) 就就 等等 價價 于于 方方 程程x1+x2+xr+xr+1=n滿滿足足條條件件x11，x22，xr2，xr+10的整數(shù)解個數(shù)。的整數(shù)解個數(shù)。進(jìn)行代換，令進(jìn)行代換，令y1=x1-1，y2=x2-2，yr=xr-2，yr+1=xr+1，則，則y10，y20，yr0，yr+10，且，且y1+y2+yr+yr+1=n-1-2(r-1)。根據(jù)定理根據(jù)定理3.3.3的證明：這個方程的非負(fù)整數(shù)解個的證明：這個方程的非負(fù)整數(shù)解個數(shù)是：數(shù)是：因此滿足條件的因此滿足條件的r-組合數(shù)為組合數(shù)為分析分析2（1）問題表示：問題表示：任一任一 r-組合組合 ，不妨，不妨 設(shè)為設(shè)為 ，那么就是要求，那么就是要求 （2）如果對）如果對 jr 通過某種變換，消除相鄰元素之間通過某種變換，消除相鄰元素之間 的約束條件限制，那么就可以利用普通集合組合的約束條件限制，那么就可以利用普通集合組合 公式直接求解。公式直接求解。（3）回憶多重集組合公式放縮法是把重復(fù)元素伸拉變）回憶多重集組合公式放縮法是把重復(fù)元素伸拉變 換到普通集合，那么本題是否可以通過壓縮變換換到普通集合，那么本題是否可以通過壓縮變換 到普通集合到普通集合解解 方法方法2考慮考慮S的任意一個的任意一個r-組合組合 ，不妨設(shè)，不妨設(shè) ，令，令 ，即，即則則且當(dāng)且當(dāng)顯然顯然 與滿足題設(shè)條件的與滿足題設(shè)條件的 一一對應(yīng)，而一一對應(yīng)，而 是是(n-r+1)元集合的元集合的r-組合，其數(shù)量為組合，其數(shù)量為 ，即為所求。，即為所求。3.4 二項式定理二項式定理 3.4.1 和式和式3.4.2 二項式定理二項式定理3.4.3 二項式定理的推廣二項式定理的推廣3.4.4 組合恒等式組合恒等式3.4.5 非降路徑問題非降路徑問題n n在組合數(shù)學(xué)中求和是最基本的運(yùn)算在組合數(shù)學(xué)中求和是最基本的運(yùn)算n n和式表示法的引入給求和問題的表示和運(yùn)算都和式表示法的引入給求和問題的表示和運(yùn)算都帶來了極大的便捷。帶來了極大的便捷。n n例如，我們求例如，我們求1到到n的正整數(shù)的和原來寫成的正整數(shù)的和原來寫成1+2+n，有了，有了 表示法，就可以表示成表示法，就可以表示成3.4.1 和式和式 一般地，表示法的和式為一般地，表示法的和式為 ，表示，表示 讀作讀作“k從從1到到n對對ak求和求和”。這種表示方法可以推廣，即把難以表達(dá)或者復(fù)雜的這種表示方法可以推廣，即把難以表達(dá)或者復(fù)雜的k的取值范的取值范圍寫到下方。圍寫到下方。和式具有如下的性質(zhì)和式具有如下的性質(zhì)（1），其中c為與k無關(guān)的常量；（2）（3）例例3.4.1 求和求和 解解 令因為0kn，所以0n-kn，根據(jù)性質(zhì)3，根據(jù)性質(zhì)2，將S的兩個表達(dá)式相加，有：根據(jù)性質(zhì)1因此例例3.4.2 對于任意正整數(shù)對于任意正整數(shù)n，給出，給出 關(guān)于關(guān)于n的計算公式。的計算公式。方法方法1 我們觀察圖我們觀察圖3.3.1中兩個方陣，它們中兩個方陣，它們是完全相同的，我們采用不同的方式求和。是完全相同的，我們采用不同的方式求和。12345 n2345 n345 n45 n5 n n12345 n2345 n345 n45 n5 n nn n對于圖(a)，一列一列看，第1列1個1，第2列2個2，第n列n個n，如果按列求和，第1列為12，第2列為22，第n列n2，則所有數(shù)字的和恰好是n n對于圖(b)，按行求和，第1行為 ，第2行為 ，第n行為 ，則所有數(shù)字的和恰好是n n因為圖(a)和圖(b)中的數(shù)字完全相同，所以n n首先設(shè) n n方法方法2 首先設(shè) 推出 因此 關(guān)于二項式關(guān)于二項式n n程序的構(gòu)成：順序，循環(huán)，程序的構(gòu)成：順序，循環(huán)，n n算法分析的度量算法分析的度量n n比較比較n n加法與乘法的基本組合形式加法與乘法的基本組合形式3.4.2 二項式定理二項式定理對二項式的研究對二項式的研究項數(shù)項數(shù)系數(shù)系數(shù)求和結(jié)果求和結(jié)果n n二項式定理的幾種特殊形式是我們已往熟悉的二項式定理的幾種特殊形式是我們已往熟悉的二項式定理的幾種特殊形式是我們已往熟悉的二項式定理的幾種特殊形式是我們已往熟悉的公式：公式：公式：公式：（1 1）（2 2）（3 3）3.4.2 二項式定理二項式定理定理定理3.4.1 (二項式定理二項式定理)設(shè)n是正整數(shù),則對任意的x,y有：證明證明 用組合分析的方法證明。用組合分析的方法證明。等式左邊是等式左邊是n個（個（x+y）因子相乘，即）因子相乘，即這些因子展開到?jīng)]有括號為止。在展開時，每個因這些因子展開到?jīng)]有括號為止。在展開時，每個因子中均可貢獻(xiàn)一個子中均可貢獻(xiàn)一個x或一個或一個y。由乘法原理，共有。由乘法原理，共有2n項，這些項都可以寫成項，這些項都可以寫成 的形式?？傻男问健？梢栽谝栽趎個個x+y因子中選出因子中選出k個，從這個，從這k個因子中取個因子中取x，而在另外的而在另外的n-k個因子中取個因子中取y，如此得到項，所以的，如此得到項，所以的系數(shù)等于系數(shù)等于n個因子的個因子的k-組合數(shù)，即組合數(shù)，即 。因此。因此基本性質(zhì)基本性質(zhì)n n（1）對稱關(guān)系 n n（2）遞推關(guān)系 n n（3）單峰性n nn為偶數(shù)時，有n nn為奇數(shù)時，有 性質(zhì)（性質(zhì)（2）的證明）的證明 利用的組合意義來證。利用的組合意義來證。n元集合元集合 的的k元子集可以分成元子集可以分成兩類：兩類：第一類第一類k元子集含元子集含a1;第二類第二類k元子元子集不含集不含a1第一類第一類k元子集中的任一個去掉元子集中的任一個去掉a1后，就后，就是是S-a1的的k-1元子集；反過來，任給一個元子集；反過來，任給一個的的k-1元子集，添上元子集，添上a1后就是后就是S的的k元子集，元子集，故二者這間有一一對應(yīng)關(guān)系故二者這間有一一對應(yīng)關(guān)系.因而，第一類因而，第一類k元子集共有元子集共有 個個.第二類第二類k元子集就是元子集就是S-a1的的k元子集，共有元子集，共有 個個.所以所以性質(zhì)（性質(zhì)（3）的證明）的證明 證明：證明：證明：證明：設(shè)設(shè)11k k n n，考慮，考慮 與與 之比：之比：楊輝三角形體現(xiàn)了數(shù)學(xué)之美楊輝三角形體現(xiàn)了數(shù)學(xué)之美 n=01n=111n=2121n=31331n=414641n=515101051n=61615201561k=0k=1k=2k=3k=4k=5k=6對稱性、遞推性、單峰性對稱性、遞推性、單峰性數(shù)學(xué)之美數(shù)學(xué)之美n n歷史上曾經(jīng)獨(dú)立繪制過這種圖表的數(shù)學(xué)家歷史上曾經(jīng)獨(dú)立繪制過這種圖表的數(shù)學(xué)家賈憲 中國北宋 11世紀(jì) 釋鎖算術(shù) 楊輝 中國南宋 1261詳解九章算法記載之功 朱世杰 中國元代 1299 四元玉鑒級數(shù)求和公式 阿爾卡西 阿拉伯 1427算術(shù)的鑰匙 阿皮亞納斯 德國 1527 施蒂費(fèi)爾 德國 1544綜合算術(shù)二項式展開式系數(shù) 薛貝爾 法國 1545 B帕斯卡 法國 1654論算術(shù)三角形推論推論3.4.1 設(shè)設(shè)n是正整數(shù)，對一切是正整數(shù)，對一切x有有推論推論3.4.2 對任何正整數(shù)對任何正整數(shù)n有有推論推論3.4.3 對任何正整數(shù)對任何正整數(shù)n有有推論推論3.4.3證明證明 在二項式定理中令x=-1,y=1,得 將上式整理一下即得原等式成立。3.4.3 二項式定理的推廣二項式定理的推廣1n n上面得到的結(jié)果只適用于指數(shù)為自然數(shù)的情況，上面得到的結(jié)果只適用于指數(shù)為自然數(shù)的情況，能否把二項式定理推廣到非自然數(shù)的情況呢能否把二項式定理推廣到非自然數(shù)的情況呢?n n16651665年年，牛頓對此進(jìn)行了研究。，牛頓對此進(jìn)行了研究。n n他考慮了已知的無窮遞縮等比數(shù)列的求和公式：他考慮了已知的無窮遞縮等比數(shù)列的求和公式：n n 為了便于比較，我們把二項式定理改寫為：為了便于比較，我們把二項式定理改寫為：n n經(jīng)過仔細(xì)比較，不難發(fā)現(xiàn)上式中取經(jīng)過仔細(xì)比較，不難發(fā)現(xiàn)上式中取經(jīng)過仔細(xì)比較，不難發(fā)現(xiàn)上式中取經(jīng)過仔細(xì)比較，不難發(fā)現(xiàn)上式中取n=-1n=-1時，自時，自時，自時，自動成為無窮遞縮等比數(shù)列求和公式。動成為無窮遞縮等比數(shù)列求和公式。動成為無窮遞縮等比數(shù)列求和公式。動成為無窮遞縮等比數(shù)列求和公式。n n這說明二項式定理的新形式在這說明二項式定理的新形式在這說明二項式定理的新形式在這說明二項式定理的新形式在n=-1n=-1時也成立。時也成立。時也成立。時也成立。n n這個結(jié)果有沒有一般性？牛頓大膽的猜想：二這個結(jié)果有沒有一般性？牛頓大膽的猜想：二這個結(jié)果有沒有一般性？牛頓大膽的猜想：二這個結(jié)果有沒有一般性？牛頓大膽的猜想：二項式定理的新形式對于任意有理指數(shù)都是正確項式定理的新形式對于任意有理指數(shù)都是正確項式定理的新形式對于任意有理指數(shù)都是正確項式定理的新形式對于任意有理指數(shù)都是正確的，即：的，即：的，即：的，即：這個猜想是否正確？牛頓對此進(jìn)行了驗證。當(dāng)指數(shù)為這個猜想是否正確？牛頓對此進(jìn)行了驗證。當(dāng)指數(shù)為1/2時，時，驗證的結(jié)果與猜想一致。牛頓還對指數(shù)為驗證的結(jié)果與猜想一致。牛頓還對指數(shù)為驗證的結(jié)果與猜想一致。牛頓還對指數(shù)為驗證的結(jié)果與猜想一致。牛頓還對指數(shù)為1/31/3、2/32/3等情況進(jìn)等情況進(jìn)等情況進(jìn)等情況進(jìn)行了驗證，結(jié)果也與猜想一致。行了驗證，結(jié)果也與猜想一致。行了驗證，結(jié)果也與猜想一致。行了驗證，結(jié)果也與猜想一致。然而，僅僅憑著然而，僅僅憑著有限的驗證有限的驗證能夠保證能夠保證結(jié)論的普遍正確性結(jié)論的普遍正確性嗎嗎？還要不要嚴(yán)格的證明？還要不要嚴(yán)格的證明？牛頓認(rèn)為這已經(jīng)足夠了，不需要進(jìn)一步證明，他也沒有給牛頓認(rèn)為這已經(jīng)足夠了，不需要進(jìn)一步證明，他也沒有給出證明。出證明。1811年，年，高斯高斯對此進(jìn)行了嚴(yán)格的證明，結(jié)果表明牛頓的猜對此進(jìn)行了嚴(yán)格的證明，結(jié)果表明牛頓的猜想是正確的。想是正確的。二項式定理在二項式定理在組合理論、開高次方、高階等差數(shù)列組合理論、開高次方、高階等差數(shù)列求和求和，以及以及差分法差分法中有廣泛的應(yīng)用。中有廣泛的應(yīng)用?，F(xiàn)在，人們已經(jīng)把二項式定理推廣到了指數(shù)為任意的實數(shù)，現(xiàn)在，人們已經(jīng)把二項式定理推廣到了指數(shù)為任意的實數(shù)，甚至復(fù)數(shù)時的情況。甚至復(fù)數(shù)時的情況。定理定理3.4.2 (牛頓二項式定理牛頓二項式定理)設(shè)設(shè)是一個實數(shù)，則對一切是一個實數(shù)，則對一切x和和y，滿足，滿足 有有 其中其中3.4.3 二項式定理的推廣二項式定理的推廣1 當(dāng)當(dāng)=-n(負(fù)整數(shù)負(fù)整數(shù))時，有時，有 當(dāng)當(dāng)=(分?jǐn)?shù)分?jǐn)?shù))時，有時，有牛頓二項式定理設(shè)是一個實數(shù)，則對一切x和y，滿足 ,有 3.4.3 二項式定理的推廣二項式定理的推廣2n n二項式定理給出了兩項和的二項式定理給出了兩項和的二項式定理給出了兩項和的二項式定理給出了兩項和的n n次冪的展開公式，次冪的展開公式，次冪的展開公式，次冪的展開公式，有時我們也需要計算三項或多項和的有時我們也需要計算三項或多項和的有時我們也需要計算三項或多項和的有時我們也需要計算三項或多項和的n n次冪，這次冪，這次冪，這次冪，這時該怎么辦？時該怎么辦？時該怎么辦？時該怎么辦？n n最容易想到的辦法是多次應(yīng)用二項式定理，即最容易想到的辦法是多次應(yīng)用二項式定理，即最容易想到的辦法是多次應(yīng)用二項式定理，即最容易想到的辦法是多次應(yīng)用二項式定理，即先把后幾項合并成一項，應(yīng)用二項式定理，再先把后幾項合并成一項，應(yīng)用二項式定理，再先把后幾項合并成一項，應(yīng)用二項式定理，再先把后幾項合并成一項，應(yīng)用二項式定理，再對式子中出現(xiàn)的后幾項的冪進(jìn)行類似處理。對式子中出現(xiàn)的后幾項的冪進(jìn)行類似處理。對式子中出現(xiàn)的后幾項的冪進(jìn)行類似處理。對式子中出現(xiàn)的后幾項的冪進(jìn)行類似處理。v 定理定理3.4.3 (多項式定理多項式定理)設(shè)設(shè)n是正整數(shù)，則是正整數(shù)，則其中其中稱為多項式系數(shù)稱為多項式系數(shù)，并且是對所有滿足，并且是對所有滿足n1+n2+nt=n 的非負(fù)整數(shù)解的非負(fù)整數(shù)解 n1,n2,nt求和。求和。證明證明 (1)先將先將(x1+xt)n寫成寫成n個個(x1+xt)因子的乘積：因子的乘積：將其展開，直到?jīng)]有括號為止。因為每個將其展開，直到?jīng)]有括號為止。因為每個因子中都可取因子中都可取x1,x2,xt中的任一個，所以中的任一個，所以展開式共有展開式共有tn項，且每項都可以寫成項，且每項都可以寫成 的形式的形式.要得到這一項，我們應(yīng)該要得到這一項，我們應(yīng)該在在n個因子中的個因子中的n1個里面取個里面取x1，有，有 種取法；種取法；在剩下的在剩下的n-n1個因子中的個因子中的n2個里面取個里面取x2，有，有 種取法；種取法；最后，在最后，在個因子里面取個因子里面取xt，有，有種取法種取法.由乘法原理知，由乘法原理知，前的系數(shù)前的系數(shù)為為例例3.4.3 展開的系數(shù)為 推論推論3.4.4 (x1+xt)n的展開式在合并同類的展開式在合并同類項以后不同的數(shù)目是項以后不同的數(shù)目是 證明證明(x1+xt)n的展開式中任何一項對應(yīng)的展開式中任何一項對應(yīng)于方程于方程 n1+n2+nt=n的一組非負(fù)整數(shù)解，的一組非負(fù)整數(shù)解，所以合并同類項后不同的項數(shù)等于這個方所以合并同類項后不同的項數(shù)等于這個方程的非負(fù)整數(shù)解的個數(shù)程的非負(fù)整數(shù)解的個數(shù) 推論推論3.4.5其中求和是對方程其中求和是對方程n1+n2+nt=n 的一切的一切非負(fù)整數(shù)解來求。非負(fù)整數(shù)解來求。證明證明:在多項式定理中令在多項式定理中令x1=x2=xt=1即可即可.說明：推導(dǎo)例說明：推導(dǎo)例3.3.3v 在多項式定理中如果取在多項式定理中如果取t2，就得到普，就得到普通的二項式定理通的二項式定理.v 多項式系數(shù)多項式系數(shù) 組合意義如下：組合意義如下：(1)是多項式是多項式(x1+xt)n中中項的系數(shù)。項的系數(shù)。(2)是多重集是多重集S=n1.a1,n2.a2,nt.at的的n排列數(shù)排列數(shù)(3)如果我們把如果我們把n個不同的球放到個不同的球放到t個不同個不同的盒子里的盒子里,并且使得第一個盒子里有并且使得第一個盒子里有n1個個球，第二個盒子里有球，第二個盒子里有n2個球個球,第第t個盒子個盒子里有里有nt個球，那么放球的方案數(shù)是個球，那么放球的方案數(shù)是n n