關(guān)于錯(cuò)排問題的遞推公式的一點(diǎn)分析

馮弋舟

中圖分類號：G633.6文獻(xiàn)標(biāo)識碼：B文章編號：1672-1578（2018）01-0166-01

1.背景

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

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

2.問題的提出

習(xí)題解答上在給出Dn的遞推公式時(shí)，這樣的：

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

很多剛學(xué)習(xí)錯(cuò)排的同學(xué)會誤以為Dn-1包括Dn-2，為什么還要加Dn-2呢？

本文將分析這個(gè)問題。

3.問題分析

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

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

把2放1位置后全錯(cuò)排D3，是把數(shù)字1、3、4排到第2、3、4三個(gè)位置上的錯(cuò)排，那么數(shù)字1、3、4 排到第2、3、4位置的錯(cuò)排怎么排呢？

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

所以D3不包括D2。

為什么會出現(xiàn)以為D3包括D2的錯(cuò)誤想法呢？因?yàn)檎臶不是錯(cuò)排]思維導(dǎo)致。把數(shù)字2放1位置后的全排列數(shù)3！，包含了數(shù)字2放1位置且數(shù)字1放2位置后的全排列2！導(dǎo)致。

4.總結(jié)

本文澄清了錯(cuò)排的遞推公式中一個(gè)易引起誤會的問題，讓更多中學(xué)生明白錯(cuò)誤產(chǎn)生的原因，做題時(shí)不再發(fā)生此類錯(cuò)誤。