離散数学・組合せ論の問題

方針：すべての最短経路の数から、条件 $y\le x$ を破る経路の数を引く。破る経路の数は鏡像原理で数える。

1. 最短経路全体の数

$(0,0)$ から $(5,5)$ への最短経路は、右への 1 歩（R）5 個と上への 1 歩（U）5 個を 1 列に並べたものと 1 対 1 に対応する。10 歩のうちどの 5 歩を R にするかを選べばよいので
$$\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252\text{通り}.$$

2. 条件を破る経路の数（鏡像原理）

条件 $y\le x$ を破る経路は、$y=x+1$ を満たす点（直線 $y=x+1$ 上の格子点）を少なくとも 1 回通る。そのような経路について、最初に直線 $y=x+1$ に触れた点までの部分を直線 $y=x+1$ に関して折り返す。このとき、始点 $(0,0)$ は $(-1,1)$ に移り、残りの部分はそのまま残すので、$(-1,1)$ から $(5,5)$ への最短経路が 1 本得られる。

逆に、$(-1,1)$ から $(5,5)$ への最短経路は、$(-1,1)$ が直線 $y=x+1$ の上にあり $(5,5)$ が下側にあるので、必ず直線 $y=x+1$ 上の点を通る。最初に通った点までを再び折り返すと、$(0,0)$ から $(5,5)$ への条件を破る経路に戻る。したがって両者は 1 対 1 に対応する。

$(-1,1)$ から $(5,5)$ へは右に $6$ 歩、上に $4$ 歩進むので、その最短経路の数は
$$\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210\text{通り}.$$

3. 求める数
$$\left(\genfrac{}{}{0ex}{}{10}{5}\right)-\left(\genfrac{}{}{0ex}{}{10}{4}\right)=252-210=42.$$

これはカタラン数 $C_5=\frac{1}{5+1}\left(\genfrac{}{}{0ex}{}{10}{5}\right)=\frac{252}{6}=42$ と一致する。

よって答えは $42$ 通り。

条件 $y\le x$ を常に満たす格子経路は、(0,0) から (n,n) までのディック経路に対応し、その数はカタラン数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ で与えられる。

$n=5$ のとき $C_5=\frac{1}{6}\left(\genfrac{}{}{0ex}{}{10}{5}\right)=\frac{252}{6}=42$。

検算（反射法）：全経路 $\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252$ 通り。直線 $y=x+1$ に触れる経路は、最初に触れた点以降を反射させると (0,0) から (4,6) への経路と一対一に対応する。その数は $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$ 通り。よって $252-210=42$ 通り。

また、カタラン数の漸化式 $C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5={\sum }_{k=0}^4{C}_k{C}_{4-k}=14+5+4+5+14=42$ でも一致する。