【摘 要】 有关乱序排列的最经典问题就是欧拉错放信笺问题，很多文章与参考书都给出了答案，但很少系统的介绍其解法，在此个人进行了一些研究，并总结了一些与其他知识相联系的心得。
　　【关键词】 Bernoulli-Euler 错放信笺问题 贝努利-欧拉 乱序排列
　　
　　Bernoulli-Euler错放信笺问题：某人给n个人各写了一封信，准备了n个写有收信人地址的信封，问有多少种投放信笺的可能，使每封信笺与信封上写的收信人不相符？
　　解法一：首先将问题转化为图论中的问题，以结点xi表示信笺，结点yi表示信封（i=1，2，3，4，5，6....n），xl与yk有边，表示信笺与信封不相符。于是问题变为求的二分图G=Kn，n中有多少个完美匹配。
　　现设G中完美匹配的个数为φ（n），x1与y2相配时，完美匹配的个数等于从图G中删除结点x1与y2后所得的图G（x1，y2）中完美匹配的个数，这个数记为ψ（k-1）。在G（x1，y2）中，若x2与y1相配，则ψ（k-1）=φ（k-2）；若x2不与y1相配，则ψ（k-1）=φ（k-1）。于是G中x1与y2相配时，可得φ（k-1）+φ（k-2）个完美匹配；同理，x1与yj（3≤j≤k）相配时，亦有φ(k-1）+φ(k-2）个完美匹配，故φ（k）=（k-1）［φ（k-1）+φ（k-2）］；所以 我们有 φ（n）=（n-1）［φ（n-1）+φ（n-2）］，φ（2）=1，φ（1）=0。
　　下面由上面的数列an=（n-1）（an-1+an-2），a2=1，a1=0。验证符合。用递推如下：ａｎ＝（ｎ－１）（ａｎ－１＋ａｎ－２）；ａｎ－ｎａｎ－１＝－［ａｎ－１－（ｎ－１）ａｎ－２］。设ｂｎ＝ａｎ－ｎａｎ－１，（n∈N，n≥2）又a2=1，a1=0，所以有：类推…ｂｎ＝ａｎ－ｎａｎ－１∴ｂｎ＋ｎｂｎ－１＋ｎ（ｎ－１）ｂｎ－２＋…＋ｂｎ－ｍ＋…＋ｂ２＝ａｎ－ｎ！ａ１＝ｎ！－ｃｎ１（ｎ－１）！＋…（－１）ｋｃｎｋ（ｎ－ｋ）！＋…＋（－１）ｎｃｎｎ０！
　　解法二：用容斥关系求解：设U为所有装法构成的集合，则显然有card(U)=n！则我们对信与信封编号为1，2，3……n，并记Ai为第i封信恰好装入第i个信封的所有装法的集合，则CuAi为第i封信不装入第i个信封的所有装法的集合，记为 card（CuA）而求全部都装错的装法集合即为：card（CUA1∩CUA2∩.....∩CUAn），由容斥关系我们可以得到：card(CUA1∩CUA2∩….∩CUAn）=ｎ！－ｃｎ１（ｎ－１）！＋…（－１）ｋｃｎｋ（ｎ－ｋ）！＋…＋（－１）ｎｃｎｎ０！
　　在这里我们又得到了一种递归数列的求法，通过模型转换用排列与图论结合，可以很快得出结论。
　　参考文献
　　１ 高中数学课本