“錯位”問題解法探討“錯位”問題解法探討

何正榮

【摘要】“錯位”排列是高中數學中排列組合一章的難點，很多同學對相關問題或無從下手，或分析的思路混亂.其實，該類型的題目其規律性很強，掌握了規律，相關問題可迎刃而解.在此，通過對典型的題目進行分析，探討總結解此類題的規律.

【關鍵詞】錯位；解法；探討；規律オ

問題(部分指定元素“錯位”) 編號為1號至n(n≥2)號的n名運動員，分別從編號為1號至n號的n個運動項目中各選擇1個不同的運動項目進行訓練.如果1號至k號(k＜n)的k名運動員不選擇與自身編號相同的運動項目,求滿足條件的不同選擇種數.

解法1 利用容斥原理求解.

容斥原理：對k個集合M1，M2，…，M璳，則

玞ard(M1∪M2∪…∪M璳)

=А1≤i≤kИ玞ard(M璱)-А1≤i1

其中А1≤i1

設i(i≤k)號運動員選擇i號運動項目，其余運動員在其余運動項目中各選擇1個不同的運動項目時，所有選擇結果為元素構成集合M璱.則這樣的集合有M1,M2,…,M璳共獵1璳個，每個集合的元素個數均為獳﹏-1﹏-1，這獵1璳個集合元素個數之和

А1≤i≤kИ玞ard(M璱)=獵1璳?獳﹏-1﹏-1.

從集合M1,M2,…,M璳中任取m(2≤m＜k)個集合的交集有獵玬璳個，每個交集均為指定1號至k號運動員中的m名運動員選擇與自身編號相同的運動項目，其余n-m名運動員在其余n-m項運動項目中各選擇1個不同的運動項目時，所有選擇結果為元素構成的集合，所以每個交集的元素個數均為獳﹏-m﹏-m，這獵玬璳個交集的元素個數之和

А1≤i1

交集M1∩M2∩…∩M璳是1號至k號運動員均不選擇與自身編號相同的運動項目，其余n-k名運動員在其余n-k項運動項目中各選擇1個不同的運動項目時，所有選擇結果為元素構成的集合，所以其元素個數

玞ard(M1∩M2∩…∩M璳)=獳﹏-k﹏-k=獵琸璳?獳﹏-k﹏-k.

由容斥原理，得

玞ard(M1∪M2∪…∪M璳)=獵1璳?獳﹏-1﹏-1-獵2璳?獳﹏-2﹏-2+…+（-1）﹎-1獵琺璳?獳﹏-m﹏-m+…+（-1）﹌-1獵玨璳?獳﹏-k﹏-k.①

而并集M1∪M2∪…∪M璳是1號至k號運動員中至少有一名運動員選擇與自身編號相同的運動項目時，所有選擇結果為元素構成的集合，所以其補集就是1號至k號運動員均不選擇與自身編號相同的運動項目時，所有選擇結果為元素構成的集合，其元素個數即為所求的不同選擇種數，記所求的不同選擇種數為a﹏,k，于是

a﹏,k=獳琻璶-玞ard(M1∪M2∪…∪M璳).②

由①和②得：

a﹏,k=獳琻璶-獵1璳?獳﹏-1﹏-1+獵2璳?獳﹏-2﹏-2-…+（-1）琸獵玨璳?獳﹏-k﹏-k.這就是原問題的求解公式.

解法2 用數學歸納法求解.

為方便敘述，把k=m時滿足條件的不同選擇種數記為a﹏,m.

當k=1，即“1號運動員不選擇1號運動項目，每名運動員各選擇1個不同運動項目”時，其對立事件“1號運動員選擇1號運動項目，其余運動員各選擇1個不同運動項目”的不同選擇種數為

獳﹏-1﹏-1，所以a﹏,1=獳琻璶-獳﹏-1﹏-1.③

k=1時分為兩種情形：

一是“2號運動員選擇2號運動項目”，這是去掉了2號運動員和2號運動項目的問題，由③得滿足條件的不同選擇種數

a﹏-1,1=獳﹏-1﹏-1-獳﹏-2﹏-2；

二是“2號運動員不選擇2號運動項目”，這就是k=2時的情形，其不同選擇種數為a﹏,2，所以

a﹏,2=a﹏,1-a﹏-1,1=獳琻璶-獳﹏-1﹏-1-(獳﹏-1﹏-1-獳﹏-2﹏-2)

=獵02?獳琻璶-獵12?獳﹏-1﹏-1＋獵22?獳﹏-2﹏-2.④

