全装错信问题即全错位排列问题及拓展

1、全装错信问题即全错位排列问题及拓展龙城老欧全装错信问题又称全错位排列问题，最早由瑞士数学家伯努利提出，最后由伯努利与他 的学生欧拉讨论解决，这个问题就是一一我们将编号是1、2、n的n封信，装入编号为1、2、n的n个信封，要求每 封信都和信封的编号不同，即1不能装进1, 2不能装进2, 3不能装进3问有多少种装 法？看到这个问题时，我们的第一反应就是退到简单处入手研究，如果只有一封信，2封信， 3封信，4封信，然后从中再思考，之间是否有共性，是否有关联，共性用归纳，关 联构成递推，或者其他。解法容易知道：al=0,a2=l, a3=2, a4=6;依我们设ai为i封信的全错位排列数据递归推理那么

2、有ai = (aiT+ai2)x (i-1)， (i=3)。为什么？为什么？为什么？大多数人看不明白。不急，尽量先自己思考，不行的话，听我来解释：思考1：对于插入第i个元素，只可能有两种情况：第一种情况:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第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)个人已经都坐在在自己的板凳上了，现在第i个人张三带着自己的板凳来 了，下面我们来对这i个人进行全错位排排坐，方法1：前面(i-1)个人中的某一个带着板凳出来与第i个人张三互换板凳坐(有(i-1) 种方法)，其它(i-2)个人进行全错位排列(有ai-2种方法)，这样就整体上都是全错位;方法2：第i个人张三走进去与将（i-1）个人中的某一个人换出来（i-1种方法），换出来的人（不妨称是李四）坐张三的板凳，换出来的李四的板凳看作张三的新板凳，这样又面临了（i-1）个元素进行

4、全错位排列问题（ai-2种方法），这样就整体上也都是全错位了。两种方法合起来求和可得i个元素进行全错位排列数：ai = （ai-1+ai-2） x（i-1） （i=3） ，a1=0,a2=1,这样就可以源源不断地求任意i个元素的全排列数了。那么能不能建立ai关于i的函数呢？这有点难，但也是可行的！ 通项公式研究：僚上所雄.利用学里面的加法和乘法瓯理可以得到谊问题的诵推公式;其I1 fl3 - 0 , o2 = U笔此*何世的就转比如求述推益贞的迹顶曲点绻 在公氏门、两腔冋脸民5 + 1】！，關m卄I _-I（m-l）耳! jj+ I （nI）! JlUtWi助数列此=工，则州=0”爲=丄，式化

5、）转化为h!2!=(n+l)i 一冷区 & 爲-I妬=(n+l)i 一冷区 & 爲-I3)45-1E =r?+1 (n-kljM卜旷l1严3)45-1E =r?+1 (n-kljM卜旷l1严(-1广匕(a -3 (ri + 1)!/2!(h+1)! n (it n %】=(rt-b l)du +从而町以得到(5)得斗5匸匕JJthOi J这样我们就得到通项公式了!这个太难了！换个“平易近人”的形式给你:n（n至少比1大）个元素全部错位的排列数加=两23广4!-拓展进一步研究一个新问题：n封信装入n个信封，其中恰有m（m小于n,比1大）封信装错的情况数为f（n,m） 这样就得到一个部分错位排列问

6、题公式：f (n, m)二 Cf (n, m)二 Cmf (m)二nCmm!n 2!11+ 3! 4!1+ (1) m!这个很容易理解，先把信全部放对，再分两步思考，第一步，选出m封信，第二步将这m 封信信全部装错，乘法原理问题得解。学会了吗？尝试练习一下吧！ 练习一1、将8封信装入8个信封，信全部装错的情况有多少种？2、编号为1-7的 7 位同学去抢编号为1-7的 7 张椅子坐，每个人坐的椅子与自己的编 号都不相同的情况有多少种？3、9 对夫妻参加舞会，在跳交谊舞时（男女搭配，全部参加）跳舞双方都不是夫妻档 的情况有多少种？ 练习二1、将8封信随机装入8个写好的信封，恰有2封信装对的情况有多少种？2、编号为1-7的 7 为同学去