其实这道题(用数学归纳法)从小算到大比较容易理解。设Prob(m,n)表示共有m把钥匙,其中刚好n把配对的情况的数目。
首先从2把钥匙开始,Prob(2,0)=1,prob(2,2) = 1;
然后是三把钥匙,Prob(3,1) = C(3,1)*Prob(2,0) = 3*1=3,Prob(3,3) = 1, Prob(3,0) = P(3,3) - Prob(3,1) - Prob(3,3) = 6-3-1=2;
4把钥匙,Prob(4,1) = C(4,1)*Prob(3,0) = 8,Prob(4,2) = C(4,2)*Prob(2,0) = 6,Prob(4,4) = 1,Prob(4,0) = P(4,4) - Prob(4,1) - Prob(4,2) - Prob(4,4) = 24-8-6-1= 9;
因此对于5把钥匙的情况,Prob(5,1) = C(5,1)*Prob(4,0) = 5*9 = 45, Prob(5,2) = C(5,2)*Prob(3,0) = 10*2= 20, Prob(5,3) = C(5,3)*Prob(2,0) = 10, Prob(5,5) = 1, Prob(5,0) = P(5,5) - Prob(5,1) - Prob(5,2) - Prob(5,3) - Prob(5,5) = 120 -45 - 20 -10 -1 = 44。 |