淺談01隔闆法

本篇随筆簡單講解一下組合數學中的隔闆法進階（其實是特殊版本），01隔闆法。

一、01隔闆法的應用

在隔闆法的探讨中，我們已經解決了一堆球放到籃子裡，每個籃子必須至少放一個這類問題。

但是如果可以不放呢？

二、01隔闆法的概念

其實大體還是隔闆法，就相當于原先一個縫隙隻能放一個闆子，現在的縫隙可以放好多好多闆子了呗。

那就大有文章可做，至少不能按之前的方法算了。

怎麼辦呢？

我們把球抽象成0，闆抽象成1.

那麼不就相當于，在\(N\)個0和\(M-1\)個1的全排列中，除掉同類的排列，也就是：

\[\frac{(N+M-1)!}{(M-1)!N!}=C_{N+M-1}^{M-1}

\]

這就是01隔闆法了。

後記：

對于更高遠的問題，請參見：多重集的排列組合