二、有限多重集的r-組合數(shù)設(shè)多重集s={n1a1,n2a2,…,nk-資料下載頁
2024-10-12 12:38本頁面
【導(dǎo)讀】當(dāng)r<n，且存在某個ni<r時，S的r-組合數(shù)沒有。例：求S={3·a,4·b,5·c}的10-組合數(shù)。P3表示D的10-組合中多于5個c這一性質(zhì)，即A1是D的10-組合中a至少出現(xiàn)4個的組合全體。對A2的任一10-組合中拿走5個b，就是D的5-組合。所以|A3|就是D的4-組合數(shù)，即。所以|A1∩A2|就是D的1-組合數(shù)，即?，F(xiàn)6個的組合全體。所以|A2∩A3|=|A1∩A2∩A3|=0。4下x1+x2+x3'=4的整數(shù)解個。類似可以知道|A1∩A3|=|A2∩A3|=|A1∩A2∩A3|=0?，F(xiàn)在考慮這樣的問題：在書架上有5本書，把。一本在原來位置上，有多少種放法？這就是錯位排列問題。定義：設(shè)集合S={1,2,…n,則稱該排列是S. S的所有錯位排列數(shù)記為Dn。當(dāng)n=3時，1,2,3錯位，可排成2,3,1，或3,1,2，
【正文】 r}的生成函數(shù)是 f(x)=(1+x+x2)(1+x2+(x2)2+(x2)3)(1+x5+(x5)2)) ? =1+x+2x2+x3+2x4+2x5+3x6+3x7+2x8+2x9+2x10+3x11+3x12+2x13+ 2x14+x15+2x16+x17+x18。 ? 這表明凡是質(zhì)量不超過 18 克的物體都能用給定的砝碼稱出 。 ? 其中質(zhì)量為 1,3,15,17,18克的只有一種稱法 ， ? 質(zhì)量為 2,4,5,8,9,10,13,14,16克的物體有 2種稱法 ，質(zhì)量為 6,7,11,12克的物體有 3種稱法 。 ? 從上例中看出用生成函數(shù)可比較容易地解決一些計(jì)數(shù)問題 。 ? 下面用生成函數(shù)來求多重集的 r組合數(shù) 。 ? 例：設(shè)多重集 S={?a 1,?a 2,… , ?a k}， S的 r組合數(shù)是 ar=C(r+k1,r)， 它也是方程 x1+x2+… +xk=r的非負(fù)整數(shù)解的個數(shù) 。 ? 現(xiàn)用生成函數(shù)的方法求 ar。 ? 設(shè) {ar}的生成函數(shù)為 f(y)， ? 構(gòu)造冪級數(shù) (1+y+y2+… )k， ? (1+y+y2+… )表示 ai可以不取 ,取 1個 ,2個 … , ? 把冪級數(shù) (1+y+y2+… )k展開后 ， ? yr冪來源于 yx1yx2… yxk=yx1+x2+… +xk,x1+x2+… +xk=r， ? 其中 yx1來自第一個因式 (1+y+y2+… )， ? yx2來自第二個因式 (1+y+y2+… )， … ， ? yxk來自第 k個因式 (1+y+y2+… )， 且 x1,x2,… ,xk為非負(fù)整數(shù) 。 因此展開式中 yr的系數(shù)對應(yīng)了不定方程x1+x2+…+x k=r的非負(fù)整數(shù)解的個數(shù)。故所構(gòu)造的冪級數(shù)就是 {ar}的生成函數(shù) f(y)。 由推論 : ????????0),1()1( 1)(rrk yrrkCyyf所以 ar=C(k+r1,r) 設(shè)多重集 S={n1a 1,n2a 2,…,n ka k}， S的 r組合數(shù) ar就相當(dāng)于方程 x1+x2+…+x k=r(x1?n1,x2?n2,…,x k?nk}的非負(fù)整數(shù)解的組數(shù)。 設(shè) {ar}的生成函數(shù)為 f(y)， 類似可以得到： f(y)=(1+y+y2+…+y n1)(1+y+y2+…+y n2)…(1+y+y 2+…+y nk)， 則 f(y)的展開式中 yr的系數(shù) ar就是所求的 S的 r組合數(shù)。 ? 例 :設(shè) S={?a 1,?a 2,… , ?a k}， 求 S的每個元素只出現(xiàn)偶數(shù)次的 r組合數(shù) ar。 ? 解：令 {ar}的生成函數(shù)是 f(y)， 因?yàn)橐?S的每個元素只出現(xiàn)偶數(shù)次 ， 則對 a1來講 ， 或者不出現(xiàn) ， 或者是 2， 4， 6， … 其他也類似 。 故生成函數(shù)為： ? f(y)=(1+y2+y4+… )k=1/(1y2)k ? =1+ky2+C(k+1,2)y4+… +C(k+n1,n)y2n+… ? 所以有 ???????????),1,0(120),1,0(2),1( 22??nnrnnrkCa rrr? 例：求 S={3a,4b,5c}的 10組合數(shù) a10。 ? 令 {ar}的生成函數(shù)是 f(y)， ? 則 ? f(y)=(1+y+y2+y3)(1+y+y2+y3+y4) (1+y+y2+y3+y4+y5) ? =1+3y+6y2+10y3+14y4+17y5+18y6+17y7+14y8+ 10y9+6y10+3y11+y12 ? 所以 10組合數(shù)是 6， ? 事實(shí)上我們已求得 S的所有 r組合數(shù) 。 ? 同樣 ， 用生成函數(shù)的方法也可求解不定方程的整數(shù)解組數(shù) 。 ? 例：求 x1+x2+x3=5(0?x1,0?x2,1?x3)的整數(shù)解組數(shù) 。 ? 解：令 x339。=x31， ? 則原問題即為求在約束條件 0?x1,0?x2,0?x3‘下 x1+x2+x3’=4的非負(fù)整數(shù)解組數(shù) 。 ? 解的組數(shù)為 a4,{ar}的生成函數(shù)是 ?????????????????03222),2()1(1)1)(1)(1()(rryrrCyyyyyyyyf ???所以有 a4=C(4+2,4)=15。 ?作業(yè) : ?P238:35, 36(2),37,39,40 ?P253:2,5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1