Combinations and Permutations

排列组合 "n 个球放入 m 个盒子 m" 问题。

球以及盒子有不能区分，和能区分两种属性。题目还能分成是否能有空箱子所以一共是 8 种情况。

注意文中的
C (n,m) 可以读作 n choose m ，即为 n 选 m。应该是 n 在上，m 在下。

\binom{n}{m}= \frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}

等于（注意 m 和 n 的位置是不一样的）

C_{n}^{m}= \frac{A_{n}^{m}}{m!}= \frac{n!}{m!(n-m)!}

情景#

\binom{n-1}{m-1}

或者说

C(n-1,m-1), n>=m

或者说

C_{n-1}^{m-1}, n>=m

0, n<m

使用插板法：n 个球中间有 n-1 个间隙，现在要分成 m 个盒子，而且不能有空箱子，所以只要在 n-1 个间隙选出 m-1 个间隙即可

\binom{n+m-1}{m-1}

C(n+m-1,m-1)

我们在第 1 类情况下继续讨论，我们可以先假设 m 个盒子里都放好了 1 个球，所以说白了就是，现在有 m+n 个相同的球，要放入 m 个不同的箱子，没有空箱。也就是第 1 种情况

第二类斯特林数 dp [n][m]
dp[n][m]=m*dp[n-1][m]+dp[n-1][m-1],1<=m<n
dp[k][k]=1,k>=0
dp[k][0]=0,k>=1
0,n<m

这种情况就是第二类斯特林数，我们来理解一下这个转移方程。

对于第 n 个球，如果前面的 n-1 个球已经放在了 m 个箱子里，那么现在第 n 个球放在哪个箱子都是可以的，所以 m*dp [n-1][m];

如果前 n-1 个球已经放在了 m-1 个箱子里，那么现在第 n 个球必须要新开一个箱子来存放，所以 dp [n-1][m-1]

其他的都没法转移过来

sigma dp [n][i],0<=i<=m,dp [n][m] 为情况 3 的第二类斯特林数

这种情况就是在第 3 种情况的前提下，去枚举使用的箱子的个数

dp [n][m]*fact [m],dp [n][m] 为情况 3 的第二类斯特林数，fact [m] 为 m 的阶乘

因为球是不同的，所以 dp [n][m] 得到的盒子相同的情况，只要再给盒子定义顺序，就等于现在的答案了

power (m,n) 表示 m 的 n 次方

每个球都有 m 种选择，所以就等于 m^n

dp[n][m]=dp[n][m-1]+dp[n-m][m], n>=m
dp[n][m]=dp[n][m-1], n<m
边界 dp [k][1]=1,dp [1][k]=1,dp [0][k]=1

现在有 n 个球，和 m 个箱子，我可以选择在所有箱子里面都放上 1 个球，也可以不选择这个操作。

如果选择了这个操作，那么就从 dp [n-m][m] 转移过来

如果没有选择这个操作，那么就从 dp [n][m-1] 转移过来

dp [n-m][m],dp 同第 7 种情况，n>=m
0, n<m

因为要求无空箱，我们先在每个箱子里面放 1 个球，然后还剩下 n-m 个球了，再根据情况 7 答案就出来了

————————————————