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