关于排列组合问题之全错位排列递推公
式的推导!
把编号 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
s(6)=5*(9+44)=265 ....................
关于排列组合问题之全错位排列递推公
式的推导!
把编号 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
s(6)=5*(9+44)=265 ....................