“错位”问题解法探讨“错位”问题解法探讨

何正荣

【摘要】“错位”排列是高中数学中排列组合一章的难点，很多同学对相关问题或无从下手，或分析的思路混乱.其实，该类型的题目其规律性很强，掌握了规律，相关问题可迎刃而解.在此，通过对典型的题目进行分析，探讨总结解此类题的规律.

【关键词】错位；解法；探讨；规律オ

问题(部分指定元素“错位”) 编号为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页.