4 × 4 の格子で、左下から右上へ上と右だけに進む経路は 8!/(4!·4!) = 70 通りです。計算機は 2 番目のリンクでそれを示します。たいていは「対角線を決して越えない」という規則を付け加え、そのとき数は 8!/(4!·5!) = 14 になります。二つの式の違いは分母の n + 1 という因数だけで、これがカタラン補正のすべてです。
許されない 56 通りはばらばらに散ってはいません。鏡映の議論により、対角線を越えることはそれらを、ずらした終点へ向かう経路と一対一に対応させ、その数は 8!/(3!·5!) = 56 です。だから 70 − 56 = 14 で、二つの画面は一致します。同じ数列 1, 2, 5, 14, 42 は、因数の列に括弧を入れる方法、凸多角形の三角形分割、正しい括弧列の数も数えます。3 番目のリンクは C₅ = 10!/(5!·6!) = 42、次の項で、七角形の三角形分割の数です。
答え
14
読み方
計算機で 8!/(4!·5!) として求めた C₄ です。2 番目のリンクは制約なしの数え上げ 8!/(4!·4!) = 70、3 番目は次のカタラン数 42 です。
出典
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。