noip2007 提高组初赛 问题求解1 题解

NOIP问题求解经常考数学里的排列组合内容，建议可以专项复习下。

提供两种思路：

1、先往每个盒子里放一个球，有C(7,2)中情况，然后剩下三个自由组合。
2、用“插板方法”：七个人成为一个环，然后插入板子分割成四部分。

解法一：递推公式S(x,y)=S(x-1,y)*y+S(x-1,y-1)。因为把X个球放入Y个箱子，相当于先把X-1个球放好再放最后一个。最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子。前者对应S(x-1,y)*y (放入每一个不同的箱子都是一种不同的放法，因为箱子内原来的球不同)，后者对应S(x-1,y-1)。
解法二：7个球放入4个箱子无非是2+2+2+1或者3+2+1+1或者4+1+1+1三种情况。所以分别求解再加起来：C(7,1)*C(6,2)*C(4,2)*C(2,2)/P(3,3)+C(7*3)*C(4,2)+C(7,4)。

答案是350。