AtCoder Regular Contest 143 の B 問題で出会った面白い等式

問題はこちら。 atcoder.jp

概要としてはこんな感じ。

 1 以上  N^{2} 以下の自然数を、 N \times N のマス目に1つずつ書く。
 i j 列の値を  a_{i,j} と表すとき、すべての  a_{i, j} が以下を満たすような書き込み方が何通りあるか答えよ。

 \exists j' \in \{1, 2, \dots, N \}, a_{i, j'} \gt a_{i, j} または  \exists i' \in \{1, 2, \dots, N \}, a_{i', j} \lt a_{i, j}

制約は  1 \leq N \leq 500 です。
大きい数になるので、 998244353 で割ったものを出力してください。

本問題の解答については公式解説にゆずるとして、
この問題では、部分問題として、逆に条件を満たさないような  a_{i, j} が1つ存在する場合の、 i 行と  j 列に書き込む数の組み合わせを求める問題を解くことになります。

解説では以下の式で計算しています。
 \ _{n^{2}}C_{2n-1} \times (n-1)! \times (n-1)!

お気持ちとしてはこんな感じ。

  1. とりあえず、 1 以上  N^{2} 以下の自然数 2n-1 個集めてきて
  2. 下位  n-1 個、真ん中  1 個、上位  n-1 個の3グループにわけ、
  3. 真ん中を  a_{i, j} とし、上位を  i 行、下位を  j 列に書き込む。

一方、私がコンテスト中に立てた式はこんな感じ。
 \displaystyle{\sum_{k=n}^{n^{2}-n+1}  \ _{k-1}P_{n-1} \times \ _{n^{2} - k}P_{n-1}}

お気持ちとしてはこう。

  1. とりあえず  a_{i, j} = k とおく。
  2.  a_{i, j} 未満の数字は、 k-1 個あるので  j 列をそれで埋める。
  3. 同様に a_{i, j} より大きい数字は、 n^{2} - k 個あるので  i 行をそれで埋める。
  4.  k n から  n^{2} - n + 1 まで動かす。※  \ _{n}P_{k} n \geq k を満たすため

計算量のオーダーは変わりませんが、定数項は解説の解き方の方が有利です。

当記事の趣旨としては、
 \ _{n^{2}}C_{2n-1} \times (n-1)! \times (n-1)! = \displaystyle{\sum_{k=n}^{n^{2}-n+1}  \ _{k-1}P_{n-1} \times \ _{n^{2} - k}P_{n-1}}
が成り立つことの証明です。

とりあえず、辺々  (n-1)! \times (n-1)! で割っておきます。
 \ _{n^{2}}C_{2n-1} = \displaystyle{\sum_{k=n}^{n^{2}-n+1}  \ _{k-1}C_{n-1} \times \ _{n^{2} - k}C_{n-1}}
以下、これを示します。

 \ _{n}C_{m} については以下の有名な式が成り立ちます。
 \ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-1}C_{m} \quad (n, m \geq 1)
証明としてはこんな感じ。
 \ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-1}C_{m}
 \quad = \frac{(n-1)!}{(n-m)!(m-1)!} + \frac{(n-1)!}{(n-m-1)!(m)!}
 \quad = \frac{1}{n-m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!} + \frac{1}{m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}
 \quad = \frac{1}{n-m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!} + \frac{1}{m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}
 \quad = \frac{n}{(n-m) \times m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}
 \quad = \frac{n!}{(n-m)!(m)!}

さらに、ここから以下が成り立ちます。
 \ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-2}C_{m-1} + \dots + \ _{m-1}C_{m-1}
ただし  n \lt m のとき  \ _{n}C_{m} = 0 としています。

ここで、
 \ _{n}C_{m} = \displaystyle{\sum_{j=0}^{n-m}  x_{i, j} \times \ _{n-i-j}C_{m-i}}
を満たす  x_{i, j} を考えます。 1 \leq i \leq m, 0 \leq j \leq n-m です。
また、実際にこれを満たすような  x_{i, j} が存在することは、先の等式から帰納的に証明されます。

 \ _{n}C_{m} に関する等式から、 x_{i, j} には以下の漸化式が成り立ちます。  x_{i+1, j} = x_{i, j} + x_{i, j-1} + \dots + x_{i, 0} = x_{i, j} + x_{i+1, j-1}
文字を置き換えて
 x_{i, j} =  x_{i-1, j} + x_{i, j-1}
すこし乱暴ですが、この漸化式と  x_{1, 0} = x_{1, 1} = \dots = x_{1, n-m} = 1より
 x_{i, j} =  \ _{i+j-1}C_{j} =  \ _{i+j-1}C_{i-1}
が成り立ちます。

よって、
 \ _{n}C_{m} = \displaystyle{\sum_{j=0}^{n-m}   \ _{i+j-1}C_{i-1} \times \ _{n-i-j}C_{m-i}}
となります。

この等式の、

  •  n n^{2}
  •  m 2n-1
  •  i n
  •  j k - n

置き換えると  \ _{n^{2}}C_{2n-1} = \displaystyle{\sum_{k=n}^{n^{2}-n+1}  \ _{k-1}C_{n-1} \times \ _{n^{2} - k}C_{n-1}} を得ることができました。