NF杯2024(M) - 別解（母関数を利用する）

　置換の言葉を用いて記述し，母関数で場合の数を計算できることをみる．

　$N=999$ とし，$\{ 1,\dots, N\}$ の置換の集合を $S_N$ とする．条件より，$1, \dots, n$ の数字はどれもちょうど1回ずつ書き込まれ，さらにどの行にもちょうど1回数字がちょうど表れる．

　そこで，「$i$列目 $\tau(i)$ 行目に数字 $\sigma(i)$ が書き込まれている」とする ($\sigma, \tau\in S_N$, $i=1,2,\dots, N$ )． 条件を満たすような $(\sigma,\tau)$ の個数を求めればよいが，条件は，次のように言い換えられる．

• 任意の $l=1,2,\dots,N$ に対して「$\sigma(l) \neq l$ ならば $\tau(\sigma^{-1}(l)) = l$である」が真．

$\sigma$ の固定点が $m$ 個，$\tau$ の固定点が $n$ 個であるとし($0\leq n, m \leq N$)，$\sigma$ の固定点を $p_1,\dots, p_m$ とおく．$k$ 項の攪乱順列の個数 (モンモール数) を $a_k$ とおくと，

• $\sigma$ の選び方は，固定点の選び方とそれ以外の攪乱順列による置換を考えて， ${}_N\mathrm{C}_{m}a_{N-m}$ 通り取れる．
• $\tau$ は条件より，補集合 $\{1,\dots, n \}\setminus{\{ p_1,\dots, p_m \}}$ 上で $\tau = \sigma$ と決定されるから，特にそこでは固定点が存在しない．よって，$\{ p_1,\dots, p_m\}$ 上で固定点が $n$ 個の置換となればよいから， $n\le m$ であり，${}_{m}\mathrm{C}_{n}a_{m-n}$ 通り取れる．

また，輝き度は $2^n$ である．よって，次の総和を計算すればよい． $$\sum_{0\leq n\leq m\leq N} ({}_N\mathrm{C}_{m}\cdot a_{N-m}\cdot {}_{m}\mathrm{C}_{n}\cdot a_{m-n}\cdot 2^n)$$ $n=p$, $m-n=q$, $N-m = r$ と変換すると $0\leq p,q,r\leq N$であり， $$\begin{aligned} &\sum_{0\leq n\leq m\leq N} ({}_N\mathrm{C}_{m}\cdot a_{N-m}\cdot {}_{m}\mathrm{C}_{n}\cdot a_{m-n}\cdot 2^n) \\ &= \sum_{p+q+r = N} ({}_N\mathrm{C}_{p+q}\cdot a_{r}\cdot {}_{p+q}\mathrm{C}_{p}\cdot a_{q}\cdot 2^p) \\ &= N! \sum_{p+q+r = N} \left(\frac{a_{r}}{r!}\cdot \frac{a_{q}}{q!}\cdot \frac{2^p}{p!}\right) \\ &= N![x^N] \left(\frac{e^{-x}}{1-x}\right)^2 e^{2x} \\ &= N![x^N] (1-x)^{-2} \\ &= N![x^N] (1+2x + 3x^2 + \dots + (N+1)x^N + \dots) \\ &= (N+1)! \end{aligned}$$ ただし，モンモール数の指数型母関数が $\sum_{k\geq 0} \frac{a_k}{k!} x^{k} = \frac{e^{-x}}{1-x}$ であることを用いた． 　以上より，求める答えは $$v_5(1000!) = 200 + 40 + 8 + 1 = \mathbf{249}$$