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

《組合數(shù)學(xué)》課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 3.2.2 集合排列和組合的生成集合排列和組合的生成l 排列的生成方法排列的生成方法l(a)鄰位互換法鄰位互換法l(b)字典序法字典序法l 組合的生成方法組合的生成方法l (a)生成集合生成集合I=1,2,n的所有組合的所有組合 字典序字典序 格雷碼格雷碼l (b)生成集合生成集合I=1,2,n的所有的所有r組合組合對(duì)稱性，遞推性，單峰性對(duì)稱性，遞推性，單峰性二項(xiàng)式定理二項(xiàng)式定理設(shè)n是正整數(shù),則對(duì)任意的x,y有：牛頓二項(xiàng)式定理牛頓二項(xiàng)式定理設(shè)設(shè)是一個(gè)實(shí)數(shù)，則對(duì)一切是一個(gè)實(shí)數(shù)，則對(duì)一切x和和y，滿足，滿足 ,有有 多項(xiàng)式定理多項(xiàng)式定理設(shè)設(shè)n是正整數(shù)，則是正整數(shù)，則其中其中稱為多項(xiàng)式系數(shù)稱為多項(xiàng)式系數(shù)，并且是對(duì)所有滿足，并且是對(duì)所有滿足n1+n2+nt=n 的非負(fù)整數(shù)解的非負(fù)整數(shù)解 n1,n2,nt求求和。和。證明組合恒等式的證明組合恒等式的方法方法：v 代數(shù)方法：代數(shù)方法：通過(guò)代入組合數(shù)的值或已知的組合恒通過(guò)代入組合數(shù)的值或已知的組合恒等式進(jìn)行計(jì)算或化簡(jiǎn)，使等式兩邊相等等式進(jìn)行計(jì)算或化簡(jiǎn)，使等式兩邊相等v 二項(xiàng)式定理：二項(xiàng)式定理：v比較展開式中比較展開式中xr的系數(shù)，的系數(shù)，v在展開式中令在展開式中令x和和y為某個(gè)特定的值為某個(gè)特定的值v利用冪級(jí)數(shù)的利用冪級(jí)數(shù)的微分或積分微分或積分等數(shù)學(xué)分析的方法等數(shù)學(xué)分析的方法v 數(shù)學(xué)歸納法數(shù)學(xué)歸納法v 組合分析方法組合分析方法：說(shuō)明等式兩邊都是對(duì)同一組合問(wèn)說(shuō)明等式兩邊都是對(duì)同一組合問(wèn)題的計(jì)數(shù)題的計(jì)數(shù) 基本模型基本模型 非降路徑模型應(yīng)用非降路徑模型應(yīng)用l組合恒等式證明組合恒等式證明 限定條件下的非降路徑數(shù)限定條件下的非降路徑數(shù)l應(yīng)用實(shí)例應(yīng)用實(shí)例3.4.5 非降路徑問(wèn)題非降路徑問(wèn)題基本模型描述基本模型描述從從(0,0)點(diǎn)開始點(diǎn)開始,水平向右走一水平向右走一步為步為x,垂直向垂直向上走一步為上走一步為y，則走到則走到(m,n)點(diǎn)點(diǎn)水平向右要走水平向右要走m步步,垂直向上垂直向上要走要走n步步(0,0)(m,n)yx從從(0，0)點(diǎn)到點(diǎn)到(5，6)點(diǎn)的一條非降路徑，規(guī)定水平向點(diǎn)的一條非降路徑，規(guī)定水平向右走一個(gè)單元格用右走一個(gè)單元格用x表示，垂直向上走一個(gè)單元格用表示，垂直向上走一個(gè)單元格用y表表示，則此路經(jīng)對(duì)應(yīng)于排列示，則此路經(jīng)對(duì)應(yīng)于排列xyxxyyyxxyy。反過(guò)來(lái)，按照。反過(guò)來(lái)，按照以上規(guī)則，給定排列以上規(guī)則，給定排列xyxxyyyxxyy，就對(duì)應(yīng)了如圖所示，就對(duì)應(yīng)了如圖所示的非降路徑。的非降路徑。(0,0)(5,6)yx 一般地，一條一般地，一條從從(0,0)點(diǎn)到點(diǎn)到(m,n)點(diǎn)的非降路徑點(diǎn)的非降路徑就就是是多重集多重集mx，ny的一個(gè)排列的一個(gè)排列。反之，反之，給給定多重集定多重集mx，ny的一個(gè)排列就唯的一個(gè)排列就唯一地確定了一條從一地確定了一條從(0,0)點(diǎn)到點(diǎn)到(m,n)點(diǎn)的非降路徑。點(diǎn)的非降路徑。(0,0)(m,n)yx(p,q)x(0,0)y(r,s)補(bǔ)充補(bǔ)充1 從從(p,q)點(diǎn)到點(diǎn)到(r,s)點(diǎn)，這里點(diǎn)，這里pr,qn.(0,0)yx(m,n)(-1,1)y=x+1解解 根據(jù)題意，要滿足總是能找出零錢，就意味著對(duì)于隊(duì)列中每根據(jù)題意，要滿足總是能找出零錢，就意味著對(duì)于隊(duì)列中每個(gè)歌迷而言，她前面的人個(gè)歌迷而言，她前面的人(包括她在內(nèi)包括她在內(nèi))中持中持50元的人不少于持元的人不少于持100元的人。顯然是求從元的人。顯然是求從(0，0)到到(m,n)不穿過(guò)直線不穿過(guò)直線y=x且在且在y=x下下方的非降路徑數(shù)，方的非降路徑數(shù)，歷年試題填空一場(chǎng)演唱會(huì)門票為50元一張，排隊(duì)買票的歌迷中有n個(gè)人手持50元紙幣，n個(gè)人手持100元紙幣。假定每個(gè)人只能購(gòu)票1張，售票處沒(méi)有準(zhǔn)備零錢，那么售票處不會(huì)找不出錢的概率為（）。3.5 集合的分劃與集合的分劃與Stirling數(shù)數(shù)3.5.1 集合的分劃與第二類集合的分劃與第二類Stirling數(shù)數(shù) 定義定義3.5.1 集合S的子集族稱為n元集S的一個(gè)k-分劃，如果這個(gè)子集族滿足1.每個(gè)Si非空；2.當(dāng)ij時(shí)，3.其中每個(gè)其中每個(gè)Si稱稱為為一個(gè)分劃一個(gè)分劃塊塊，也把，也把這這個(gè)個(gè)k-分劃分劃記為記為：例例3.5.1 集合A=1,2,3,4有7個(gè)2-分劃，它們是 定義定義3.5.2 一個(gè)n元集合的全部k-分劃的個(gè)數(shù)記為第二類Stirling數(shù)，表示為或 S2(n,k)(1)(2)定理定理3.5.1 第二類第二類Stirling數(shù)數(shù) 滿足如下遞推關(guān)系滿足如下遞推關(guān)系 證明證明 等式左邊等式左邊 是集合是集合的的k-分劃的個(gè)數(shù)，這些分劃的個(gè)數(shù)，這些k-分劃可以分成兩類分劃可以分成兩類:第第1類：類：an是是A的的k-分劃中的一塊，這時(shí)，分劃中的一塊，這時(shí)，只需對(duì)集合只需對(duì)集合A-an進(jìn)行進(jìn)行(k1)-分劃，再加上分劃，再加上an這一塊，就構(gòu)成了這一塊，就構(gòu)成了A的的k-分劃，因此，這分劃，因此，這類分劃有類分劃有 個(gè)；個(gè)；第第2類：類：an不是不是A的的k-分劃中單獨(dú)的一塊，分劃中單獨(dú)的一塊，此時(shí)，先構(gòu)造此時(shí)，先構(gòu)造A-an的的k-分劃，共有分劃，共有 種方法。種方法。然后，對(duì)于然后，對(duì)于A-an的每個(gè)的每個(gè)k-分劃，將分劃，將an加加到該到該k-分劃的分劃的k個(gè)塊中的某一塊，從而構(gòu)成個(gè)塊中的某一塊，從而構(gòu)成A的的k-分劃分劃 因此由乘法原理，集合因此由乘法原理，集合A的此類的此類k-分劃共分劃共有有 個(gè)個(gè)綜上以上，由加法原理綜上以上，由加法原理定理定理3.5.2 第二類第二類Stirling數(shù)滿足下列性質(zhì)：數(shù)滿足下列性質(zhì)：性質(zhì)性質(zhì)(1)性質(zhì)性質(zhì)(2)(1)組合意義組合意義是n元集合 的2-分劃數(shù)，先取出a1,則對(duì)于 a2,a3,an，每個(gè)元素都有兩種選擇，即與a1在同一塊里或者ai與a1不在同一塊里，不同的選擇就構(gòu)成了集合A的不同的2-分劃，但這里要排除掉a2,a3,an，都與a1在同一塊中的情形(此時(shí)不構(gòu)成集合A的2-分劃 由此可知，n元集合A的2-分劃數(shù)為2n-1-1 證明證明 (2)是是n元集合的元集合的(n-1)-分劃，由于分劃中分劃，由于分劃中各各塊塊是非空的，所以每個(gè)是非空的，所以每個(gè)(n-1)-分劃中必有分劃中必有一一塊為塊為兩個(gè)元素，其余各兩個(gè)元素，其余各塊塊都恰有一個(gè)元都恰有一個(gè)元素，所以，素，所以，對(duì)對(duì)于于n元集合的每個(gè)元集合的每個(gè)(n-1)-分劃，分劃，只要確定了有兩個(gè)元素的那一只要確定了有兩個(gè)元素的那一塊塊，整個(gè)，整個(gè)(n-1)-分劃就確定了分劃就確定了 因此，因此，就是在就是在n元集中元集中選選取取2個(gè)元素的個(gè)元素的 方法數(shù)方法數(shù) 組合意義組合意義3.5.2 第一類第一類Stirling數(shù)數(shù) 第一類Stirling數(shù)也與集合的分劃相關(guān) 集合有7個(gè)2-分劃，但我們要求將每個(gè)分劃塊做成圓排列(或者輪換)，則共可構(gòu)成11個(gè)不同的圓排列組定義定義3.5.3 一個(gè)一個(gè)n元集合的全部元集合的全部k-分劃所分劃所形成的不同的圓排列組的個(gè)數(shù)，即形成的不同的圓排列組的個(gè)數(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單獨(dú)構(gòu)成一個(gè)圓排列，只需對(duì)集合A-an進(jìn)行(k-1)-圓排列分劃，再加上an這個(gè)圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個(gè)。第2類：an不是A的k-圓排列分劃中的單獨(dú)一個(gè)圓排列，此時(shí)，先構(gòu)造A-an的k-圓排列分劃，共有 種方法，然后對(duì)于A-an的每個(gè)k-圓排列分劃，將an插入該k-圓排列分劃的k個(gè)圓排列中的某一個(gè)圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個(gè)。綜上以上分析，由加法原理，有 第一類第一類Stirling數(shù)的三角形數(shù)的三角形