上に四歩、横に四歩、対角線を越えずに進む。70 通りのうち 14 通り

中央の二項係数はすべての経路を数え、カタラン数の公式は許される経路を数えます。

統計とデータ · 難易度: 古典的な結果 · 更新日 2026-11-10

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

電卓で解いてみる

これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。

本サイトは独立した第三者のツールサイトです。Casio、Texas Instruments およびその販売代理店とは、提携・スポンサー・承認のいずれの関係もありません。機種名と製品名は各権利者の商標であり、機種を識別する目的でのみ記載しています。

本マニュアルのキー操作手順は、当サイト独自のレイアウトデータ(オンライン電卓の表示に使うものと同じデータ)と公開されている製品情報に基づいて作成しています。仕様と地域別の設定は、実機およびメーカーの最新資料で確認しています。