\((1,2,\cdots, N)\) の順列 \(P\) であって \(P_i > P_{i+1}\) の個数が \(K-1\) 個であるものを数える問題です。

これは Eulerian Number \(A(N,K)\) がそのまま答えになります。(Eulerian number - wikipedia)

導出

とはいっても自分は結果を最初から知っているので茶番かもしれません。

小課題 3 の解説で、 \(f(N,K)\) を \(N,K\) の場合の答えとすると、 \(n \ge 2\) のとき

\[ f(n,k)=k \times f(n-1,k) + (n -k +1) \times f(n-1,k-1)\]

という式を導出しました。多項式 \(A_n(x)\) を,

\[A_n(x):=\sum_{i = 0}^n f(n,i) x^i\]

とおくと、

\[ \begin{aligned} A_n(x) &= xA_{n-1}'(x) + (nxA_{n-1} - x^2A_{n-1}'(x))\\ &= x(1-x) A_{n-1}'(x) + nxA_{n-1}(x) \end{aligned} \]

です。ここで、\(A_{n-1}'(x) = \frac{d}{dx} A_{n-1}(x)\) を意味し、一般に多項式や形式的べき級数において

\[x \frac{d}{dx} \left(\sum_{i\ge0} a_i x^i\right) =\sum_{i\ge0} i \times a_i x^i \]

であることを使いました。 \(B_n(x) = \frac{A_n(x)}{(1-x)^{n+1}}\) とすると、

\[ \begin{aligned} B_{n-1}'(x) &= \frac{(1-x)^{n} A_{n-1}'(x) + n (1-x)^{n-1} A_{n-1}(x) }{(1-x)^{2n}}\\ &= \frac{(1-x) A_{n-1}'(x) + n A_{n-1}(x) }{(1-x)^{n+1}}\\ &= \frac{A_n(x)}{x(1-x)^{n+1}}\\ &= \frac{1}{x} B_n(x) \end{aligned} \]

より、 \(xB'_{n-1}(x) = B_n(x)\) という関係式が分かります。いま \(A_1(x) = x\) であるので、

\[B_1(x) = \frac{x}{(1-x)^2} = \sum_{i\ge 0} i x^i\]

です。これに関係式（ \(\sum a_i x^i \mapsto \sum i \times a_i x^i\) ） を \(N-1\) 回適用して

\[B_2(x) = xB_1'(x) = \sum_{i\ge 0} i^2 x^i\]

\[B_3(x) = xB_2'(x) = \sum_{i\ge 0} i^3 x^i\]

\[B_4(x) = xB_3'(x) = \sum_{i\ge 0} i^4 x^i\]

\[\vdots\]

\[B_N(x) = xB_{N-1}'(x) = \sum_{i \ge 0} i^N x^i\]

であり、

\[A_N(x) = (1-x)^{N+1} \sum_{i \ge 0} i^N x^i\]

が分かりました。これの \(x^K\) の係数（すなわち、この問題の答え）は、 \((1-x)^{N+1}\) を展開すればそのまま

\[\sum_{i=0}^{K+1} (-1)^i \binom{N+1}{i} (K+1-i)^N\]

と分かります。