这就是错排的算法(错排指没有人抽中自己的排列方法)
假设有n个人抽,错排的种类有an
n=2时,显然只有一种,A拿B,B拿A, a2=1
n=3时,A拿B,B拿C,C拿A; A拿C,C拿B,B拿A,两种, a3=2
然后需要递归了
假设n=k时有ak种错排
那么当n=k+1时
加入了k+1的名字
肯定不能是k+1自己抽
必然有第i(i不为k+1)个人拿了k+1
然后分两种情况：
(1)第k+1个人拿了i,那么这样的话就变成了k+1-2=k-1个人错排的情况
即有a(k-1)种,但是i可以取1,2,...,k
所以这种情况下的错排方法有k*a(k-1)种
(2)第k+1个人拿的不是i,那么剩下的就随便错排就行了,因为就相当于k个人错排而把i替换成了k+1而已
所以有ak种,同样的i可以取1,2,...,k
所以总共是k*ak种
所以得到递推式
a(k+1)=k*a(k-1)+k*ak
验证k=3,n=4时
A拿B,B拿A,C拿D,D拿C
A拿C,C拿A,B拿D,D拿B
A拿D,D拿A,C拿B,B拿C
A拿B,B拿C, C拿D, D拿A
A拿B,B拿D, D拿C, C拿A
A拿C,C拿B, B拿D, D拿A
A拿C,C拿D, D拿B, B拿A
A拿D,D拿B, B拿C, C拿A
A拿D,D拿C, C拿B, B拿A
a4=9
而3*a1+3*a2=3*1+3*2=9
所以递推式成立
所以持续做下去可得
a5=4*(a3+a4)=4*(9+2)=44
a6=5*(a4+a5)=5*(9+44)=265
a7=6*(a5+a6)=6*(44+265)=1854
a8=7*(a6+a7)=7*(265+1854)=14833
a9=8*(1854+14833)=133496
a10=9*(14833+133496)=1334961
而总共的可能排法是10*9*8*...*1=3628800
所以第一问的答案是
1334961/3628800=465/1264
第二问是
1-465/1264=799/1264 这就是错排的算法(错排指没有人抽中自己的排列方法)
假设有n个人抽,错排的种类有an
n=2时,显然只有一种,A拿B,B拿A, a2=1
n=3时,A拿B,B拿C,C拿A; A拿C,C拿B,B拿A,两种, a3=2
然后需要递归了
假设n=k时有ak种错排
那么当n=k+1时
加入了k+1的名字
肯定不能是k+1自己抽
必然有第i(i不为k+1)个人拿了k+1
然后分两种情况：
(1)第k+1个人拿了i,那么这样的话就变成了k+1-2=k-1个人错排的情况
即有a(k-1)种,但是i可以取1,2,...,k
所以这种情况下的错排方法有k*a(k-1)种
(2)第k+1个人拿的不是i,那么剩下的就随便错排就行了,因为就相当于k个人错排而把i替换成了k+1而已
所以有ak种,同样的i可以取1,2,...,k
所以总共是k*ak种
所以得到递推式
a(k+1)=k*a(k-1)+k*ak
验证k=3,n=4时
A拿B,B拿A,C拿D,D拿C
A拿C,C拿A,B拿D,D拿B
A拿D,D拿A,C拿B,B拿C
A拿B,B拿C, C拿D, D拿A
A拿B,B拿D, D拿C, C拿A
A拿C,C拿B, B拿D, D拿A
A拿C,C拿D, D拿B, B拿A
A拿D,D拿B, B拿C, C拿A
A拿D,D拿C, C拿B, B拿A
a4=9
而3*a1+3*a2=3*1+3*2=9
所以递推式成立
所以持续做下去可得
a5=4*(a3+a4)=4*(9+2)=44
a6=5*(a4+a5)=5*(9+44)=265
a7=6*(a5+a6)=6*(44+265)=1854
a8=7*(a6+a7)=7*(265+1854)=14833
a9=8*(1854+14833)=133496
a10=9*(14833+133496)=1334961
而总共的可能排法是10*9*8*...*1=3628800
所以第一问的答案是
1334961/3628800=465/1264
第二问是
1-465/1264=799/1264