这篇博客总结一下下边8种问题：

1. 有n个相同的球，k个不同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

2. 有n个相同的球，k个不同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

3. 有n个相同的球，k个相同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

4. 有n个相同的球，k个相同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

5. 有n个不同的球，k个相同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

6. 有n个不同的球，k个相同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

7. 有n个不同的球，k个不同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

8. 有n个不同的球，k个不同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

1. 有n个相同的球，k个不同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

这个问题等价于求n=a1+a2+a3+...ak ,ai不能为0的方案数。隔板法，插空法。

把n个相同的球放在一行，那么这n个球中间有n-1个空，那么在这n-1个空中选k-1个空，放k-1个隔板，就把这n个球分成了k份。

所以方案数为C(n-1,k-1)  , 组合数公式，表示从n-1个取k-1个的方案数。

例题: 牛客网 https://ac.nowcoder.com/acm/contest/553/D

2. 有n个相同的球，k个不同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

和问题1方法一样，这个允许盒子为空。n=a1+a2+a3+...ak ,ai可以为0的方案数。

这个题等价于 有n+k个相同的球，k个不同盒子，盒子不许为空的方案数。因为：把这n+k个球分到k个盒子之后，把每个盒子里的球的数量都减一，那么球的总数就是n个了，盒子里的球就可能是空的了。

所以方案数为 C（n+k-1,k-1）.

例题: 牛客网 https://ac.nowcoder.com/acm/contest/553/D

3. 有n个相同的球，k个相同的盒子，把n个球放到盒子里，盒子允许为空，有多少种方案。

这是一道动态规划题，用dp[i][j]表示把n个球放到不超过k个盒子里的方案数。

我们可以根据有没有空盒子列出下面这个转移方程：

dp[i][j]=dp[i][j-1]+dp[i-j][j]   ,解释一下：

dp[i][j-1] 表示有空盒子，那么就是i个球放到不超过j-1个盒子的方案数

dp[i-j][j] 表示没有空盒子，那么每个盒子最少要有1个球，那么先把每个盒子放一个球，还剩下i-j个球，把剩下的i-j个球分到不超过j个盒子。

dp[n][k]就是答案。

4. 有n个相同的球，k个相同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

和第3个方法一样，也是动态规划，dp[i][j]表示的意义和第3题一样。

答案应该是 dp[n][k]-dp[n][k-1].

显然，（n个球放到k个相同的盒子，盒子允许为空的方案数）减去（n个球放到k-1个盒子，盒子允许为空的方案数）就是 （n个球放到k个盒子，盒子不允许为空的方案数）。

5. 有n个不同的球，k个相同的盒子，把n个球放到盒子里，盒子不允许为空，有多少种方案。

这个题是第二类Stirling数，不知道的自己百度。

用S（n,k）表示n个不同的球，放到k个不同的盒子，盒子不允许为空的方案数。

那么 S(n,k)=S（n-1,k-1）+k*S(n-1,k)    1