關于錯排問題的遞推公式的一點分析

馮弋舟

中圖分類號：G633.6文獻標識碼：B文章編號：1672-1578（2018）01-0166-01

1.背景

排列組合里有一道題，叫錯排問題（staggered formula）。錯排問題最早被尼古拉.伯努利和歐拉研究，因此歷史上也稱為尼古拉.伯努利-歐拉（Bernoulli-Euler裝錯信封問題）。這個問題如下：寫了n封信，裝到n個不同的信封，每封信和信封都不匹配，問全部裝錯的可能性有多少種。

錯排問題的標準定義是： 集合{1，2，…，n}的一個排列i1i2，…in }， 滿足條件i j≠j（1≤ j≤ n），即沒一個數字在它自然順序位置的全排列。問這樣的排列有多少個。n個自然數的全部錯排數用Dn表示。

2.問題的提出

習題解答上在給出Dn的遞推公式時，這樣的：

假設i1的位置放置2（還有 3.4..n 等n-1種可能），剩下1，3，4，…n往i2，i3..in位置上放，這時錯排數設為An，那么Dn=（n-1）An。An的計算又分為兩種情況： （1） 1不放在第2個位置i2上，剩下n-1個數的錯排數為Dn-1。（2）1放在第2個位置i2上，剩下的n-2個數的進行錯排，錯排數為Dn-2。所以An=Dn-1+Dn-2，所以最后總Dn=（n-1）（Dn-1 +Dn-2）。

很多剛學習錯排的同學會誤以為Dn-1包括Dn-2，為什么還要加Dn-2呢？

本文將分析這個問題。

3.問題分析

下面以n=4（數字小好分析）為例子分析：

2放1位置時錯排列為 2143、2341、2413，放1位置的還有3和4 ，所有共有3*3=9種錯排。那么2放1位置后的剩下3個數的全錯排數（圖1），是否包含 2放1位置和1放2位置后的錯排數（圖2）呢？

把2放1位置后全錯排D3，是把數字1、3、4排到第2、3、4三個位置上的錯排，那么數字1、3、4 排到第2、3、4位置的錯排怎么排呢？

現在把數字1、3、4改為數字"2"、3、4 在第2、3、4位置上錯排，"2"（其實是1）不許排在位置2上，錯排數為D3。真實情況是"2"（其實是1）是排在位置2上，也是錯排，但這時的 卻把這情況給排除了，所以必須加上這種情況：把數字"2"（其實是1）放在位置2上，剩下3、4兩數在3、4位置上錯排，錯排數為D2。

所以D3不包括D2。

為什么會出現以為D3包括D2的錯誤想法呢？因為正排[不是錯排]思維導致。把數字2放1位置后的全排列數3！，包含了數字2放1位置且數字1放2位置后的全排列2！導致。

4.總結

本文澄清了錯排的遞推公式中一個易引起誤會的問題，讓更多中學生明白錯誤產生的原因，做題時不再發生此類錯誤。