同理k=2時分兩種情形：

一是“3號運動員選擇3號運動項目”，這就是去掉了3號運動員和3號運動項目的問題，其不同選擇種數為a﹏-1,2，由④得

a﹏-1,2=獵02?獳﹏-1﹏-1-獵12?獳﹏-2﹏-2＋獵22?獳﹏-3﹏-3；

二是“3號運動員不選擇3號運動項目”，即k=3時的情形，其不同選擇種數為a﹏,3，

所以

a﹏,3=a﹏,2-a﹏-1,2

=獵02?獳琻璶-獵12?獳﹏-1﹏-1＋獵22?獳﹏-2﹏-2-(獵02?獳﹏-1﹏-1-┆獵12?獳﹏-2﹏-2+獵22?獳﹏-3﹏-3)

=獵03?獳玭璶-獵13?獳﹏-1﹏-1＋獵23?獳﹏-2﹏-2-獵33?獳﹏-3﹏-3.

設k=m時，

a﹏,m=獵0璵?獳琻璶-獵1璵?獳﹏-1﹏-1＋獵2璵?獳﹏-2﹏-2-…＋(-1)琺獵玬璵?獳﹏-m﹏-m成立.⑤

下面證明當k=m＋1時，

a﹏,m+1=獵0﹎+1?獳琻璶-獵1﹎+1?獳﹏-1﹏-1＋獵2﹎+1?獳﹏-2﹏-2-…＋(-1)琺獵玬﹎+1?獳﹏-m﹏-m＋(-1)﹎+1獵﹎+1﹎+1?獳﹏-(m+1)﹏-(m+1)成立.

同理k=m時分為兩種情形：

一是“m＋1號運動員選擇了m＋1號運動項目”，這就是去掉了m＋1號運動員和m＋1號運動項目問題，其不同選擇種數為a﹏-1,m，由⑤得

a﹏-1,m=獵0璵?獳﹏-1﹏-1-獵1璵?獳﹏-2﹏-2+獵2璵?獳﹏-3﹏-3-…+（-1）﹎-1獵﹎-1璵?獳﹏-m﹏-m+(-1)琺獵琺璵?獳﹏-m-1﹏-m-1;

二是“m＋1號運動員不選m＋1號運動項目”，這就是k=m+1時的情形，其不同選擇種數為a﹏,m+1，所以

a﹏,m+1=a﹏,m-a﹏-1,m=獵0玬?獳玭璶-獵1璵?獳﹏-1﹏-1＋獵2璵?獳﹏-2﹏-2-…

＋（-1）﹎-1獵﹎-1璵?獳﹏-m+1﹏-m+1＋(-1)﹎獵琺璵?獳﹏-m﹏-m-［獵0璵?獳﹏-1﹏-1-獵1璵?獳﹏-2﹏-2＋…＋(-1)﹎-1?獵﹎-1璵?獳﹏-m﹏-m＋(-1)﹎獵玬璵?獳﹏-m-1﹏-m-1］=獵0玬?獳玭璶-(獵1璵＋獵0璵)獳﹏-1﹏-1＋(獵2璵＋獵1玬)獳﹏-2﹏-2＋…＋［(-1)琺獵琺璵-(-1)﹎-1獵﹎-1璵］獳﹏-m﹏-m-(-1)琺獵琺璵?獳﹏-m-1﹏-m-1.

因為獵玬璶+獵﹎-1璶=獵﹎﹏+1，

所以獵1璵＋獵0璵=獵1﹎+1，獵2璵＋獵1璵=獵2﹎+1，…，オ獵琺璵＋獵﹎-1﹎=獵琺﹎+1.

而獵0璵=獵0﹎+1，(-1)琺獵琺璵-(-1)﹎-1獵﹎-1璵=(-1)琺(獵琺璵＋獵﹎-1璵)，-(-1)琺獵琺璵=(-1)﹎+1獵﹎+1﹎+1，所以k=m＋1時，

