全裝錯信問題即全錯位排列問題及拓展

1、全裝錯信問題即全錯位排列問題及拓展龍城老歐全裝錯信問題又稱全錯位排列問題，最早由瑞士數(shù)學(xué)家伯努利提出，最后由伯努利與他 的學(xué)生歐拉討論解決，這個問題就是一一我們將編號是1、2、n的n封信，裝入編號為1、2、n的n個信封，要求每 封信都和信封的編號不同，即1不能裝進(jìn)1, 2不能裝進(jìn)2, 3不能裝進(jìn)3問有多少種裝 法？看到這個問題時，我們的第一反應(yīng)就是退到簡單處入手研究，如果只有一封信，2封信， 3封信，4封信，然后從中再思考，之間是否有共性，是否有關(guān)聯(lián)，共性用歸納，關(guān) 聯(lián)構(gòu)成遞推，或者其他。解法容易知道：al=0,a2=l, a3=2, a4=6;依我們設(shè)ai為i封信的全錯位排列數(shù)據(jù)遞歸推理那么

2、有ai = (aiT+ai2)x (i-1)， (i=3)。為什么？為什么？為什么？大多數(shù)人看不明白。不急，盡量先自己思考，不行的話，聽我來解釋：思考1：對于插入第i個元素，只可能有兩種情況：第一種情況:插入第i個元素時，前i-1個已經(jīng)錯位排好，則選擇其中任意一個與第i個互 換一定滿足要求，選擇方法共i-1種，前i-1位錯排fi-1種，記fi-1*(i-1),如下圖：第二種情況:插入第i個元素時，前i-1個中恰有一個元素恰好在自己的位置上，即恰好只 有一個元素不滿足錯位排列，其他i-2個錯位排好，則將i與j交換，j在i-2位中的插入 共i-1種，前i-2位錯排ai-2種，記fi-2*(i-1)

3、，如下圖：以上兩種情況求和可得：ai = (ai-1+ai-2)x(i-1) (i=3)我們還可以這樣思考：思考2：有(i-1)個人已經(jīng)都坐在在自己的板凳上了，現(xiàn)在第i個人張三帶著自己的板凳來 了，下面我們來對這i個人進(jìn)行全錯位排排坐，方法1：前面(i-1)個人中的某一個帶著板凳出來與第i個人張三互換板凳坐(有(i-1) 種方法)，其它(i-2)個人進(jìn)行全錯位排列(有ai-2種方法)，這樣就整體上都是全錯位;方法2：第i個人張三走進(jìn)去與將（i-1）個人中的某一個人換出來（i-1種方法），換出來的人（不妨稱是李四）坐張三的板凳，換出來的李四的板凳看作張三的新板凳，這樣又面臨了（i-1）個元素進(jìn)行

4、全錯位排列問題（ai-2種方法），這樣就整體上也都是全錯位了。兩種方法合起來求和可得i個元素進(jìn)行全錯位排列數(shù)：ai = （ai-1+ai-2） x（i-1） （i=3） ，a1=0,a2=1,這樣就可以源源不斷地求任意i個元素的全排列數(shù)了。那么能不能建立ai關(guān)于i的函數(shù)呢？這有點難，但也是可行的！ 通項公式研究：僚上所雄.利用學(xué)里面的加法和乘法甌理可以得到誼問題的誦推公式;其I1 fl3 - 0 , o2 = U筆此*何世的就轉(zhuǎn)比如求述推益貞的跡頂曲點綣 在公氏門、兩腔冋臉民5 + 1】！，關(guān)m卄I _-I（m-l）耳! jj+ I （nI）! JlUtWi助數(shù)列此=工，則州=0”爲(wèi)=丄，式化

5、）轉(zhuǎn)化為h!2!=(n+l)i 一冷區(qū) & 爲(wèi)-I妬=(n+l)i 一冷區(qū) & 爲(wèi)-I3)45-1E =r?+1 (n-kljM卜曠l1嚴(yán)3)45-1E =r?+1 (n-kljM卜曠l1嚴(yán)(-1廣匕(a -3 (ri + 1)!/2!(h+1)! n (it n %】=(rt-b l)du +從而町以得到(5)得斗5匸匕JJthOi J這樣我們就得到通項公式了!這個太難了！換個“平易近人”的形式給你:n（n至少比1大）個元素全部錯位的排列數(shù)加=兩23廣4!-拓展進(jìn)一步研究一個新問題：n封信裝入n個信封，其中恰有m（m小于n,比1大）封信裝錯的情況數(shù)為f（n,m） 這樣就得到一個部分錯位排列問

6、題公式：f (n, m)二 Cf (n, m)二 Cmf (m)二nCmm!n 2!11+ 3! 4!1+ (1) m!這個很容易理解，先把信全部放對，再分兩步思考，第一步，選出m封信，第二步將這m 封信信全部裝錯，乘法原理問題得解。學(xué)會了嗎？嘗試練習(xí)一下吧！ 練習(xí)一1、將8封信裝入8個信封，信全部裝錯的情況有多少種？2、編號為1-7的 7 位同學(xué)去搶編號為1-7的 7 張椅子坐，每個人坐的椅子與自己的編 號都不相同的情況有多少種？3、9 對夫妻參加舞會，在跳交誼舞時（男女搭配，全部參加）跳舞雙方都不是夫妻檔 的情況有多少種？ 練習(xí)二1、將8封信隨機裝入8個寫好的信封，恰有2封信裝對的情況有多少種？2、編號為1-7的 7 為同學(xué)去