回覆列表
-
1 # A名字都被起完了1
-
2 # 使用者928021938244
設1,2,...,n的全排列b1,b2,...,bn的集合為A,
而使bi=i的全排列的集合記為Ai(1
則Dn=|A|-|A1∪A2∪...∪An|.
所以Dn=n!-|A1∪A2∪...∪An|.
注意到|Ai|=(n-1)!,|Ai∩Aj|=(n-2)!,...,|A1∩A2∩...∩An|=0!=1。
由容斥原理:
Dn=n!-|A1∪A2∪...∪An|
=n!-C(n,1)(n-1)!+C(n,2)(n-2)!-C(n,3)(n-3)!+...+(-1)^nC(n,n)*0!
=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
給你看道幾乎一樣的題目五個編號為1~5的小球放進5個編號為1~5的小盒裡面,全錯位排列(即1不放1,2不放2,依次類推)一共有多少种放法這是著名的信封問題,很多著名的數學家都研究過瑞士數學家尤拉按一般情況給出了一個遞推公式:用A、B、C……表示寫著n位友人名字的信封,a、b、c……表示n份相應的寫好的信紙.把錯裝的總數為記作f(n).假設把a錯裝進B裡了,包含著這個錯誤的一切錯裝法分兩類:(1)b裝入A裡,這時每種錯裝的其餘部分都與A、B、a、b無關,應有f(n-2)種錯裝法.(2)b裝入A、B之外的一個信封,這時的裝信工作實際是把(除a之外的)份信紙b、c……裝入(除B以外的)n-1個信封A、C……,顯然這時裝錯的方法有f(n-1)種.總之在a裝入B的錯誤之下,共有錯裝法f(n-2)+f(n-1)種.a裝入C,裝入D……的n-2種錯誤之下,同樣都有f(n-2)+f(n-1)種錯裝法,因此:f(n)=(n-1){f(n-1)+f(n-2)}這是遞推公式,令n=1、2、3、4、5逐個推算就能解答蒙摩的問題.f(1)=0f(2)=1f(3)=2f(4)=9f(5)=44答案是44種錯位排列就是給自己的不算,來排列