解説の最後の式の形式的冪級数による導出です。本解説同様に \(\mathrm{mex}\) の総和を求めます。

\(h(m)\) を \(\mathrm{mex}\) が \(m\) 以上であるような \(A\) の個数とします。このとき、求めるべきは

\[\displaystyle\sum_{m=1}^{M}h(m)=\displaystyle\sum_{m=0}^{M}h(m)-M^N\]

です（\(\mathrm{mex}\) がちょうど \(m\) であるものがちょうど \(m\) 回数えられることから従います）。ここで、

\[p(x):=\displaystyle\sum_{i=0}^{N}\dfrac{x^i}{i!}, \quad q(x):=\displaystyle\sum_{i=1}^{N}\dfrac{x^i}{i!}=p(x)-1\]

とします。このとき、

\[h(m)=[x^N] N! ( p^{M-m} q^m )(x)\]

が成り立ちます。これは、数列において、要素として \(i\) が表れる回数を \(a_i\) としたときに、\(\mathrm{mex}\) が \(m\) 以上であることは \(a_0,a_1, \dots, a_{m-1}\) が正であることと同値であり、また、このような数列の個数は

\[\dfrac{N!}{\prod_{i=0}^{M-1}a_i!}\]

であることから従います。 よって

\[\displaystyle\sum_{m=0}^{M}h(m)=[x^N]\displaystyle\sum_{m=0}^{M}N! ( p^{M-m} q^m )(x)\]

となります。これは次のように計算出来ます。なお、\(N+1\) 次以上の項は答えに影響しないので、それぞれ無限和としてよく、

\[p(x)=e^x, \quad q(x)=e^x-1\]

とできることに留意してください。

\[ \begin{aligned} [x^N]\displaystyle\sum_{m=0}^{M}N! ( p^{M-m} q^m )(x) & = N![x^N]\displaystyle\sum_{m=0}^{M} ( p^M \dfrac{q^m}{p^m})(x) \\ & = N![x^N]\Big(p^M\dfrac{1-\big(\tfrac{q}{p}\big)^{M+1}}{1-\tfrac{q}{p}}\Big)(x) \\ & = N![x^N]\Big(\dfrac{p^{M+1}-q^{M+1}}{p-q}\Big)(x) \\ & = N(x) \\ & = N![x^N]\Bigg(e^{(M+1)x}-(e^x-1)^{M+1}\Bigg) \\ & = N![x^N]\Bigg(e^{(M+1)x}-\displaystyle\sum_{k=0}^{M+1}\displaystyle\binom{M+1}{k}e^{kx}(-1)^{M+1-k}\Bigg) \\ & = N!\Bigg(\dfrac{(M+1)^N}{N!}-\displaystyle\sum_{k=0}^{M+1}\displaystyle\binom{M+1}{k}(-1)^{M+1-k}\dfrac{k^N}{N!}\Bigg) \\ & = (M+1)^N-\displaystyle\sum_{k=0}^{M+1}\displaystyle\binom{M+1}{k}(-1)^{M+1-k}k^N \\ & = (M+1)^N-(M+1)!S(N,M+1) \end{aligned} \]

以上より所望の結果が得られます。