全錯位排列問題的探究與應用

●劉延彬 (汝陽縣第一高級中學 河南汝陽 471200)

已知n個編號為1，2，…，n的不同位置，n個編號為1，2，…，n的不同元素.將元素與位置一一對應，若某元素的編號與某位置的編號相同，則稱元素與位置“編號一致”，若某元素的編號與對應位置的編號不同，則稱元素與位置“編號錯位”.一般地，把編號為1的元素不放在第1個位置，編號為2的元素不放在第2個位置，編號為3的元素不放在第3個位置，……，編號為n的元素不放在第n個位置，即編號為i(i=1，2，…，n)的元素不放在編號為i的位置上.按照這樣的規則，將n個不同元素排成一列，稱為n個不同元素的一個全錯位排列，所有這樣的排列稱為n個不同元素的全錯位排列.將n個不同元素全錯位排列的問題，稱為“全錯位排列問題”.事實上，“全錯位排列問題”是全排列的特例.

在全錯位排列問題中，若有n個元素，用A(n)表示n個不同元素全錯位排列的方法數.例如：

當n=1時，顯然A(1)=0.

當n=2時，只有1種全錯位排列情況，即A(2)=1=2·A(1)+(-1)2.

當n=3時，有2種全錯位排列情況，即A(3)=2=3·A(2)+(-1)3.

當n=4時，用1，2，3，4這4個數字組成無重復數字的4位數，其中1不在千位，2不在百位，3不在十位，4不在個位，共有9種排法，即A(4)=4·A(3)+(-1)4.

同理可驗證，A(5)=5·A(4)+(-1)5=44.

……

由此，猜想一個重要結論如下：

引理 用A(n)表示n個不同元素全錯位排列的方法數，則n個不同元素全錯位排列的方法數滿足

下面用第二數學歸納法給出引理的一般性證明.

證明(1)易知

當 n=2 時，A(2)=1，A(3)=2，滿足 A(3)=3·A(2)+(-1)3=2，式(1)成立;

當 n=3 時，A(3)=2，A(4)=9，滿足 A(4)=4·A(3)+(-1)4=9，式(1)成立.

(2)假設n≤k(k≥3)時，式(1)成立，即k個元素a1，a2，a3，…，ak全錯位排列的方法數的遞推關系為

則當 n=k+1 時，設全錯位排列的元素為 a1，a2，a3，…，ak，ak+1.在 k 個元素 a1，a2，a3，…，ak全錯位排列的基礎上，k+1個元素全錯位排列后，它們全錯位排列的方法分為2類：

①ak+1與ai(i=1，2，…，k)互調位置，其余元素全錯位排列，方法數為k·A(k-1);

②ak+1在ai(i=1，2，…，k)的位置上，但ai不在ak+1的位置上，其余元素仍然錯位排列.這樣的排列，相當于ak+1將k個元素a1，a2，a3，…，ak的每一個全錯位排列中的元素置換了一遍.k個元素a1，a2，a3，…，ak的每一個全錯位排列是k個元素，因此該類全錯位排列的方法數為k·A(k).

即當n=k+1時，式(1)成立.因此，n個元素全錯位排列的方法數的遞推關系為

下面求出A(n)的通項公式.式(1)的兩邊都除以n!，得

定理 用A(n)表示n個不同元素所有的全錯位排列的方法數，則

n個不同元素排成一列，記下每個元素的編號，重新排列后，有以下結論：

推論1 某i個元素(特定)現在的編號與原編號一致，n-i個元素現在的編號與原編號錯位的排列方法數為A(n-i).

推論2 i個元素(不特定)現在的編號與原編號一致，n-i個元素現在的編號與原編號錯位的排列方法數為Cin·A(n-i).

推論3 某i個元素(特定)在原有的位置上互相全錯位，另n-i個元素在原有的位置上互相全錯位，這樣的排列數為A(i)·A(n-i).

推論4 i個元素(不特定)在原有的位置上互相全錯位，另n-i個元素在原有的位置上互相全錯位，這樣的排列數為Cin·A(i)·A(n-i).

下面舉例說明.

例1 同寢室4人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀卡，則4張賀卡不同的分配方式有_______種.

解該題屬于4個元素的全錯位問題.由定理得故分配方式有9種.

例2 設編號為1，2，3，4，5 的5 個球及編號為1，2，3，4，5 的5 個盒子，一個盒子內放一球，恰有2 個球的編號與盒子編號相同，則投放種數有多少?

解“恰有2個球的編號與盒子編號相同”等價于“恰有3個球的編號與盒子編號不同”.

由推論2得，投放種數為C25·A(3)=10·(3-1)=20.

例3 編號為1，2，3，4，5的5個人，分別坐在編號為1，2，3，4，5的座位上，則至多2個號碼一致的坐法有多少種?

解法1 (直接法)至多2個號碼一致，分3種情況：

(1)“恰2個一致”等價于“恰3個錯位”，

(2)“恰1個一致”等價于“恰4個錯位”，

(3)“沒有一致”等價于“5個全錯位”，N3=A(5)=44.從而

例4 有4位同學在同一天的上、下午參加“身高與體重”、“立定跳遠”、“肺活量”、“握力”、“臺階”5個項目的測試，每位同學上、下午各測試一個項目，且不重復.若上午不測“握力”項目，下午不測“臺階”項目，其余項目上、下午都各測試一人，則不同的安排方式共有多少種?

解4位同學上午測試“身高與體重”、“立定跳遠”、“肺活量”、“臺階”4個項目的方法數為A44=24種.

下午測試的方法分為2類：(1)4位同學測試的項目仍然是上午的4個項目，方法數是4個元素的全錯位排列數，只需將每一個全錯位排列中的“握力”項目替換為“臺階”，方法數為A(4)=9;(2)若測“臺階”的同學剛好測“握力”項目，則方法數為A(3)=2.故下午測試的方法數共有9+2=11種.

從而上、下午不同的安排方式共有24·(9+2)=264種.