トップ› 九州大学› 1996年› 文系第4問

九州大学 1996年文系第4問解説

方針・初手

領域 $x \geqq y$ 内を進む経路の数を求める問題である。点 $(i, j)$ へ至る直前の点は、原則として左隣の点 $(i-1, j)$ と下隣の点 $(i, j-1)$ である。領域の境界条件に注意しながら、漸化式を立てて順に求めていくのが確実なアプローチである。

解法1

原点から領域 $x \geqq y$ 内の点 $(i, j)$ に至る経路の数 $N(i, j)$ について考える。点 $(i, j)$ への直前の点は $(i-1, j)$ または $(i, j-1)$ のいずれかである。

$i > j$ のとき、直前の点 $(i-1, j)$ と $(i, j-1)$ はどちらも領域 $x \geqq y$ に含まれるため、

$$N(i, j) = N(i-1, j) + N(i, j-1)$$

が成り立つ。 $i = j$ のとき、点 $(i, i)$ への直前の点のうち、$(i-1, i)$ は条件 $x \geqq y$ を満たさず通ることができない。したがって、下隣の $(i, i-1)$ からしか到達できないため、

$$N(i, i) = N(i, i-1)$$

となる。また、任意の $i \geqq 0$ について、点 $(i, 0)$ へは $x$ 軸上を直進する1通りのみであるから、

$$N(i, 0) = 1$$

である。

(1)

上記の規則を用いて順に計算する。

$$N(1, 1) = N(1, 0) = 1$$

$$N(2, 1) = N(1, 1) + N(2, 0) = 1 + 1 = 2$$

$$N(3, 1) = N(2, 1) + N(3, 0) = 2 + 1 = 3$$

$$N(2, 2) = N(2, 1) = 2$$

$$N(3, 2) = N(2, 2) + N(3, 1) = 2 + 3 = 5$$

(2)

$n \geqq 2$ のとき、漸化式より以下が成り立つ。

$$N(n, 1) = N(n-1, 1) + N(n, 0)$$

常に $N(n, 0) = 1$ であるから、

$$N(n, 1) - N(n-1, 1) = 1$$

数列 $\{N(n, 1)\}$ は、初項 $N(1, 1) = 1$、公差 $1$ の等差数列である。したがって、

$$N(n, 1) = 1 + (n-1) \cdot 1 = n$$

これは $n=1$ のときも $N(1, 1) = 1$ となり成り立つ。

(3)

$n \geqq 3$ のとき、点 $(n, 2)$ に至る直前の点は $(n-1, 2)$ と $(n, 1)$ である。 $n \geqq 3$ であるから $n-1 \geqq 2$ となり、点 $(n-1, 2)$ も点 $(n, 1)$ も共に領域 $x \geqq y$ 内に含まれている。したがって、漸化式がそのまま適用でき、

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

と表せる。 (2) の結果より $N(n, 1) = n$ であるから、

$$N(n, 2) - N(n-1, 2) = n$$

となる。これは数列 $\{N(n, 2)\}$ の階差数列の一般項が $n$ であることを示している。 $n \geqq 3$ のとき、$N(n, 2)$ は次のように求められる。

$$N(n, 2) = N(2, 2) + \sum_{k=3}^{n} k$$

(1) より $N(2, 2) = 2$ であるから、等差数列の和の公式を用いて、

$$N(n, 2) = 2 + \frac{1}{2}(n - 3 + 1)(3 + n)$$

$$N(n, 2) = 2 + \frac{1}{2}(n - 2)(n + 3)$$

$$N(n, 2) = \frac{4 + n^2 + n - 6}{2}$$

$$N(n, 2) = \frac{n^2 + n - 2}{2}$$

因数分解して、

$$N(n, 2) = \frac{(n-1)(n+2)}{2}$$