Catalan 数の一般化 - yoshitake-hのブログ

$m, n$ をたがいに素な自然数とする．
座標平面上を，右に1または下に1だけ移動することをくりかえして，右に $m-1$ ，下に $n$ だけ移動する経路全体の集合を $A$ とする．このうち始点と終点を結ぶ直線より右上を通らない経路は，
$\frac{1}{m}\binom{m+n-1}{n}$
通りある．

証明

$A$ に属する経路は
$\binom{m+n-1}{n}$
通りある．
経路 $a\in A$ に対し， $a$ と右に1だけ移動することを交互に無限回くりかえす経路を $f(a)$ とおく．
逆に，経路 $f(a)$ において，途中，右に1だけ移動した直後の点 $P$ に対し， $P+\mathbb{Z}\cdot (m,\,-n)$ で $f(a)$ を切ると， $A$ に属する経路（＋右に1だけ移動）が得られる．
切り方は $m$ 通りある．
$m,\,n$ がたがいに素であることより，異なる切り方に対し， $A$ に属する異なる経路が得られる．
これによって， $A$ に属する経路を $m$ 個ずつに分けることができる．
$m$ 通りの切り方のうち， $nx+my$ が最大となる点 $(x,\,y)$ で切るものがただ1つある．
この切り方は， $A$ に属する経路のうち，始点と終点を結ぶ直線より右上を通らないものにちょうど対応している．//

http://d.hatena.ne.jp/yoshitake-h/20100112