131104 初版 131104 更新
この式が出る理由は極めて簡明で,
P から Q に至る最短経路は,
A1 - B1 から A7 - B7 までの黄色の橋を通らなくてはならない。
それは1つではないが,最初にとおる橋で経路を分類することができる。
最初
という語はカタラン数との結びつけている。
A3 - B3 をとおる経路と,A5 - B5 をとおる経路は
共通部分がある。
だが,
最初
という語をつけると,
共通部分はない。
さりげない語だが,
場合の数では重複なく数える際に鍵になる語である。
例えば,最初に A3 - B3 をとおる最短経路は,
すべての経路のうちの 5 × 11C4 である。
ただしこの中には, A5 - B5 をとおるものも含まれている。