关于排列组合问题之全错位排列递推公式的推导
巡山小妖精
805次浏览
2021年01月10日 15:09
最佳经验
本文由作者推荐
动漫视频网站-乘法分配律
.
关于排列组合问题之全错位排列递推公式的推导
这个推导是偷军团—云淡的，不是我的独创（转载请注明作者：军团—云淡）
把编号 1
-------------n的小球放到编号1------
n的盒子里，全错位排列（1号球不在
1号盒，2号球不在2号盒，依次类推），共有几种情况？
设n个球全放错的情况有 s（n）种
1号盒子可以选[2,n]
共（n-1）种选择，设1号盒选择某号球后对应的错排次数
是 a
（n-1）个选择对应的错排次数是相同的 ，则 s（n）=（n-1）a
不妨设1号盒选择2号球
1： 2号盒选择1号球，剩下 （n-2）个球去错排，有
s（n-2）种情况
2：
2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球
换成2号球，
对问题没有影响，此时就相当于对（n-1）个球去错排，有s（n-1）种情况
于是a=
s（n-1)+s(n-2)
s(n)=(n-1) [ s（n-1）+s（n-2）]
s(2)=1,s(3)=2
s(4)=3*(1+2)=9
s(5)=4*(2+9)=44
.........
.
.
例题1.5个信封都写有1-5编号，现在放进5个有编号1-5的邮箱，
问信封和邮
箱都不相同的情况有多少种？
.