小红过生日,请了五位同学,来的五位同学都将帽子挂在同一个地方.走时,彼此开了一个玩笑,都带别人的帽子,则这五个同学有几种不同的情形?

Question

小红过生日,请了五位同学,来的五位同学都将帽子挂在同一个地方.走时,彼此开了一个玩笑,都带别人的帽子,则这五个同学有几种不同的情形?

Answer 1

这是一个典型错排问题
pala提出的问题:十本不同的书放在书架上.现重新摆放,使每本书都不在原来放的位置.有几种摆法?
这个问题推广一下,就是错排问题:n个有序的元素应有n!种不同的排列.如若一个排列式的所有的元素都不在原来的位置上,则称这个排列为错排.
下面用递推的方法推导错排公式:
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
综上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
边界M(1)=0,M(2)=1
所以M(3)=2
M(4)=9
M(5)=44
共44种情况