二、有限多重集的r-組合數(shù)設(shè)多重集s={n1a1,n2a2,…,nk(編輯修改稿)
2024-11-17 12:38 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 5544 ? 相鄰禁位排列問(wèn)題 ? 定義：設(shè)集合 S={1,2,… ,n}， 如果 S的一個(gè)排列的任何兩個(gè)相鄰位置上不出現(xiàn)i,i+1(i=1,2,… ,n)的模式 ,則稱該排列是 S的一個(gè)相鄰禁位排列 。 S的所有相鄰禁位排列數(shù)記為 Qn。 ? 當(dāng) n=1時(shí) ， 只有一個(gè)數(shù) ， 當(dāng)然不相鄰 ， 所以 Q1=1； ? 當(dāng) n=2時(shí) ， 只能排成 2,1， 所以 Q2=1； ? 當(dāng) n=3時(shí) ， 可排成 1,3,2或 2,1,3， 或 3,2,1,所以 Q3=3； ? 定理：對(duì)任意的正整數(shù) n， 有 ? Qn=n!C(n1,1)(n1)!+C(n1,2)(n2)!… +(1)n1C(n1,n1)0! ? 證明：設(shè) S={1,2,… ,n}， 用 X表示 S的所有排列集合 ， 則 |X|=n!。 ? 對(duì)于 j=1,2,… ,n， 規(guī)定在一個(gè)排列中 ， 有j(j+1)出現(xiàn) ， 則該排列具有性質(zhì) pj。 ? 令 Aj表示具有性質(zhì) pj的所有排列集合 。 ? 則 S的相鄰禁位排列全體是： 121 ?nAAA ????? 例： 8人一列行走一天 ,現(xiàn)要變換位置 ,使得第 2天行走時(shí) ,沒有一個(gè)人的前面是第一天在他前面的人 ,求變換位置方式數(shù) . ? 解：把這些人用 1,2,3,4,5,6,7,8按第一天的位置編號(hào) ,排在最后的為 1,排在首位的為 8,則所求問(wèn)題就是 8個(gè)數(shù)的相鄰禁位排列問(wèn)題 ,所以 Q8=8!C(7,1)(7)!+C(7,2)(6)! C(7,3)(5)!+C(7,4)(4)!C(7,5)(3)!+C(7,6)(2)!C(7,7)1!。 ? 相鄰禁位排列與錯(cuò)位排列之間有著密切的聯(lián)系 : ? Qn=Dn+Dn1 ? 3. 相鄰禁位環(huán)排列問(wèn)題 ? 定義：設(shè)集合 S={1,2,… ,n}， 如果 S的一個(gè)環(huán)排列的任何兩個(gè)相鄰位置上不出現(xiàn)i,i+1(i=1,2,… ,n)的模式 ,并且也沒有出現(xiàn)n,1的模式 ,則稱該環(huán)排列是 S的一個(gè)相鄰禁位環(huán)排列 。 S的所有相鄰禁位環(huán)排列數(shù)記為 An。 ? 當(dāng) n=1時(shí) ， 只有一個(gè)數(shù) ， 當(dāng)然不相鄰 ， 所以 A1=1； ? 當(dāng) n=2時(shí) ， 無(wú)法滿足要求 ,所以 A2=0； ? 定理：對(duì)任意的正整數(shù) n， 有 ? An=(n1)!C(n,1)(n2)!+C(n,2)(n3)!… +(1)n1C(n,n1)0!+(1)nC(n,n)1! ? 例： 8個(gè)小孩坐在旋轉(zhuǎn)的木馬上 ,如果讓他們交換位置 ,使得每個(gè)小孩前面都不是原來(lái)在他前面的孩子 ,問(wèn)有多少種變換位置方式 ? ? 解：把這些孩子用 1,2,3,4,5,6,7,8編號(hào) ,則所求問(wèn)題就是 8個(gè)數(shù)的相鄰禁位環(huán)排列問(wèn)題 ,所以 Q8=7!C(8,1)(6)!+C(8,2)(5)!C(8,3)(4)!+C(8,4)(3)!C(8,5)(2)! +C(8,6)1! C(8,8)1!=1625。 第十二章 生成函數(shù)與遞推關(guān)系 生成函數(shù) (稱為母函數(shù) )是組合數(shù)學(xué)中的一個(gè)重要內(nèi)容 ， 可用來(lái)求解組合計(jì)數(shù)問(wèn)題 。 ? 在前面討論多重集 S={n1a 1,n2a 2,… , nka k}(n=n1+n2+… +nk})的 r組合數(shù)時(shí) ， ? 當(dāng)對(duì)一切 i=1,2,… ,k有 ni?r時(shí) ， 有計(jì)算公式 N=C(k+r1,r)； ? 當(dāng) rn， 且存在某個(gè) nir,利用容斥原理予以解決 。 ? 利用下面的組合模型來(lái)模擬多重集的 r組合數(shù) ? 設(shè)有 n個(gè)標(biāo)志為 1 , 2 , … , n的網(wǎng)袋 ， 第 i個(gè)(i=1,2,… n)網(wǎng)袋里放有 ni個(gè)球 ? (不同網(wǎng)袋里的球是不同的 ， 同一網(wǎng)袋里的球則是沒有差別的 ， 認(rèn)為是相同的 )。 ? 因此多重集 S的一個(gè) 6組合 {a1a1a3a3a3a4}就相應(yīng)于從第 1個(gè)網(wǎng)袋里取 2個(gè)球 ， 第 3個(gè)網(wǎng)袋里取 3個(gè)球 ， 第 4個(gè)網(wǎng)袋里取 1個(gè)球 。 ? 反之 ， 從第 1個(gè)網(wǎng)袋里取 2個(gè)球 ， 第 3個(gè)網(wǎng)袋里取 3個(gè)球 ， 第 4個(gè)網(wǎng)袋里取 1個(gè)球 。 就對(duì)應(yīng)了 S的一個(gè) 6組合 a1a1a3a3a3a4。 ? 一般地 ， 多重集 S的 r組合數(shù)就等于從 n個(gè)網(wǎng)袋里取 r個(gè)球的取法數(shù) 。 ? 現(xiàn)在用 x代表球 ， xi1代表從第 1個(gè)網(wǎng)袋里取 i1個(gè)球 ， xi2代表從第 2個(gè)網(wǎng)袋里取 i2個(gè)球 ， … , xik代表從第 k個(gè)網(wǎng)袋里取 ik個(gè)球 。 ? i1,i2,… ,ik 個(gè) 滿 足 條 件 i1+i2+… +i
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1