来自朱全民老师PPT

Description

（样例：n = 3, m = 2）

A
给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
样例输出：8
B
给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
样例输出：6
C
给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
样例输出：4
D
给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
样例输出：3
E
给定N个相同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
样例输出：4
F
给定N个相同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
样例输出：2
G
给定N个相同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
样例输出：2
H
给定N个相同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
样例输出：1

Solutions

因为题目顺序有点畸形，按照正常人的思维，如下做题顺序较优：
A F E G H D C B

分别辨析：

A
给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
[分析] 每个球都可以放在任意个盒子中。
[答案] $m\cdot n$
F
给定N个相同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
[分析] 题目转化为，将n个球放在一排，在它们之间n-1个空隙选m-1个插棍子将小球分为m部分，将每部分放进盒中，问有几种分法。
[答案] $C^{m−1}_{n−1}$
E
给定N个相同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
[分析] 与上题类似，但有盒子可以为空，这就意味着两根棍子可以在同一缝隙。将问题转化，先在每个盒子放一个球再来放剩下N个球，与上题类似，将n+m个球放在一排，在它们之间n+m-1个空隙选m-1个插棍子将小球分为m部分。这样使得棍子不重合。
[答案] $C^{m−1}_{n+m−1}$
G
给定N个相同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
[分析] 设答案为 $f[n][m]$ ,数值等于有空盒子的情况（ $f[n][m-1]$ ，n个球放在m-1个盒子里）加上没空盒子的情况( $f[n-m][m]$ ,每个盒子放一个球，剩下n-m个球随便放)。
[递推式] $f[n][m]=f[n][m-1]+f[n-m][m]$
[边界条件] $f[i][j]=1(i=0\ or\ j=1),\ f[i][j]=f[i][i] (j>i)$
H
给定N个相同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
[分析] 先每个盒放一个球，再如G.
[答案] $0\ (when\ m>n),\ f[n-m][m]$ (n>=m,f同G中的f)
D
给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
[分析] 设答案为 $f[n][m]$ ，答案为 $f[n-1][m-1]$ (第n个球放在第m个盒子，其余的放在其余的格子) $+m f[n-1][m]$ (第n个球任意放，乘上n-1个球放在m个盒子中的方案数)，这样能保证一定没有空盒子。
[递推式] $f[n][m]=f[n-1][m-1]+m*f[n-1][m]$
[边界条件] $f[i][j]=1(i=j\ or\ j=1),\ 0(j>i)$
C
给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
[分析] 与D有联系，为n个盒子放在1~m个盒子的方案数的总和
[答案] $\sum_{i=1}^m f[n][i]$
B
给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
[分析] 与D有联系，为n个盒子放在1~m个盒子的方案数的总和成上m个盒子的排列总数
[答案] $n!\sum_{i=1}^mf[n][i]$ (f同D中的f)