●劉延彬 (汝陽縣第一高級(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種.