離散数学・組合せ論の問題
座標平面上で、原点 から点 まで、1 歩ごとに 軸の正の向きに 進む（右へ ）か、 軸の正の向きに 進む（上へ ）かのどちらかで進む最短経路を考える。このうち、経路上のすべての格子点 が を満たすもの（直線 より上側に一度も出ないもの）の個数を求めよ。
この問題で使うもの
- カタラン数（説明と入口の問題）
この問題を解けるようになるまで（6 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
対角線を越えない格子路の個数なので、カタラン数 （鏡像原理）を使う。ここでは 。
ヒント 2
全体の経路数 から、直線 に触れる経路の数を引く。触れる経路は、最初に触れた点までを で折り返すと から への経路に対応する。
ヒント 3
全体は 通り、悪い経路は右 回・上 回の経路で 通り。あとは引き算をする。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
方針 対角線 を越えない格子路の個数は、カタラン数 で数えられる。ここでは である。鏡像原理で式の意味を確かめながら計算する。
1. すべての最短経路の個数
右へ 回、上へ 回、合わせて 歩進む。 歩のうちどの 歩を「上」にするかを選べば経路が 1 つ決まるので、
通りある。
2. 条件を満たさない経路（悪い経路）の個数
を破る経路は、途中で必ず直線 上の点に到達する。最初に に触れた点までの部分を直線 に関して折り返すと、始点 は に移る。こうして、悪い経路と「 から への最短経路」とが 1 対 1 に対応する（後者はかならず をまたぐので、最初に触れた点で折り返せば元に戻せる）。
から へは右へ 回、上へ 回の計 歩なので、その個数は
である。
3. 求める個数
これは と一致する。
よって答えは である。
別解
これは条件 を満たす格子路の数え上げで、カタラン数 に等しい。
反射原理で確かめる。原点から までの最短経路の総数は である。
直線 に一度でも触れる経路は、最初に触れた点以降を直線 で反射すると、 の反射点 への経路と一対一に対応する。その個数は である。
よって求める個数は となる。
検算: であり、一致する。