冯弋舟
中图分类号:G633.6文献标识码:B文章编号:1672-1578(2018)01-0166-01
1.背景
排列组合里有一道题,叫错排问题(staggered formula)。错排问题最早被尼古拉.伯努利和欧拉研究,因此历史上也称为尼古拉.伯努利-欧拉(Bernoulli-Euler装错信封问题)。这个问题如下:写了n封信,装到n个不同的信封,每封信和信封都不匹配,问全部装错的可能性有多少种。
错排问题的标准定义是: 集合{1,2,…,n}的一个排列i1i2,…in }, 满足条件i j≠j(1≤ j≤ n),即没一个数字在它自然顺序位置的全排列。问这样的排列有多少个。n个自然数的全部错排数用Dn表示。
2.问题的提出
习题解答上在给出Dn的递推公式时,這样的:
假设i1的位置放置2(还有 3.4..n 等n-1种可能),剩下1,3,4,…n往i2,i3..in位置上放,这时错排数设为An,那么Dn=(n-1)An。An的计算又分为两种情况: (1) 1不放在第2个位置i2上,剩下n-1个数的错排数为Dn-1。(2)1放在第2个位置i2上,剩下的n-2个数的进行错排,错排数为Dn-2。所以An=Dn-1+Dn-2,所以最后总Dn=(n-1)(Dn-1 +Dn-2)。
很多刚学习错排的同学会误以为Dn-1包括Dn-2,为什么还要加Dn-2呢?
本文将分析这个问题。
3.问题分析
下面以n=4(数字小好分析)为例子分析:
2放1位置时错排列为 2143、2341、2413,放1位置的还有3和4 ,所有共有3*3=9种错排。那么2放1位置后的剩下3个数的全错排数(图1),是否包含 2放1位置和1放2位置后的错排数(图2)呢?
把2放1位置后全错排D3,是把数字1、3、4排到第2、3、4三个位置上的错排,那么数字1、3、4 排到第2、3、4位置的错排怎么排呢?
现在把数字1、3、4改为数字"2"、3、4 在第2、3、4位置上错排,"2"(其实是1)不许排在位置2上,错排数为D3。真实情况是"2"(其实是1)是排在位置2上,也是错排,但这时的 却把这情况给排除了,所以必须加上这种情况:把数字"2"(其实是1)放在位置2上,剩下3、4两数在3、4位置上错排,错排数为D2。
所以D3不包括D2。
为什么会出现以为D3包括D2的错误想法呢?因为正排[不是错排]思维导致。把数字2放1位置后的全排列数3!,包含了数字2放1位置且数字1放2位置后的全排列2!导致。
4.总结
本文澄清了错排的递推公式中一个易引起误会的问题,让更多中学生明白错误产生的原因,做题时不再发生此类错误。