趣味數學——伯努利-歐拉裝錯信封問題_風聞

文/遼源市第十九中學校 馬世勝 王德貴

伯努利-歐拉裝錯信封問題，是數學史上著名的數論問題，其實是排列組合問題，今天我們用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過程中，循序漸進，做好基礎知識的理解和掌握。