Question

假如有五个数字分别要放置在编号为12345的位置上（设计成一组一组的序列），如果序列在每个位置都不重叠相同数字的话能排5组，如果不管重叠多少个数字的话（全部排列组合）应该是120组，现在的问题是如果让它重叠一个、两个、三个数字分别能排多少组？用公式怎么算？

Answer 1

考点：排列、组合及简单计数问题

专题：排列组合

分析：先根据题意求出D_n=（n-1）（D_n-2+D_n-1），特殊地，D₁=0，D₂=1，再分别求出重叠一个、两个、三个数字分别能排的组数，得到公式，问题得以解决．

解答： 解：当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D_n表示，那么D_n-1就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推．第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：（1）把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D_n-2种方法；（2）第k个元素不把它放到位置n，这时，对于这n-1个元素，有D_n-1方法；
综上得到，
D_n=（n-1）（D_n-2+D_n-1），
特殊地，D₁=0，D₂=1，
所以，D₃=2×（0+1）=2，
D₄=3×（1+2）=9，
重叠三个：有C₅³×D₂=10×1=10组，
重叠二个：有C₅²×D₃=10×2=20组，
重叠一个：（即1放在1号位，或2放在2号位，…，且只有一个数字对号），有C₅¹×D₄=5×9=45组，
公式为C_n^m×D_n-m（其中n为元素的个数，m为重叠的个数）

点评：本题考查了排列组合的问题，关键是求出元素编号与位置编号各不对应的方法数D_n，属于中档题．