網(wǎng)絡(luò)路徑問題、母函數(shù)與排列組合、容斥原理論文(編輯修改稿)
2025-02-05 20:26 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 函數(shù)來求解遞推關(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)系的步驟是比較廣泛適用的基本步驟，具體問題再具體分析。4 容斥原理與錯(cuò)位排列 容斥原理容斥原理又稱包含排斥原則，交叉分類原理，篩法公式，是計(jì)數(shù)法則——和則的一種推廣形式。容斥原理的簡(jiǎn)單形式：（1）集合內(nèi)的容斥原理，又稱容斥公式。設(shè)集合A包含這n個(gè)有限集合，則有（2）集合外的容斥原理，又稱逐步淘汰公式。設(shè)，則有 容斥原理的一般形式：定理1 限位排列數(shù)為，式子中，是有i個(gè)棋子布置到限位排列部分的方案數(shù)。證明 一個(gè)棋子落入限位部分的方案數(shù)為，剩下的n1個(gè)棋子為無限制條件的排列，所以至少有一個(gè)棋子進(jìn)入限位部分的方案數(shù)為，兩個(gè)棋子落入限位部分的方案數(shù)為，而其余n2個(gè)棋子為無限制條件的排列，所以至少有兩個(gè)棋子進(jìn)入限位部分的方案數(shù)為，其余類推。根據(jù)容斥原理，n個(gè)棋子無一落入限位部分的方案數(shù)應(yīng)為例 有甲乙丙丁四個(gè)人完成ABCD四項(xiàng)任務(wù)，但是甲不能從事任務(wù)B，乙不能從事任務(wù)BC，丙不能從事任務(wù)CD，丁不能從事任務(wù)D。若要求每人從事一項(xiàng)任務(wù)，有多少種不同的方案？解 每一種分配方案相當(dāng)于ABCD的限位排列。限位部分的棋牌多項(xiàng)式為，即，所求的方案數(shù)。 絕對(duì)錯(cuò)位排列定理2 對(duì)于，有絕對(duì)錯(cuò)位排列數(shù)為.證明 設(shè)是集合的全部個(gè)排列中滿足第j個(gè)位置上恰好是j的排列的特性，那么集合便是S的排列中所有滿足性質(zhì)的集合。所以有。由于中的每個(gè)排列均具有形式。其中是集合的一個(gè)—排列。顯然，這種排列有個(gè)。所以。又因?yàn)橹械拿總€(gè)排列都具有形式。其中是集合的一個(gè)—排列，顯然，這種排列有個(gè)。因此，.對(duì)于的任意k—組合，有.另外，由于存在集合的個(gè)k—組合。應(yīng)用容斥原理定理得證。例1 在一個(gè)聚會(huì)結(jié)束后，有10位先生要取回他們的帽子，有多少種方式使得這些人中沒有人能夠拿回他們來時(shí)所戴的帽子？解 用公式計(jì)算得.例2 數(shù)的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置上的錯(cuò)排數(shù)目。解 由題意知，本題實(shí)際上是這5個(gè)數(shù)的錯(cuò)排問題。即所以 相對(duì)的禁排列位置問題定理3 對(duì)于，證明 令為集合的全部個(gè)n—排列的集合。為排列中出現(xiàn)模式的性質(zhì)。為滿足性質(zhì)的排列的集合，因此。下面分析每個(gè)的數(shù)量。中的排列必定出現(xiàn)12這樣的子串，即對(duì)進(jìn)行全排列。所以對(duì)一般的每個(gè)有，將它們加起來得。對(duì)于中任意兩個(gè)的交，比如是中的排列包含2種模式 共享同一個(gè)元素，如；沒有共享的元素，如。情況下就如同排列中有子串，n個(gè)元素中有3個(gè)合并成1個(gè)，就是的全排列；；情況下就如同排列中有子串就是的全排列；；一般地。更一般地，對(duì)于中的每個(gè)k—組合有由于對(duì)每一個(gè)（有相鄰的子串就一定少一個(gè)元素），存在集合的個(gè)k—組合，應(yīng)用容斥原理得到公式所以，定理得證。例 某班8個(gè)男生每天跑步，他們排成一豎行，除了第一個(gè)領(lǐng)跑的男生外，每個(gè)男生前面都有另一個(gè)男生，為了不讓他們總看見前面的同一個(gè)人，第二天要交換位置，使得前面的人與前一天的不同。他們有多少交換位置的方法？解 根據(jù)定理3得5 幾何圖形計(jì)數(shù) 計(jì)數(shù)方法在幾何學(xué)中，計(jì)數(shù)問題是比較有趣的，比如計(jì)算線段的條數(shù)，具備要求的三角形個(gè)數(shù)若干圖分平面所得的區(qū)域數(shù)等等。此類的問題看似沒有規(guī)律，但是通過分析，還是可以得到一些方法的。比如枚舉法、加法原理和乘法原理法、遞推法以及折線法。 計(jì)數(shù)方法在幾何圖形中的應(yīng)用 枚舉法例1 如下圖所示，數(shù)一數(shù)圖中有多少條不同的線段？解 對(duì)于兩條線段，只要有一個(gè)端點(diǎn)不同，就是不同的線段，所以，以左端點(diǎn)為標(biāo)準(zhǔn)，線段分5類計(jì)數(shù)。以A為左端點(diǎn)：AB,AC,AD,AE,AF共5條；以B為左端點(diǎn)：BC,BD,BE,BF共4條；以C為左端點(diǎn)：CD,CE,CF共3條；以D為左端點(diǎn)：DE,DF共2條；以E為左端點(diǎn)：EF只一條。所以不同的線段一共有5+4+3+2+1=15（條）如果一條線段上有個(gè)點(diǎn)（包
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1