最短経路
さいたんけいろ 1対1で対応lattice path
名詞
式と読み方
m plus n choose m
定義
碁盤の目状の道を、遠回りせずに右と上（など決まった向き）だけに進んで A から B へ行く道順。右 m 回・上 n 回なら ₘ₊ₙCₘ 通り。
A route along a grid from one point to another that moves only right or up (in the fixed directions); with m moves right and n moves up there are C(m + n, m) of them.
例文
話し言葉 Every lattice path from A to B is just a string of 4 R's and 3 U's, so pick where the U's go. A から B への最短経路はどれも R 4 個と U 3 個の並びなので、U の位置を選べばいい。
書き言葉・答案 Find the number of lattice paths from (0, 0) to (5, 3) that pass through (2, 1). (0, 0) から (5, 3) へ行く最短経路のうち、(2, 1) を通るものの個数を求めよ。
言い間違えやすいところ
- 英語の shortest path は、用例コーパスでは MIT OCW 6.042 のグラフの最短路（グラフで 2 頂点を結ぶ最も短い道、エントリ path-in-a-graph）の意味で出てくる。学習指導要領解説（数学C）の「最短経路の探索」も離散グラフの話。碁盤の目の道順は、Levin（3.1・3.2）のように how many lattice paths from (0, 0) to (m, n) … と問う。
- 「通らない」経路は、全体から通る経路を引く（余事象）。通れない辺があるときは、その辺を通る経路を数えて引く。
根拠の件数
用例コーパスで数えた件数はありません（数えない言い方か、どの取得元にも出てこなかった言い方です）。