問題
平面上の点集合をとする．ただしは正の整数である．両端がの点であるような長さ1の線分の集合をとする．
(1) の相異なる本の元の選び方は何通りあるか．
(2) 相異なる本のの元を選ぶとき，点と点とがこれらの線分でつながる確率を求めよ．
(3) 相異なる本のの元を選ぶとき，点と点とがこれらの線分でつながる確率を求めよ．たとえば，で前図のような場合は，点と点とはつながっていると考える．
方針
長さ1の線分は格子の横辺と縦辺だけである。まず横辺 本、縦辺 本を数えて を得る。(2)では から まで、少なくとも右方向に 回、上方向に3回、合計 本の線分が必要なので、選んだ全ての線分が最短経路そのものでなければならない。(3)では 本を選ぶが、端点間の経路の長さは と同じ奇偶に限られるため、 本の経路はありえない。したがって最短経路1本に、経路外の線分を1本追加する場合を数える。
解答
(1)
長さ1の線分は、隣り合う格子点を結ぶ横または縦の線分である。
横の線分は、各 について の 本がある。したがって横の線分は 本である。
縦の線分は、各 について の3本がある。したがって縦の線分は 本である。よって である。相異なる 本を選ぶ方法は 通りである。
(2)
点 から点 までつながるには、 座標を合計 だけ増やし、 座標を合計3だけ増やす必要がある。長さ1の線分を1本通るごとに、座標は上下左右のいずれかに1だけ変わる。したがって、どのようなつながり方でも少なくとも 本の線分が必要である。
いま選ぶ線分はちょうど 本であるから、つながるためには、それら全てが から への最短経路を作っていなければならない。最短経路では右へ進む線分が 本、上へ進む線分が3本であり、その並べ方は 通りである。
全ての選び方は 通りである。よって求める確率は である。
(3)
今度は 本を選ぶ。 から までの経路の長さは、最短長 に戻り道の分だけ偶数を加えたものになる。したがって、経路の長さは の形であり、 本の経路は存在しない。
よって 本の線分を選んで2点がつながるためには、その中に から への最短経路が含まれており、残り1本はその経路に含まれない線分である必要がある。
最短経路は 通りである。1つの最短経路は 本の線分を使うので、経路外の線分は 本である。したがって有利な選び方は 通りである。
ここで重複して数えていないことを確認する。 本の中に異なる2つの最短経路が含まれるなら、2つの経路はどこかで分かれて再び合流し、その部分だけで少なくとも1つの小さな四角形を作る。その場合、2つの最短経路の和集合は最短経路より少なくとも2本多い線分を含むので、少なくとも 本必要である。よって 本の場合には最短経路はただ1つである。
全ての選び方は 通りであるから、求める確率は である。