全錯(cuò)位排列問題的探究與應(yīng)用

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

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

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

當(dāng)n=1時(shí)，顯然A(1)=0.

當(dāng)n=2時(shí)，只有1種全錯(cuò)位排列情況，即A(2)=1=2·A(1)+(-1)2.

當(dāng)n=3時(shí)，有2種全錯(cuò)位排列情況，即A(3)=2=3·A(2)+(-1)3.

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

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

……

由此，猜想一個(gè)重要結(jié)論如下：

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

下面用第二數(shù)學(xué)歸納法給出引理的一般性證明.

證明(1)易知

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

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

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

則當(dāng) n=k+1 時(shí)，設(shè)全錯(cuò)位排列的元素為 a1，a2，a3，…，ak，ak+1.在 k 個(gè)元素 a1，a2，a3，…，ak全錯(cuò)位排列的基礎(chǔ)上，k+1個(gè)元素全錯(cuò)位排列后，它們?nèi)e(cuò)位排列的方法分為2類：

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

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

即當(dāng)n=k+1時(shí)，式(1)成立.因此，n個(gè)元素全錯(cuò)位排列的方法數(shù)的遞推關(guān)系為

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

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

n個(gè)不同元素排成一列，記下每個(gè)元素的編號(hào)，重新排列后，有以下結(jié)論：

推論1 某i個(gè)元素(特定)現(xiàn)在的編號(hào)與原編號(hào)一致，n-i個(gè)元素現(xiàn)在的編號(hào)與原編號(hào)錯(cuò)位的排列方法數(shù)為A(n-i).

推論2 i個(gè)元素(不特定)現(xiàn)在的編號(hào)與原編號(hào)一致，n-i個(gè)元素現(xiàn)在的編號(hào)與原編號(hào)錯(cuò)位的排列方法數(shù)為Cin·A(n-i).

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

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

下面舉例說明.

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

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

例2 設(shè)編號(hào)為1，2，3，4，5 的5 個(gè)球及編號(hào)為1，2，3，4，5 的5 個(gè)盒子，一個(gè)盒子內(nèi)放一球，恰有2 個(gè)球的編號(hào)與盒子編號(hào)相同，則投放種數(shù)有多少?

解“恰有2個(gè)球的編號(hào)與盒子編號(hào)相同”等價(jià)于“恰有3個(gè)球的編號(hào)與盒子編號(hào)不同”.

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

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

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

(1)“恰2個(gè)一致”等價(jià)于“恰3個(gè)錯(cuò)位”，

(2)“恰1個(gè)一致”等價(jià)于“恰4個(gè)錯(cuò)位”，

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

例4 有4位同學(xué)在同一天的上、下午參加“身高與體重”、“立定跳遠(yuǎn)”、“肺活量”、“握力”、“臺(tái)階”5個(gè)項(xiàng)目的測(cè)試，每位同學(xué)上、下午各測(cè)試一個(gè)項(xiàng)目，且不重復(fù).若上午不測(cè)“握力”項(xiàng)目，下午不測(cè)“臺(tái)階”項(xiàng)目，其余項(xiàng)目上、下午都各測(cè)試一人，則不同的安排方式共有多少種?

解4位同學(xué)上午測(cè)試“身高與體重”、“立定跳遠(yuǎn)”、“肺活量”、“臺(tái)階”4個(gè)項(xiàng)目的方法數(shù)為A44=24種.

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

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