對(duì)全錯(cuò)位排列問(wèn)題的拓展及新方法的探究

田震　胡鑫

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

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

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

1問(wèn)題的提出

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

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

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

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

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

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

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

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

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

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

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

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

①

（m≥n）， ②

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

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

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

再根據(jù)：

最終答案為：

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

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

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

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

③

④

由于③、④式相等

得 ⑤

⑥

故 ⑦

⑧

令： ⑨

則 ⑩

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

3結(jié)束語(yǔ)

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