對全錯位排列問題的拓展及新方法的探究

田震　胡鑫

摘 要 全錯位排列問題一直是組合數(shù)學(xué)中的經(jīng)典問題，本文在前人研究的基礎(chǔ)上，想出了一個新穎的計算方法——“相式”計算法，可單獨(dú)利用“相式”進(jìn)行計算，也可以將“相式”與前人已總結(jié)出的公式相結(jié)合，得到一個全新的計算表達(dá)式，該表達(dá)式適用于以往經(jīng)典全錯位排列模式以外的排列數(shù)計算，使全錯位排列問題得到了進(jìn)一步的解決。

關(guān)鍵詞 全錯位排列 拓展 新方法 探究

中圖分類號：G623.5 文獻(xiàn)標(biāo)識碼：A

1問題的提出

全錯位排列問題，也稱“伯努利-歐拉錯裝信封問題”，題意為：某人寫了n封信及相應(yīng)的n個不同信封，問他把這n封都裝錯信封的裝法有多少種？

數(shù)學(xué)家歐拉給出了該問題的公式推導(dǎo)：他用A、B、C…分別表示n個信封，a、b、c…則分別表示n份相對應(yīng)的信紙。把錯裝的總數(shù)記作F（n）。若把a(bǔ)錯裝進(jìn)B，則該錯誤的錯裝法分兩類：

（1）b裝入A，有F（n-2）種錯裝。

（2）b裝入A、B之外的信封，有F（n-1）種錯裝。

故a裝入B，共F（n-2）+F（n-1）種錯裝。a裝入C、D…同樣有F（n-2）+F（n-1）種錯裝，故：

F（n）=（n-1）[F（n-1）+F（n-2）]

F（1）=0，F(xiàn)（2）=1

2“相式”原理及推導(dǎo)

有m個盒子和m個小球，盒子和小球都分別標(biāo)著1，2，3...，其中m個小球中的n個小球編號分別與m個盒子中的n個盒子編號相同（剩余m-n個小球之間編號互不相同），若將m個盒子里放入這m個小球，要求小球編號與盒子編號不同的放法有幾種？

先把與小球編號相同的其中一個盒子置于首位，將該盒子放入與其編號不同的小球，應(yīng)有m-n種放法，在第一個盒子里的小球確定之后，剩下m-1個盒子里放入m-1個小球，其中這m-1個小球中有n-1個小球與盒子編號相同，我們把這n-1小球放入m-1個盒子中的排列數(shù)記作：

接下來將置于首位的盒子放入與盒子編號相同的小球（其中與首位盒子編號相同的小球不能放入），這時小球放入首位盒子的放法有n-1種，剩下m-1個盒子中有n-2個小球編號與之相同，同理，將這n-2個小球放入m-1個盒子中的排列數(shù)記作：

最后排列總數(shù)可表示為：

①

（m≥n）， ②

我們把含“”符號的等式稱為“相式”。指把m個標(biāo)有不同編號的小球（其中n個小球編號與盒子編號相同）放入m個標(biāo)有不同編號的盒子，且要求小球與盒子編號不同的排列數(shù)。

例：現(xiàn)有編號為1，2，3，4的四個小球和編號為1，2，3，4的四個盒子，將這四個小球放入這四個盒子中，其中小球編號不能與盒子編號相同的放法有多少種？

根據(jù)題設(shè)條件得知：m=4，n=4，代入①、②式有：

再根據(jù)：

最終答案為：

假如上述例題中的四個小球編號分別是1，2，3，5將其放入編號分別1，2，3，4的盒子中，問小球編號與盒子編號不同的放法有多少種？

同理，知m=4，n=3，代入上述①、②式中：

，而，由于，故，得出：=11

在本題中發(fā)現(xiàn)遞推公式不再適用，而“相式”則可算得結(jié)果。為便于計算作如下推導(dǎo)：當(dāng)m=n時，有：

③

④

由于③、④式相等

得 ⑤

⑥

故 ⑦

⑧

令： ⑨

則 ⑩

若將上述例題用⑨⑩式，即m=4，代入得：

3結(jié)束語

錯排問題是組合數(shù)學(xué)常遇到的問題，本文用“相式”對錯排關(guān)系及排列數(shù)進(jìn)行數(shù)學(xué)語言的表達(dá)，在前人研究的基礎(chǔ)上，建立了能夠解決大多數(shù)錯排問題的計算公式，總之錯排問題還有待進(jìn)一步的探索。