組合與排列 - shiqi

排列組合 "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 答案就出來了

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