还值得一提地是递推方法.doc

《还值得一提地是递推方法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、吴云：还值得一提的是递推方法。递推是组合学中一个极其重要的方法，应该引起注意。就拿此题来说，递推方法也不失为一种漂亮的解法。问题就不再描述了，直接说重点。考虑第i和j号的盒子I和J及小球I'和J'，并假设I'已放入J中。1）如果J'放入I中，则问题化归为n-2的情形；2）如果J'不放入I中，则问题化归为n-1的情形。又因为I'的取法有n-1种，所以得到递推式：f(n+2)=(n+1)[f(n+1)+f(n)]两边同时除以(n+2)!再令g(n)=f(n)/n!,进而可化为g(n+2)-g(n+1)=-

2、[g(n+1)-g(n)]/(n+2)，直接递推即可。可以令c(n)=g(n+1)-g(n),则c(n)/c(n-1)=-1/(n+1),对n=2ton求积，即c(n)/c(n-1)=-1/(n+1)c(n-1)/c(n-2)=-1/nc(n-2)/c(n-3)=-1/(n-1)……c(2)/c(1)=-1/3将这上面的n-1个式子累乘，即得c(n)的通项：c(n)=[(-1)^(n-2)]/(n+1)！=[(-1)^(n+1)]/(n+1)！即g(n+1)-g(n)=[(-1)^(n+1)]/(n+

3、1)！再用叠加法求出g(n+1)的通式，又由g(n+1)=f(n+1)/(n+1)！，进而可推出f(n+1)的通式，即f(n+1)=A(n+1,n+1)-A(n,n+1)+A(n-1,n+1)-A(n-2,n+1)+…+[(-1)^(n+1)]A(0,n+1)还有一个很重要的思想是容斥原理。作为竞赛中主要的计数原理，它的应用必定很广泛，玉龙用的就是这个方法，很漂亮。