AtCoder Regular Contest 124 F - Chance Meeting

問題

解法

雑ですが画像だけで伝わってほしい。

問題文の $H,W$ からそれぞれ $1$ ずつ引いて縦の移動回数がちょうど $H$ 回、横の移動回数がちょうど $W$ 回になるよう調整しています。

画像中の「非交差」という表現は不適切かもしれなくて、正確には「始終点以外で同じマスにいることがないようなような移動」です。

補足

$\displaystyle \sum _ {n = 0} ^ \infty \binom{2n}{n} x ^ n = \dfrac{1}{\sqrt{1 - 4x}}$ は、カタラン数の母関数 $\displaystyle \sum _ {n = 0} ^ \infty \dfrac{1}{n + 1} \binom{2n}{n} x ^ n = \dfrac{1 - \sqrt{1 - 4x}}{2x}$ を $x$ 倍して微分することで得られる。

関係無いが、ここから有名な等式 $\displaystyle \sum _ {k = 0} ^ n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4 ^ n$ が得られる (誰かがこの等式の組合せ的な解釈についてしゃべってた気がするけど忘れた)。

なお、A002420 - OEIS によると $\displaystyle\lbrack x ^ n\rbrack \sqrt{1 - 4x} = \dfrac{1}{1 - 2n}\binom{2n}{n}$ らしい。