OMC008(F)

　次の補題を示しておく．

補題：非負整数 $N$ に対し次が成り立つ． $$\sum_{n=0}^{N+1}(-1)^{N+1-n}{}_{N+1}\mathrm{C}_{n}n^{N+1}=(N+1)!$$ 証明：$N+1$ 個のボールをちょうど $N+1$ 色で塗り分ける方法は $(N+1)!$ 通りあり，一方で $N+1$ 個のボールを $n$ 色以下で塗り分ける方法は $n^{N+1}$ 通りある．これらに対し包除原理を用いれば補題の式が得られる．(証明終)

　$N=2020$ とすると，補題より与式は次のように変形できる． $$\begin{aligned} \sum_{n=0}^{N}{}_{N}\mathrm{C}_{n}(n+1)^N &=\sum_{n=0}^{N}(-1)^n{}_{N}\mathrm{C}_{n}(n+1)^N+2\sum_{\substack{0\leq n\leq N\\ n:odd}}{}_{N}\mathrm{C}_{n}(n+1)^N\\ &=\frac{(-1)^N}{N+1}\sum_{n=0}^{N+1}(-1)^{N+1-n}{}_{N+1}\mathrm{C}_{n}n^{N+1}+2^{N+1}\sum_{\substack{0\leq n\leq N\\ n:odd}}{}_{N}\mathrm{C}_{n}\Bigl(\frac{n+1}{2}\Bigr)^N\\ &=(-1)^NN!+2^{N+1}\sum_{\substack{0\leq n\leq N\\ n:odd}}{}_{N}\mathrm{C}_{n}\Bigl(\frac{n+1}{2}\Bigr)^N \end{aligned}$$ Legendreの定理より $N!=2020!$ は $2$ で $2013$ 回まで割り切れるため，上式も $2$ で $\bf{2013}$ 回まで割り切れる．