解説

方針・初手

$S$ 型移動は $1$ 回だけで、これにより $x$ 座標と $y$ 座標がともに $1$ ずつ増える。

したがって、残りの $2n-2$ 回の $N$ 型移動では、右方向への移動を $n-1$ 回、上方向への移動を $n-1$ 回行う必要がある。

$S$ 型移動が何回目にあるかを固定すれば、残りの $2n-2$ 個の位置に、右方向の $N$ 型移動を $n-1$ 個入れるだけで経路が決まる。

解法1

$N$ 型移動のうち、点 $(x,y)$ から点 $(x+1,y)$ へ進むものを $H$、点 $(x,y+1)$ へ進むものを $V$ と書く。

$S$ 型移動は点 $(x,y)$ から点 $(x+1,y+1)$ へ進むので、原点から点 $(n,n)$ に到達するには、$N$ 型移動の中に $H$ が $n-1$ 回、$V$ が $n-1$ 回含まれなければならない。

よって、$S$ 型移動の位置を決めると、残りの $2n-2$ 個の位置に $H$ を $n-1$ 個入れることで経路が一意に決まる。

まず、$A(n)$ を求める。

全体の移動回数は

$$ (2n-2)+1=2n-1

$$

である。$S$ 型移動の位置は $2n-1$ 通りあり、その位置を決めた後、残りの $2n-2$ 個の位置から $H$ の位置を $n-1$ 個選べばよい。したがって、

$$ A(n)=(2n-1){}_{2n-2}\mathrm{C}_{n-1}

$$

である。

特に $n=3$ のとき、

$$ A(3)=5{}_{4}\mathrm{C}_{2}=5\cdot 6=30

$$

である。

次に $B(n,k)$ を求める。

$S$ 型移動が $k$ 回目であると固定する。このとき、残りの $2n-2$ 回はすべて $N$ 型移動であり、その中に $H$ が $n-1$ 回、$V$ が $n-1$ 回含まれればよい。

したがって、

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$

である。これは $k$ によらない。

よって、

$$ B(4,1)={}_{6}\mathrm{C}_{3}=20

$$

であり、同様に

$$ B(4,2)={}_{6}\mathrm{C}_{3}=20

$$

である。

また、

$$ B(n,1)={}_{2n-2}\mathrm{C}_{n-1}

$$

である。

一般に、$k=2,3,\ldots,2n-1$ に対しても同じく

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$

である。

解法2

$S$ 型移動の直前の点を用いて数えてもよい。

$S$ 型移動が $k$ 回目であるとする。$S$ 型移動の前には $k-1$ 回の $N$ 型移動がある。

そのうち右方向への移動が $i$ 回であるとすると、$S$ 型移動の直前の点は

$$ (i,\ k-1-i)

$$

である。

この後、$S$ 型移動によって点

$$ (i+1,\ k-i)

$$

へ移る。

点 $(n,n)$ に到達するには、$S$ 型移動の後の $N$ 型移動で、右方向へ $n-1-i$ 回進む必要がある。$S$ 型移動の後の $N$ 型移動は

$$ 2n-1-k

$$

回であるから、この場合の経路数は

$$ {}_{k-1}\mathrm{C}_{i}{}_{2n-1-k}\mathrm{C}_{n-1-i}

$$

である。

したがって、

$$ B(n,k)=\sum_i {}_{k-1}\mathrm{C}_{i}{}_{2n-1-k}\mathrm{C}_{n-1-i}

$$

となる。ただし、二項係数が意味をもつ範囲の $i$ について和をとる。

**(i)**

$k\leqq n$ のとき

このとき $k-1\leqq n-1$ なので、与えられた公式を

$$ p=k-1,\quad q=n-1,\quad r=2n-2

$$

として用いると、

$$ \begin{aligned} \sum_{i=0}^{k-1}{}_{k-1}\mathrm{C}_{i}{}_{2n-1-k}\mathrm{C}_{n-1-i} &= {}_{2n-2}\mathrm{C}_{n-1} \end{aligned} $$

である。

よって、

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$

である。

**(ii)**

$k\geqq n$ のとき

今度は、$S$ 型移動の後の $N$ 型移動における右方向の移動回数を $j$ とする。

後半で右方向へ $j$ 回進むとき、前半では右方向へ $n-1-j$ 回進む必要がある。したがって、

$$ B(n,k)=\sum_j {}_{2n-1-k}\mathrm{C}_{j}{}_{k-1}\mathrm{C}_{n-1-j}

$$

である。

ここで

$$ p=2n-1-k,\quad q=n-1,\quad r=2n-2

$$

とすれば、$p\leqq q\leqq r$ が成り立つので、与えられた公式より

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$

である。

以上より、すべての $k=1,2,\ldots,2n-1$ に対して

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$

が成り立つ。

解説

この問題では、$S$ 型移動が一度だけ $x$ 座標と $y$ 座標を同時に $1$ ずつ増やすことが重要である。

そのため、残りの $N$ 型移動だけを見ると、結局は右方向に $n-1$ 回、上方向に $n-1$ 回進む通常の格子経路の数え上げになる。

$B(n,k)$ は一見すると $k$ に依存しそうだが、$S$ 型移動の位置を固定しても、残りの $N$ 型移動の並べ方は常に

$$ {}_{2n-2}\mathrm{C}_{n-1}

$$

通りである。ここが最も重要な点である。

答え

**(1)**

$$ A(3)=30

$$

**(2)**

$$ B(4,1)=20,\qquad B(4,2)=20

$$

**(3)**

$$ B(n,1)={}_{2n-2}\mathrm{C}_{n-1}

$$

**(4)**

$k=2,3,\ldots,2n-1$ に対して、

$$ B(n,k)={}_{2n-2}\mathrm{C}_{n-1}

$$