網(wǎng)絡(luò)路徑問(wèn)題、母函數(shù)與排列組合、容斥原理論(編輯修改稿)
2025-02-02 21:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 令 ? ? ???? 0 !nnn nxDxH。用 ? ?!11 ?? nxn乘 ? ? ? ? 11 11 ?? ???? nnn DnD 的兩端，并求和，能夠得到 ? ? ? ? ? ? ? ? ? ???? ?? ???? ??? ?? ??????? 0 110 10 11 !11!11!1 n nnn nnn nn nxnxDnnxD 上式左邊 ? ? ? ? ? ? 1??? xHxDxH ，而右邊第一項(xiàng)為 ? ?xxHnxDxnxD nnnnnn ?? ???????001!!，第二項(xiàng)為 ????? !3!2!1 321 xxx ，即 1??xe 的展開(kāi)式。 所以式子 ? ? ? ? ? ? ? ? ? ???? ??????????? ??????? 01101011 !11!11!1 nnnnnnnnn nxnxDnnxD就變成了 本 科 畢 業(yè) 論 文 第 10 頁(yè) 共 23 頁(yè) ? ? ? ? 11 ???? ? xexxHxH ，因此有 ? ? xexH x?? ?1 . 把上式中的 ??xH 寫(xiě)成 ? ? 11 ?? ?xe x 并展開(kāi)，得到下列表達(dá)式 ? ? ? ??? ?????????? ????? 3232 1!3!21 xxxxxxxH . 變形后得 ? ? ? ???? ?????? ???????0 !11!31!21!111nnn nxxH ?. 因此 !nxn 的系數(shù)就變成了 ? ? ?????? ??????? !11!31!21!111! nnD nn ?. 這就是所求的 nD 的一般式。 分析總結(jié) 由上邊的兩個(gè)例子可以看出利用母函數(shù)求解遞推關(guān)系的方法是比較適用的。組合數(shù)學(xué)的重要性在實(shí)際生活中已經(jīng)日益明顯。在各個(gè)方面已經(jīng)得到了廣泛的使用，由理論走向了實(shí)踐應(yīng)用。利用母函數(shù)來(lái)求解遞推關(guān)系在實(shí)際中也有其作用 。遞推關(guān)系在現(xiàn)實(shí)中進(jìn)行分析預(yù)測(cè)時(shí)能夠發(fā)揮很好的作用。遞推關(guān)系是計(jì)數(shù)的一個(gè)強(qiáng)有力的工具，在進(jìn)行算法分析時(shí)是必需的。上邊所提出的求解遞推關(guān)系的步驟是比較廣泛適用的基本步驟，具體問(wèn)題再具體分析。 4 容斥原理與錯(cuò)位排列 容斥原理 容斥原理又稱包含排斥原則，交叉分類原理，篩法公式，是計(jì)數(shù)法則 —— 和則的一種推廣形式。 容斥原理的簡(jiǎn)單形式：（ 1）集合內(nèi)的容斥原理，又稱容斥公式。設(shè)集合 A 包含 nAAA , 21 ?這 n個(gè)有限集合，則有 ??? ?????? ?? ??? nnni ij jk kjini ij jini in AAAAAAAAAAAA 21111121 1??????? ??????? ??????（ 2）集合外的容斥原理，又稱逐步淘汰公式。設(shè)NAAU ???，則有 本 科 畢 業(yè) 論 文 第 11 頁(yè) 共 23 頁(yè) ???? ???? nn AAANANAAAA 2121 ????? ???????? ?? nnni ij jk kjini ij jini i AAAAAAAAAN 21111 1??????? ?????? ? ??? ?? 容斥原理的一般形式：?? ? ? ? ? .0,10 nrkrWrkrrE rnk k ????????????????? 限位排列 定理 1 限位排列數(shù)為 ? ? ? ? ? ? nn rnrnrnN 1!2!1! 21 ???????? ?，式子中， ir 是有 i 個(gè)棋子布置到限位排列部分的方案數(shù)。 證明 一個(gè)棋子落入限位部分的方案數(shù)為 1r ，剩下的 n1 個(gè)棋子為無(wú)限制條件的排列，所以至少有一個(gè)棋子進(jìn)入限位部分的方案數(shù)為 ? ?!11 ?nr ，兩個(gè)棋子落入限位部分的方案數(shù)為 2r ，而其余 n2個(gè)棋子為無(wú)限制條件的排列，所以至少有兩個(gè)棋子進(jìn)入限位部分的方案數(shù)為 ? ?!22 ?nr ，其余類推。根據(jù)容斥原理， n 個(gè)棋子無(wú)一落入限位部分的方案數(shù)應(yīng)為 ? ? ? ? ? ? nnn rnrnrnAAAN 1!2!1! 2121 ??????? ??? ? ? 例 有甲乙丙丁四個(gè)人完成 ABCD四項(xiàng)任務(wù)，但是甲不能從事任 務(wù) B，乙不能從事任務(wù) BC，丙不能從事任務(wù) CD，丁不能從事任務(wù) D。若要求每人從事一項(xiàng)任務(wù)，有多少種不同的方案？ 解 每一種分配方案相當(dāng)于 ABCD的限位排列。 限位部分的棋牌多項(xiàng)式為 32 41061 xxx ??? ，即 4,10,6 321 ??? rrr ，所求的方案數(shù)44!210!36!4 ???????N 。 絕對(duì)錯(cuò)位排列 定理 2 對(duì)于 1?n ，有絕對(duì)錯(cuò)位排列數(shù)為 ? ? ?????? ??????? !11!31!21!111! nnD nn ?. 本 科 畢 業(yè) 論 文 第 12 頁(yè) 共 23 頁(yè) 證明 設(shè) jP 是集合 ? ?nS ,2,1 ?? 的全部 !n 個(gè)排列中滿足第 j 個(gè)位置上恰好是 j 的排列的特性，那么集合 ? ?? ?xPSxxAjj ???便是 S的排列中所有滿足性質(zhì) jP 的集合。 所以有 ? ? ? ??nn AAAAD 321?。由于 jA 中的每個(gè)排列均具有形式 njj ijiiii ?? 1121 ?? 。其中 njj iiiii ?? 1121 ?? 是集合 ? ?njj ,1,1,2,1 ?? ?? 的一個(gè) ? ?1?n — 排列。顯然，這種排列有 ? ?!1?n 個(gè)。所以 ? ? njnAj ,3,2,1!1 ????。 又因?yàn)??jk AA 中的每個(gè)排列都具有形式 njjkk ijiikiiii ??? 111121 ???? 。 其中 njjkk iiiiiii ??? 111121 ???? 是集合 ? ?njjkk ,1,1,1,1,2,1 ??? ???? 的一個(gè) ? ?2?n —排列，顯然，這種排列有 ? ?!2?n 個(gè)。 因此， ? ? njknAAjk ????? 1!2?. 對(duì)于 ? ?n,2,1 ? 的任意 k— 組合 ? ?kiii , 21 ? ，有 ? ?!21 knAAA ikii ??? ? ??. 另外，由于存在集合 ? ?n,2,1 ? 的 knC 個(gè) k— 組合。 應(yīng)用容斥原理 ? ? ? ? ? ? ? ?? ?? ?? ?? ? ? ?? ?? ? ????????????????????????????????????????!11!31!21!111!!!1!3!!2!!1!!!!1!2!2!2!!1!1!1!!!01!3!2!1! 321nnnnnnnnnnnnnnnnnCnCnCnCnDnnnnnnnnnn???? 定理得證。 例 1 在一個(gè)聚會(huì)結(jié)束后，有 10 位先生要取回他們的帽子，有多少種方式使得這些人中沒(méi)有人能夠拿回他們來(lái)時(shí)所戴的帽子？ 解 用公式計(jì)算得 ? ? ?????? ??????? !1011!31!21!111!10 1010 ?D . 例 2 數(shù) 9,2,1 ? 的全排列中，求偶數(shù)在原來(lái)位置上，其余都不在原來(lái)位置上的錯(cuò)排數(shù)目。 本 科 畢 業(yè) 論 文 第 13 頁(yè) 共 23 頁(yè) 解 由題意知，本題實(shí)際上是 9,7,5,3,1 這 5個(gè)數(shù)的錯(cuò)排問(wèn)題。即 5?n 所以 44!51!41!31!21!111!55 ??????? ??????D 相對(duì)的禁排列位置問(wèn)題 定理 3 對(duì)于 1?n ， ? ? ? ? ? ? ? ? !11!3!2!1! 1113 12 11 1 ?????? ?????????? nnnnnnn CnCnCnCnQ ? 證明 令 S 為集合 ? ?n,3,2,1 ? 的全部 !n 個(gè) n— 排列的集合。 jP 為排列中 出現(xiàn) ? ?1?jj 模式的性質(zhì)， ? ?1,2,1 ?? nj ? 。 jA 為滿足性質(zhì) jP 的排列的集合，因此，? ? ?? 121 ?? nn AAAQ 。 下面分析每個(gè)jA的數(shù)量。 1A 中的排列必定出現(xiàn)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1