a﹏,m+1=獵0﹎+1?獳琻璶-獵1﹎+1?獳﹏-1﹏-1＋獵2﹎+1?獳﹏-2﹏-2-…＋(-1)琺獵琺﹎+1?獳﹏-m﹏-m＋(-1)﹎+1獵﹎+1﹎+1?獳﹏-(m+1)﹏-(m+1）成立.

綜上所述，得

a﹏,k=獵0璳?獳琻璶-獵1璳?獳﹏-1﹏-1＋獵2璳?獳﹏-2﹏-2-…＋(-1)琸獵琸璳?獳﹏-k﹏-k.這與容斥原理的解法殊途同歸.

變式1(完全“錯位”) 編號為1號至n(n≥2)號的n名運動員，分別從編號為1號至n號的n個運動項目中各選擇1個不同運動項目進行訓練.如果每名運動員均不選擇與自身編號相同的運動項目，求滿足條件的不同選擇種數.

解法1 用原問題的求解公式求解.

原問題中，當k=n時，就是完全“錯位”問題.令獳00=1，得

a﹏,n=獵0璶?獳琻璶-獵1璶?獳﹏-1﹏-1＋…＋(-1)﹏-1獵﹏-1璶?獳11＋(-1)琻獵琻璶?獳00.這就是完全“錯位”問題的求解公式.

解法2 用遞推法求解.

遞推法1 設n=k時，滿足條件的選擇種數為a﹌,k.

分兩步考慮：第一步，首先由1號運動員選擇運動項目，選擇種數為n-1.第二步，若1號運動員選擇的是i號(i≤﹏且猧≠1)運動項目，則由i號運動員第二個選擇運動項目，i號運動員的選擇分為兩類：第一類是i號運動員選擇1號運動項目，此時1號運動員和i號運動員的選擇確定了，這就是“n-2名運動員和n-2個運動項目”的完全“錯位”問題，選擇種數為a﹏-2,n-2；第二類是i號運動員不選擇1號運動項目，此時1號運動項目替代了i號運動項目的作用(因為i號運動項目不會被再選擇)，這就是“n-1名運動員和n-1個運動項目”的完全“錯位”問題，選擇種數為a﹏-1,n-1，于是得：a﹏,n=(n-1)(a﹏-2,n-2＋a﹏-1,n-1)(n≥4).⑥

顯而易見，n=2時，a2,2=1；n=3時，a3,3=2，所以式⑥是完全“錯位”問題求解的遞推公式.此式表達簡潔且分散了運算量.

遞推法2 “n名運動員從n個運動項目中各選擇1個不同項目”選擇種數為獳琻璶，可分為n類：n名運動員均不選擇與自身編號相同的運動項目，選擇種數為a﹏,n；n名運動員中有且只有1名運動員選擇與自身編號相同的運動項目，選擇種數為獵1璶?a﹏-1,n-1；n名運動員中有且只有2名運動員選擇與自身編號相同的運動項目，選擇種數為獵2璶?a﹏-2,n-2；…；n名運動員中有且只有n-2名運動員選擇與自身編號相同的運動項目，選擇種數為獵﹏-2璶?a2,2；所有運動員均選擇選擇與自身編號相同的運動項目，選擇種數為1(n名運動員中不可能有且只有n-1名運動員選擇與自身編號相同的運動項目).于是得

a﹏,n=獳琻璶-獵1璶?a﹏-1,n-1-獵2璶?a﹏-2,n-2-…-獵﹏-2璶?a2,2-1(n≥3，a2,2=1).此式也是完全“錯位”問題求解的遞推公式，只是沒有遞推法1中的遞推公式簡潔.

利用遞推法2的分析思路，也可得到原問題求解的一種遞推方法.原問題可以這樣分類：k＋1號至n號運動員中，每名運動員均不選擇與自身編號相同的運動項目(即沒有運動員選擇與自身編號相同的運動項目)，選擇種數為a﹏,n；k＋1號至n號運動員中有且只有1名運動員選擇與自身編號相同的運動項目，選擇種數為獵1﹏-k?a﹏-1,n-1；k＋1號至n號運動員中有且只有2名運動員選擇與自身編號相同的運動項目，選擇種數為獵2﹏-k?a﹏-2,n-2；…；k＋1號至n號運動員中所有運動員均選擇與自身編號相同的運動項目(即有n-k名運動員選擇與自身編號相同的運動項目)，選擇種數為獵﹏-k﹏-k?a﹌,k.所以

a﹏,k=a﹏,n＋獵1﹏-k?a﹏-1,n-1＋獵2﹏-k?a﹏-2,n-2＋…＋┆獵﹏-k﹏-k?猘﹌,k.

變式2(限額“錯位”) 編號為1號至n(n≥2)號的n名運動員，分別從編號為1號至n號的n個運動項目中各選擇1個不同的運動項目進行訓練，求有且只有k(1≤k≤n)名運動員不選擇與自身編號相同的運動項目的不同選擇種數.

簡析 由題意知，n名運動員中，有n-k名運動員所選擇的運動項目的編號與自身編號相同，所以不同選擇種數為獵﹏-k璶?a﹌,k.

變式3(部分元素“錯位”) 編號為1號至n(n≥2)號的n名運動員，分別從編號為1號至n號的n個運動項目中各選擇1個不同的運動項目進行訓練，求至少有k(1≤k＜n)名運動員不選擇與自身編號相同的運動項目的不同選擇種數.

簡析 至少有k名運動員不選擇與自身編號相同的運動項目包含：n名運動員均不選擇與自身編號相同的運動項目，即沒有運動員選擇與自身編號相同的運動項目，其選擇種數為a﹏,n；有且僅有n-1名運動員不選擇與自身編號相同的運動項目，即有且僅有1名運動員選擇與自身編號相同的運動項目，選擇種數為獵1璶?a﹏-1,n-1；…；有且僅有k＋1

名運動員不選擇與自身編號相同的運動項目，即有且僅有﹏-猭-1名運動員選擇與自身編號相同的項目選擇種數為獵﹏-k-1璶?a﹌+1,k+1；有且僅有k名運動員不選擇與自身編號相同的運動項目，即有且僅有n-k名運動員不選擇與自身編號相同的運動項目，選擇種數為獵﹏-k璶?a﹌,k.所以，至少有k名運動員不選擇與自身編號相同的運動項目的不同選擇種數為

a﹏,n＋獵1璶?a﹏-1,n-1＋…＋獵﹏-k-1璶?a﹌+1,k+1＋獵﹏-k璶?a﹌,k.

變式4 從編號為1號至n(n≥2)號的n名運動員中抽出m(m＜n)名運動員，分別在編號為1號至m號的m項運動項目中選擇1個不同運動項目進行訓練.如果1號至k(k＜m)號運動員均不選擇與自身編號相同的運動項目，求滿足條件的不同選擇種數.

簡析 當m≤n-k時，1號至k號運動員中被抽出的人數可以是0至k，所以此時分為k＋1類：1號至k號運動員中被抽出的人數為0，k＋1號至n號運動員中被抽出的人數為m，滿足條件的不同選擇種數為獳﹎﹏-k；1號至k號運動員中被抽出的人數為1，k＋1號至n號運動員中被抽出的人數為m-1，此時被抽出的m名運動員中有1名“錯位”，所以滿足條件的不同選擇種數為獵1璳?獵﹎-1﹏-k?a﹎,1；…；1號至k號運動員中被抽出的人數為k，k＋1號至n號運動員中被抽出的人數為m-k，此時被抽出的m名運動員中有k名“錯位”，所以滿足條件的不同選擇種數為獵琸璳?獵﹎-k﹏-k?a﹎,k.所以滿足條件的不同選擇種數為：獳玬﹏-k＋獵1璳?獵﹎-1﹏-k?a﹎,1＋…＋獵琸璳?獵﹎-k﹏-k?a﹎,k.

當m＞n-k時，1號至k號運動員中被抽出的人數可以是m＋k-n至k，所以此時分為n-m＋1類：1號至k號運動員中被抽出的人數為m＋k-n，k＋1號至n號運動員中被抽出的人數為n-k，此時被抽出的m名運動員中有m＋k-n名“錯位”，所以滿足條件的不同選擇種數為獵﹎+k-n璳?獵﹏-k﹏-k?a﹎,m+k-n；1號至k號運動員中被抽出的人數為m＋k-n＋1，k＋1號至n號運動員中被抽出的人數為n-k-1，此時被抽出的m名運動員中有m＋k-n＋1名“錯位”，所以滿足條件的不同選擇種數為獵﹎+k-n+1璳?獵﹏-k-1﹏-k?a﹎,m+k-n+1；…；1號至k號運動員中被抽出的人數為k，k＋1號至n號運動員中被抽出的人數為m-k，此時被抽出的m名運動員中有k名“錯位”，所以滿足條件的不同選擇種數為獵﹌璳?獵﹎-k﹏-k?a﹎,k.所以滿足條件的不同選擇種數為：獵﹎+k-n璳?獵﹏-k﹏-k?a﹎,m+k-n＋獵﹎+k-n+1璳?獵﹏-k-1﹏-k?a﹎,m+k-n+1＋…＋獵琸璳?獵﹎-k﹏-k?a﹎,k.

【參考文獻】

葛軍主編.新編高中數學奧賽指導（2005年10月第3版）.第2頁、第3頁、第4頁.