問題
平面上の点の座標と座標がどちらも整数であるとき，その点を格子点という．与えられた格子点を第1番目とし，この点から右斜めまたは右斜めの方向にもっとも近い第2番目の格子点をとり，この2点を線分で結ぶ．同様にして第2番目の格子点から第3番目の格子点をとり，第2番目と第3番目を線分で結ぶ．以下これを有限回繰り返し，こうしてできる線分をつないだものを折れ線グラフということにする．上図に原点と格子点を結ぶ折れ線グラフの例を示す．次の問いに答えよ．
(1) は正の整数，はなる整数とする．原点と格子点を結ぶ折れ線グラフが存在するための必要十分条件はが偶数であることを示せ．また，この必要十分条件がみたされているとき，原点と格子点を結ぶ折れ線グラフの数を求めよ．
(2) は2以上の整数，はなる整数で，は偶数とする．原点と格子点を結ぶ折れ線グラフであって格子点，，，の少なくとも1つを通る折れ線グラフの数は，原点と格子点を結ぶ折れ線グラフの数の2倍に等しいことを示せ．
(3) コインを9回投げる．1回から回までの試行において，表の出た回数から裏の出た回数を引いた数をで表す．このとき各格子点，，を順番に線分でつなげば折れ線グラフが得られる．ただし，とする．が起きたとき，どの も3にならない条件つき確率を求めよ．
方針
各ステップは を1増やし を または 変えるので、上向きの回数を数えれば(1)は二項係数になる。(2)は、全経路から「最後まで高さ に初めて到達する経路」を引く。後者は最後の1歩の前まで高さ 未満にある経路で、反射の対応により2つの二項係数の差で数える。(3)は を終点 と見る条件付き確率に直し、(2)を直接使う。
解答
(1)
原点から へ進む折れ線グラフを考える。各ステップでは 座標が1増え、 座標は または だけ変化する。
上向きのステップ数を 、下向きのステップ数を とすると である。したがって となる。これらが整数でなければならないので、必要十分条件は である。
この条件が成り立つとき、 回のうち上向きに進む 回を選べばよいから、折れ線グラフの数は である。
(2)
(1)より、原点から へ行く折れ線グラフ全体の数は である。
求めるものは、このうち途中で高さ の格子点 の少なくとも1つを通るものの数である。 は偶数なので、 のとき高さ にはなれない。したがって、これは「終点 より前に一度は高さ に達するもの」と同じである。
そこで、終点で初めて高さ に達する折れ線グラフの数を数える。最後の1歩は から への上向きの1歩である。よって、その直前までは原点から へ行き、途中で高さ に達しない折れ線グラフである。
原点から へ行く全体の数は である。このうち途中で高さ に達するものは、初めて高さ に達した後の部分を直線 に関して反射すると、原点から へ行く折れ線グラフと1対1に対応する。したがってその数は である。
よって、終点で初めて高さ に達するものの数は である。したがって、求める数は
である。 を用いると
となる。
一方、原点から へ行く折れ線グラフの数は である。したがって求める数は、その2倍に等しい。
(3)
であることは、折れ線グラフが原点から へ行くことに対応する。この全体の数は である。
条件「どの も3にならない」は、終点より前に高さ3の格子点を通らないということである。なお、 では偶奇が合わないため は起こらない。
(2)を 、 に適用すると、終点より前に高さ3に達する折れ線グラフの数は、原点から へ行く折れ線グラフの数の2倍である。これは である。
したがって、終点まで高さ3に達しないものの数は である。求める条件つき確率は である。