yukicoder No.758 VVVVV - ftb73’s diary

N×Nの格子点を想定する。
一番左下の格子点を(0, 0), 一番右上の格子点を(N, N)とする。
右向きの(i, j)から(i+1, j)への移動と
上向きの(i, j)から(i, j+1)への移動
のみによって、(0, 0)から(n, n)に移動する経路のうち対角線をまたがない経路数を数えたい。
とくに、上向きの移動から右向きの移動に変化する箇所(山と呼ぶことにする)がk個ある場合の経路数を数えたい。この経路数をN(n, k)と置く。

対角線をまたがないという条件を無視すれば、そのときの(0, 0)から(n, n)への経路のうち山がk個ある経路数は

${ \left( \begin{array}{c} {n-1} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }$

となる。
これは、山のx座標の選び方とy座標の選び方がそれぞれ ${ \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }$ 通りあるからである。

同様に、(0, -1) から (n, n) への経路のうち山が k 個あるのは
${ \left( \begin{array}{c} {n} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }$ 通りである。

このうち、(0, -1) → (0, 0) → (n, n) と移動し y < x なる格子点を (0, -1) 以外で通らない経路を考える。
(0, -1) → (0, 0) の経路は1通りしかないので、この経路数が求めたい値になっている。
この経路は山が k 個あることから↑→の経路の組 k 個に分解できる(谷の存在しない k 個の経路に分解できる)。
分解したそれぞれの経路について、出発点 (0, -1) に近いほうから1, 2, 3, ...,, k と番号を振る。
i 番目の経路について ${ a_i }$ = （上向きの移動回数）－（右向きの移動回数）と置く。
いま、y < x なる格子点を (0, -1) 以外で通らないという条件から、任意の m について
${ \sum_{i=1}^{m} a_i > 0 }$
が成り立つ。とくに、m = k のとき
${ \sum_{i=1}^{k} a_i = 1 }$
となり、
m = 1 のとき
${ a_1 ≧ 1 }$
となる。

(0, -1) → (0, 0) → (n, n) と移動し y < x なる格子点を (0, -1) 以外で通らない経路について、
1, 2, 3,..., k の経路を
1, 2, 3,..., ,k-2, k-1, k
2, 3, 4, ..., ,k-1, k, 1
3, 4, 5, ..., k, 1, 2
4, 5, 6, ..., 1, 2, 3
と順番に循環させたものすべての集合を考えると、それは(0, -1) から (n, n) への経路のうち山が k 個ある経路全体に等しくなることを示したい。
つまり、
${ N(n, k) = \frac{1}{k} \left( \begin{array}{c} {n} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }$
であることを示したい。

上の循環させた経路は、y - xが最小となる谷が常にk, 1の間で形成され、その谷ではy - x < 0 であることから、循環させた経路の集合に重複する経路はない。
また、任意の(0, -1) から (n, n) への経路のうち山が k 個ある経路は循環させることで、y < x なる格子点を (0, -1) 以外で通らない経路に帰着できるので上の等式が成り立つ。
（時間があるときに説明を追加する）
（Eulerian Numbers | T. Kyle Petersen | Springerに詳しく載っている。）