小球與盒子

參考：​​當小球遇上盒子​​

預設問題：把 n 個小球放到 m 個盒子裡，分别有三項要求：

①球是否相同 ②盒子是否相同 ③能否有空盒。

1.球相同，盒子不同，不能有空盒

利用插闆法，n 個小球中間會存在 n-1 個空，用 m-1 塊闆插入這些空中，可以将 n 個小球分為 m 塊，是以：

\[ans=C_{n−1}^{m−1}

\]

2.球相同，盒子不同，可以有空盒

我們現在假設有 m+n 個球然後我們用 m-1 塊闆将它分隔成了 m 塊，然後，我們在每一塊中都拿出一個小球，那麼現在我們剩下 n 個小球，并且也保證了可以有空盒出現的情況，是以：

\[ans=C_{n+m−1}^{m−1}

\]

3.球不同，盒子不同，可以有空盒

每一個球都有 m 種選擇，那麼總共有 n 個球，是以：

\[ans=m^n

\]

4.球不同，盒子相同，不能有空盒

\[ans=S2(n,m)={\frac 1 {m!}}*\sum_{k=0}^{m}(-1)^k{C_m^k}*(m-k)^n

\]

\(m^n\) 的意思表示的是将\(n\)個球，\(m\)個盒子按照3來放，其中就包括了可能隻放了\(m\)個或者\(m-1\)或者\(m-2\)等等的情況，那\((m-1)^n\)中又包括了隻放了\(1<=i<=m-1\)的情況，如果說想表示\(m\)個相同盒子，\(n\)個不同球的放置，不能夠單純的靠\(m^n-(m-1)^n\)來實作，因為\(m^n\)包含了兩個\((m-1)^n\)而這兩個\((m-1)^n\)中所包含的\((m-2)^n\)又會有交集（即可能出現重複），是以需要用到容斥。最後乘\(1/m!\)是為了消除其有序性。

可以用 FFT（快速傅裡葉變換）加速

5.球不同，盒子也不同，不能有空盒

與4唯一的不同就是盒子出現的有序性，是以隻需要在上一個公式裡不除\(m!\)即可

\[ans=m!*S2(n,m)=\sum_{k=0}^{m}(-1)^k{C_m^k}*(m-k)^n

\]

6.球不同，盒子相同，可以有空盒

因為可以有空盒，我們可以枚舉每次一共用了幾個盒子，然後把相應的第二類斯特林數加起來就可以了，是以：

\[ans=\sum_{i=1}^mS2(n,i)

\]

這種數叫做貝爾數，可以說貝爾數就是其對應的第二類斯特林數之和，貝爾數對應公式：

\[B_{n+1}=\sum_{k=0}^nC_n^kB_k

\]

即枚舉包含最後一個元素的集合大小，也可以通過對應的第二類斯特林數求和得到，公式如下：

\[B_n=\sum_{k=1}^nS2(n,k)

\]

7.球相同，盒子相同，可以有空盒

設 \(f[n][m]\) 為 \(n\) 個球放到 \(m\)

如果隻有一個盤子或者沒有小球，方案數自然為 1

如果小球比盒子要少，小球肯定是放不滿盒子的，由于盒子相同，可以得到轉移 \(f[i][j]=f[i][i]\)

如果小球比盒子要多，就分為将盤子放滿和沒放滿兩種情況，即 \(f[i][j]=f[i−j][j]+f[i][j−1]\)

代碼：

for(int i=0;i<=n;i++){

for(int j=1;j<=m;j++){

if(j==1 || i==0) f[i][j]=1;

else if(i<j) f[i][j]=f[i][i];

else if(i>=j) f[i][j]=f[i-j][j]+f[i][j-1];

}

}

8.球相同，盒子相同，不能有空盒

有點類似于第一、二種情況之間的關系。

我們先假設在每一個盒子裡都放上了一個球，就跟上面的情況一樣了。

\[ans=f[n−m][m]

\]