\(M\) は固定されているとして、\(S _ {k, N}\) を、問題文の条件を満たす多重集合全体とします。

\(S _ {k, N}\) の元を、最小値に着目して分類します。

最小値が \(2\) 以上

全ての要素から \(1\) を引くという操作により、\(S _ {k, N - k}\) の元と一対一対応します。

最小値が \(1\)

\(1\) を \(1\) つ取り除くという操作により、「\(S _ {k - 1, N - 1}\) から、 \(1\) を丁度 \(M\) 個含むものを除いたもの」の元と一対一対応します。

では、\(S _ {k - 1, N - 1}\) の元のうち、\(1\) を丁度 \(M\) 個含むものはいくつあるでしょうか？ \(1\) を \(M\) 個取り除き、さらに全ての要素から \(1\) を引くという操作により、\(S _ {k - 1 - M, N - 1 - (k - 1)}\) の元と一対一対応します。

従って、以下の式が成り立ちます。

\[ \lvert S _ {k, N} \rvert = \lvert S _ {k, N - k} \rvert + \lvert S _ {k - 1, N - 1} \rvert - \lvert S _ {k - 1 - M, N - 1 - (k - 1)} \rvert \]

この式に従い計算する、時間計算量 \(\Theta(N ^ 2)\) の動的計画法が得られます。