全错位排列问题的探究与应用

2012-08-27刘延彬汝阳县第一高级中学河南汝阳471200

中学教研(数学) 2012年3期

●刘延彬 (汝阳县第一高级中学河南汝阳 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).