NOIP2007初赛问题求解中的那个盒子放球问题（数学）

来源：百度知道 编辑：UC知道 时间：2024/06/27 09:01:19
题目描述比较简单：
给定n个有标号的球，标号依次为1，2，3，…，n。将这n个球放入r个相同的盒子中，不允许有空盒子，其不同的放置方法总数记为S（n，r）。

例如：S(4,2)=7，这7种不同的放置方法依次为：
{(1),(234)}
{(2),(134)}
{(3),(124)}
{(4),(123)}
{(12),(34)}
{(13),(24)}
{(14),(23)}

问当n=7，r=4时，S(7,4)=?

这个问题我的解法是按盒子里球的数目分三组：
1，1，1，4
1，1，2，3
1，2，2，2
分别有
7*6*5*1
7*6*(5C2)*1
7*(6C2)*(4C2)*1
然后加起来

但是还有两种思路：
1、先往每个盒子里放一个球，有7C2中情况，然后剩下三个自由组合
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)。