趣味数学——伯努利-欧拉装错信封问题_风闻

文/辽源市第十九中学校 马世胜 王德贵

伯努利-欧拉装错信封问题，是数学史上著名的数论问题，其实是排列组合问题，今天我们用Python来进行分析和求解。

1.伯努利-欧拉装错信封问题

某人想邀请朋友来家中聚会，写好了5封请柬，需要装入5个信封，结果因为粗心把请柬全部装错了信封。请问：装错的可能会有多少种呢（图1）？

这个问题是由当时有名的数学家约翰·伯努利(Johann Bernoulli，1667-1748)的儿子丹尼尔·伯努利(Danid Bernoulli，17OO-1782)提出来的，瑞士著名数学家欧拉(Leonhard Euler，1707-1783)按一般情况给出解答。

这个问题可以描述为一个排列组合问题：n个元素的序列，要求在排列中没有一个元素处于它原有的位置。

2.算法分析

用编程解决排列组合问题，我们常常利用枚举法，对于这道不确定的排列组合问题，枚举法很可能不是最佳方法，不过在我们不知道具体分析思路之前，可以先试试看。

3.枚举法程序实现

先假设只有3封信的情况（图2）。

运行结果如下，有2种方法（图3）。

那么4个、5个信封应该是类似的，下面是5封信的程序，只是增加了2重循环，其它完全一样（图4）。

运行结果是44种。如果是更多的信封，这样做就很麻烦了。那么有没有规律呢（图5）？

4.递推公式法程序实现

瑞士著名数学家欧拉按一般情况给出了一个递推公式，分析如下。

用A、B、C……表示写着ｎ位友人名字的信封，a、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作D(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：

(1)b装入Ａ里，这时每种错装的其余部分都与A、B、a、b无关，应有D(n－2)种错装法。　　　　

(2)ｂ装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）n－1份信纸ｂ、ｃ……装入（除B以外的）n－1个信封A、C……，显然这时装错的方法有D(n－1)种。

总之在ａ装入B的错误之下，共有错装法D(n－2)＋D(n－1)种。

a装入C，装入D……的n－2种错误之下，同样都有D(n－1)＋D(n－2)种错装法，因此D(n)＝(n－1)[D(n－1)＋D(n－2)]

这是递推公式。令ｎ＝1、2、3、4、5逐个推算就能求出多个装错信封的解。

D(1)＝0，D(2)＝1，D(3)＝2，D(4)＝9，D(5)＝44

程序如下，这样我们就有了一个通用程序，可以求出任意一项的值（图6）。

利用递推公式，也可以求出前n项的值（图7）。

5.递归公式法程序实现

这个问题也可以用递归公式求出任意一项的值（图8）。

输入任意信封个数后可以获得满意的结果（图9）。

稍微修改一下，也可以求出前ｎ项的值（图10）。

6.结论

伯努利-欧拉装错信封问题，涉及到的是高中数学的排列组合问题，这是难点也是重点，也称为条件限制类排列问题。

用Python求解，枚举法很难实现，即使实现效率也很低，而递推和递归的方法更为有效。当然在各种算法中，枚举法虽然效率有时低一点，但对某些问题还很奏效。

递推和递归是等级考试4级内容，希望大家在学习Python过程中，循序渐进，做好基础知识的理解和掌握。