趣味數學

馬世勝　王德貴

伯努利-歐拉裝錯信封問題，是數學史上著名的數論問題，其實是排列組合問題，今天我們用Python來進行分析和求解。

1.伯努利-歐拉裝錯信封問題

某人想邀請朋友來家中聚會，寫好了5封請柬，需要裝入5個信封，結果因為粗心把請柬全部裝錯了信封。請問：裝錯的可能會有多少種呢（圖1）？

這個問題是由當時有名的數學家約翰·伯努利（Johann Bernoulli，1667-1748年）的兒子丹尼爾·伯努利（Danid Bernoulli，1700-1782年）提出來的，瑞士著名數學家歐拉（Leonhard Euler，1707-1783年）按一般情況給出解答。

這個問題可以描述為一個排列組合問題：n個元素的序列，要求在排列中沒有一個元素處于它原有的位置。

2.算法分析

用編程解決排列組合問題，我們常常利用枚舉法，對于這道不確定的排列組合問題，枚舉法很可能不是最佳方法，不過在我們知道具體分析思路之前，可以先試試看。

3.枚舉法程序實現

先假設只有3封信的情況（圖2）。

運行結果如下，有2種方法（圖3）。

那么4個、5個信封應該是類似的，下面是5封信的程序，只是增加了2重循環，其他完全一樣（圖4）。

運行結果是44種。如果是更多的信封，這樣做就很麻煩了。那么有沒有規律呢（圖5）？

4.遞推公式法程序實現

瑞士著名數學家歐拉按一般情況給出了一個遞推公式，分析如下：

用A、B、C……表示寫著n位友人名字的信封，a、b、c……表示n份相應的寫好的信紙。把錯裝的總數記作D（n）。假設把a錯裝進B里了，包含著這個錯誤的一切錯裝法分兩類：

（1）b裝入A里，這時每種錯裝的其余部分都與A、B、a、b無關，應有D（n-2）種錯裝法。

（2）b裝入A、B之外的一個信封，這時的裝信工作實際是把（除a之外的）n-1份信紙b、c……裝入（除B以外的）n-1個信封A、C……顯然這時裝錯的方法有D（n-1）種。

總之在a裝入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）]

這是遞推公式。令n=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）。

稍微修改一下，也可以求出前n項的值（圖10）。

6.結論

伯努利-歐拉裝錯信封問題，涉及到的是高中數學的排列組合問題，這是難點也是重點，也稱為條件限制類排列問題。

用Python求解，枚舉法很難實現，即使實現效率也很低，而遞推和遞歸的方法更為有效。當然在各種算法中，枚舉法雖然效率有時低一點，但對某些問題還很奏效。

遞推和遞歸是等級考試4級內容，希望大家在學習Python的過程中，循序漸進，做好基礎知識的理解和掌握。