(cache)グリッドの最短経路の数え上げまとめ

グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます．よくある書き込み(動的計画法)による解法は扱いません．

最短経路の数え上げとは

最短経路の数え上げは，以下のようなグリッド上で左下から右上への最短経路(North-East lattice path)の数を数え上げる問題です．最短経路の例として以下の赤，青の経路があります．

一般的な最短経路

例として，以下の縦

4

区画，横

6

区画のグリッド上の最短経路を考えます．

どの最短経路でも上方向に $4$ 回，右方向に $6$ 回移動する必要があります．最短経路の数は「 $↑$ 」 $4$ つ，「 $\to$ 」 $6$ つを並べる方法の数に等しいです．例えば上の赤の経路は $(\to, ↑, \to, \to, ↑, \to, ↑, \to, \to, ↑)$ に対応しています．これは同じものを含む順列の数え上げに等しく， $(\binom{10}{4}) = 210$ が答えとなります．ここで， $(\binom{n}{r})$ とは $\frac{n!}{r! (n - r)!}$ のことです．

ある点を通る最短経路

グリッド上の最短経路のうち，ある点

P

を通るようなものの数は，(左下から点

P

までの最短経路の数)×(点

P

から右上までの最短経路の数)となります．

例えば以下のグリッドの左下から右上への最短経路のうち，赤の点を通るよううなものの数は， $(\binom{6}{3}) (\binom{4}{1}) = 80$ です．

点 $P$ が辺上にあっても数え方は同じで，その辺の両端の点を通るような経路の数を数えればよいです．以下の例で赤の点を通るような物の数は， $(\binom{5}{2}) (\binom{4}{2}) = 60$ です．

ある点を通らない最短経路

全体の経路の数からある点を通る最短経路の数を引けばよい．

通ってはいけない点が複数ある場合

ある長方形領域を通らない最短経路

以下のようにグリッド上に左上から右下にかけてのオレンジの破線上の点を考えます．このグリッド上の左下から右上への最短経路は必ずオレンジの点を通ります．さらに，異なる2つのオレンジの点を通る最短経路は存在しないため，各オレンジの点を通る最短経路数の総和は，全体の最短経路数と一致します．

以下のようなグリッド上の長方形領域が通れないときの最短経路を数えます．先ほどのように直線を引き，その直線上の各点を通る最短経路数を足せばよいです．

また，このままでは上から2番目のオレンジの点は数えにくいので以下のように直線をずらしてみます．

「異なる2つのオレンジの点を通る最短経路は存在しない」，「各点を通る最短経路数の総和は，全体の最短経路数と一致する」を満たすため，このように変形しても問題ないです．

この場合の最短経路数は $(\binom{4}{4}) (\binom{6}{0}) + (\binom{4}{3}) (\binom{6}{1}) + (\binom{5}{1}) (\binom{5}{3}) + (\binom{5}{0}) (\binom{5}{4}) = 80$ となります．

一般に，長方形領域が通れない場合，その長方形の頂点から引いた直線を引くとこのように求めることができます．

ある直線を跨がない最短経路

傾き1の直線を跨がない最短経路(直線1本)

以下のようなグリッド上の直線を跨がない(直線上の点は通ってもよい)最短経路の数を数えます．

この直線を跨がないということは以下の灰色の直線上の点を通らないということになります．

このグリッドをこの通ってはいけない灰色の直線で折り返すと以下のようになります．数えたいものは黒点から赤点まで灰色の点を通らずに行く最短経路数です．これは「黒点から赤点までの最短経路数」から「黒点から赤点までで灰色の点を通るような最短経路数」を引けば良いです．ここで，「黒点から赤点までで灰色の点を通るような最短経路数」というのは「黒点から青点までの最短経路数」と等しいです．なぜならば，「黒点から青点までの最短経路」は必ず1度は灰色の点を通り，そのうち初めに通った灰色の点以降の経路を直線で折り返すと「黒点から赤点までで灰色の点を通るような最短経路」と1対1対応するからです．

例えば以下の赤の経路と青の経路が対応します．

この場合の最短経路数は $(\binom{10}{4}) - (\binom{10}{2}) = 165$ となります．

一般に，縦 $N$ 区画，横 $M$ 区画のグリッドの上から $K$ 区画にかけて以下のように直線がある場合，その直線上の点を跨がない最短経路の数は，

(\binom{N + M}{N}) - (\binom{N + M}{K - 1})

となります．

特に， $M = N, K = N$ の場合，この値はカタラン数と呼ばれ，

C_{N} = (\binom{2 N}{N}) - (\binom{2 N}{N - 1}) = \frac{1}{N + 1} (\binom{2 N}{N})

と表されます．

傾き1の直線を跨がない最短経路(直線2本)

下図のように複数の直線があっても複数回折り返すことで同じように解くことができます．

(黒 $\to$ 赤) $-$ (黒 $\to$ 青) $-$ (黒 $\to$ 黄) $+$ (黒 $\to$ 緑)が答えとなります．ただし，直線の位置によっては多くの回数折り返す必要がある場合があります．

一般に，縦 $N$ 区画，横 $M$ 区画のグリッドの上から $K$ 区画，下から $L$ 区画にかけて以下のように直線がある場合，その直線を跨がない最短経路の数は， $P = N + M - K - L + 2$ として，

\sum_{k \in Z} (\binom{N + M}{N + k P}) - (\binom{N + M}{K - 1 + k P})

となります．

傾き1の2本の直線の間を通る最短経路

s \leq t

を整数として，直線

y = x + s

と

y = x + t

の間を通る(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で

(a, b)

から

(c, d)

に移動する経路数は

\sum_{k \in Z} ((\binom{c + d - a - b}{c - a - k (t - s + 2)}) - (\binom{c + d - a - b}{c - b - k (t - s + 2) + t + 1}))

となることが知られています．*1
傾き1の直線を通らない最短経路(直線2本)はこれの特殊な例となっています．

傾き1/μの直線を跨がない最短経路

μ

を正負整数として，直線

y = \frac{1}{μ} x

を跨がない(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で

(a, b)

から

(c, d)

に移動する経路数は

(\binom{c + d - a - b}{c - a}) - \sum_{i = ⌊ a / μ ⌋ + 1}^{d} (\binom{i (μ + 1) - a - b - 1}{i - b}) \frac{c - μ d + 1}{c + d - i (μ + 1) + 1} (\binom{c + d - i (μ + 1) + 1}{d - i})

もしくは

\sum_{i = 0}^{⌊ a / μ ⌋ - b} (- 1)^{i} (\binom{a - μ (b + i)}{i}) \times \frac{c - μ d + 1}{c + d - (μ + 1) (b + i) + 1} (\binom{c + d - (μ + 1) (b + i) + 1}{d - b - i})

となることが知られています．*2

特に， $(a, b) = (0, 0)$ のとき，

\frac{c - μ d + 1}{c + d + 1} (\binom{c + d + 1}{d})

となります．

傾きq/pの直線を跨がない最短経路

p, q

を互いに素な正整数として，直線

y = \frac{q}{p} x

を跨がない(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で

(0, 0)

から

(p, q)

に移動する経路数は

\frac{1}{p + q} (\binom{p + q}{p})

となることが知られています．*3

$p = n, q = n + 1$ とすることで，カタラン数になることも確認できます．

また，この直線より上側にある「経路上の格子点」の数が $K$ 個( $0 \leq K < p + q$ )であるような経路数も同様に

\frac{1}{p + q} (\binom{p + q}{p})

となります( $K$ の値によらない)．より一般的な場合も計算できますが，効率的な計算方法は分かっていないようです．*4

対角線上を $K$ 回通る最短経路

縦横

N

区画のグリッドの左下から右上への最短経路のうち，グリッドの対角線上の(始点と終点を除く)点ををちょうど

K

回通るものの数を数えます．例えば以下の最短経路は対角線上の点を

3

回通っています．

対角線上の点のうち通るものを決めると，点と点の間は「対角線上の(始点と終点を除く)点を通らない最短経路数を求めよ．」という複数の部分問題に分割できます．下図のうち，オレンジの点が通る点，青の枠が部分問題になっています．

「縦横 $t$ 区画のグリッドの左下から右上への最短経路のうち，グリッドの対角線上の(始点と終点を除く)点を通らないものの数を求めよ．」という部分問題の解を求めます．これは簡単で，下図において，左下の赤(青)点から右上の赤(青)点まで対角線(オレンジ)を通らない最短経路の数を求めればよいです．ある直線を跨がない最短経路で紹介したカタラン数を用いて $2 C_{t - 1}$ と表すことができます．

あとは，サイズの和が $N$ になるような部分問題の積の和を求めればよいです(畳み込み)．

$\sum_{t_{1} + t_{2} + \dots + t_{K + 1} = N} (2 C_{t_{1} - 1}) (2 C_{t_{2} - 1}) \dots (2 C_{t_{K + 1} - 1}) = 2^{K + 1} \sum_{t_{1} + t_{2} + \dots + t_{K + 1} = N} C_{t_{1} - 1} C_{t_{2} - 1} \dots C_{t_{K + 1} - 1}$

$\sum_{t_{1} + t_{2} + \dots + t_{K + 1} = N} C_{t_{1} - 1} C_{t_{2} - 1} \dots C_{t_{K + 1} - 1}$ はカタラン数の畳み込みになっていて，この値は

(\binom{2 N - K - 2}{N - 1}) - (\binom{2 N - K - 2}{N}) = \frac{K + 1}{2 N - K - 1} (\binom{2 N - K - 1}{N})

であることが知られています．*5 *6

したがって， $\frac{2^{K + 1} (K + 1)}{2 N - K - 1} (\binom{2 N - K - 1}{N})$ となります．

対角線の下側しか通れないという制約が付いても，部分問題の解が $C_{t - 1}$ となるだけなので $\frac{K + 1}{2 N - K - 1} (\binom{2 N - K - 1}{N})$ です．

この制約が付いた数え上げ問題ははカタラン数の畳み込みに帰着させる方法の他にも，下図のある直線を跨がない最短経路と一対一の対応をさせることでも求めることができます．ただし，「ある直線を跨がない最短経路」で説明したような直感的で簡潔な証明が分からないので省略します．

$K$ 回曲がる最短経路

右折が $K$ 回ある最短経路

下図のような縦

N

区画，横

M

区画のグリッドの最短経路のうち，右折(

↑\to

)の数を数えます．例えば以下の例では

N = 4, M = 6

で右折回数は3回となります。

右折する地点を以下の青の点から $K = 3$ 個選べば最短経路が一意に定まります．ただし， $K$ 点は左下から右上に並ぶように選ぶ必要があります(縦横に同じ列に2点や，点の左上の領域に点が存在してはいけません)．

これは，下図の左の矢印から $K$ 個，下の矢印から $K$ 個選ぶことによって条件を満たす点を選ぶことができます．

例えば，最初の例に示した最短経路を選ぶ方法は下図のようになります．

したがって，このような経路数は $(\binom{N}{K}) (\binom{M}{K})$ となります．

形式的冪級数による解釈

最初に右に0回以上進み，右折を

K

回行って，最後に上に0回以上進む．

f = (x + x^{2} + x^{3} + \dots) (y + y^{2} + y^{3} + \dots)

f_{x} = (1 + x + x^{2} + x^{3} + \dots)

f_{y} = (1 + y + y^{2} + y^{3} + \dots)

としたときの

[x^{N} y^{M}] f_{x} f^{K} f_{y}

が求める値．

\frac{1}{(1 - x)^{K + 1}} = \sum_{0 \leq i} (\binom{K + i}{K}) x^{i}

なので

(\binom{N}{K}) (\binom{M}{K})

となる．

右左折が $K$ 回ある最短経路

右折(

↑\to

)と左折(

\to↑

)両方の数の和が

K

となる最短経路の数を数えます．例えば以下の例では

K = 5

です．

まず，始点から最初に上(

↑

)か右(

\to

)どちらに進むかで別々に考えます．上に進む場合を考えると，右折回数は

⌈ \frac{K}{2} ⌉

回，左折回数は

⌊ \frac{K}{2} ⌋

回となります．最後の右折(左折)を無視する(

K

によって最後どの列で右折(左折)するかは決まっているため)と，下図の左の矢印から右折する列を

⌈ \frac{K - 1}{2} ⌉

個，下の矢印から左折する列を

⌊ \frac{K - 1}{2} ⌋

個選ぶと最短経路が一意に定まります．

例えば，最初の例に示した最短経路を選ぶ方法は下図のようになります．

したがって，経路数は $(\binom{N - 1}{⌊ \frac{K - 1}{2} ⌋}) (\binom{M - 1}{⌈ \frac{K - 1}{2} ⌉}) + (\binom{N - 1}{⌈ \frac{K - 1}{2} ⌉}) (\binom{M - 1}{⌊ \frac{K - 1}{2} ⌋})$ となります．

形式的冪級数による解釈

最初に右に進む場合，右に1回以上進むのを

⌈ \frac{K + 1}{2} ⌉

回，上に1回以上進むのを

⌊ \frac{K + 1}{2} ⌋

回交互に繰り返すことになると考えると，右折がK回ある最短経路と同様に求めることができる．

左折が $K$ 回ある対角線を跨がない最短経路

縦横

N

区画のグリッド上の対角線を跨がない(下側のみを通る)最短経路のうち，左折(

\to↑

)を

K

回行うものの数を数えます．

下図は $N = 6, K = 3$ の経路の例です．

ここで，下図のように右へ進む場合と上へ進む場合を色分けして同じ色が連続している数を書いてみます．

右へ連続して進む区間と上へ連続して進む区間が交互に $K$ 回ずつ出現することがわかります． $i$ 番目に出現する「右へ連続して進む区間」の右に進む回数を $a_{i}$ とします．上へ進む場合も同様にして数列 $b$ を定義します．
上図の例だと $a = {2, 2, 2}, b = {1, 3, 2}$ となります．

整数列 $a, b$ の条件は

$\sum_{i = 1}^{K} a_{i} = \sum_{i = 1}^{K} b_{i} = N$
$a_{i}, b_{i} \geq 1$
$\sum_{i = 1}^{j} b_{i} \leq \sum_{i = 1}^{j} a_{i} (j = 1, 2, \dots, K)$

となりますが，3番目の条件は無視すると数列 $a, b$ は，縦 $N - K$ 区画，横 $K - 1$ 区画のグリッドの最短経路と対応が取れます．
具体的には，先ほどの $a = 2, 2, 2, b = 1, 3, 2$ は以下の最短経路と対応が取れます．縦に $K$ 本の経路がありますが，右から $i$ 番目の経路では上へ $a_{i} - 1$ 回進んでいます．
右側の数列 $b$ の例では，まず $b_{1} - 1 = 0$ 回上へ進んで右へ $1$ 回進み， $b_{2} - 1 = 2$ 回上へ進んで右へ $1$ 回進み， $b_{3} - 1 = 1$ 回上へ進んでいます．

ここで3番目の条件 $\sum_{i = 1}^{j} b_{i} \leq \sum_{i = 1}^{j} a_{i} (j = 1, 2, \dots, K)$ を考えると，このグリッドの経路上において数列 $b$ を表す最短経路が数列 $a$ を表す最短経路の上に来ないことが条件であることがわかります．

これで交差しない最短経路の組で扱う問題と同じになったためLGV公式を用いて求めると $\frac{1}{N} (\binom{N}{K}) (\binom{N}{K - 1})$ となります．これはNarayana数として知られています．

左折が $K$ 回ある直線を跨がない最短経路

より一般に，以下のように縦

N

区画，横

M

区画のグリッドの上から

L

区画にかけて下図のように直線がある場合，その直線を跨がない最短経路のうち，左折(

\to↑

)が

K

回あるようなものの数を数えます．

左折がK回ある対角線を跨がない最短経路では，最初に右，最後に上に進むしかないため考えやすくなっていましたが，今回はそうではありません．

そこで，簡単に考えるために最初は右( $\to$ )に，最後は上( $↑$ )に進む場合の経路数 $f_{\to↑} (N, M, L, K)$ を数えます．
左折がK回ある対角線を跨がない最短経路と同様に考えると，以下の数列に対応付けられます．

$\sum_{i = 1}^{K} a_{i} = M$
$\sum_{i = 1}^{K} b_{i} = N$
$a_{i}, b_{i} \geq 1$
$\sum_{i = 1}^{j} b_{i} \leq \sum_{i = 1}^{j} a_{i} + N - L (j = 1, 2, \dots, K)$

これは，下図のグリッド上の同色点間の最短経路の組であって，青点間の最短経路が赤点間の最短経路の上に来ないようなものの数となります．

LGV公式を用いると，

$f_{\to↑} (N, M, L, K) = (\binom{N - 1}{K - 1}) (\binom{M - 1}{K - 1}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 2})$

となります(ただし， $L \leq N, M$ )．

次に，最初は右( $\to$ )，最後は右( $\to$ )に進む場合の経路数 $f_{\to\to} (N, M, L, K)$ を数えます．

終点まで進んだ後に上に $1$ 移動することにすると下図のグリッド上で「最初は右( $\to$ )に，最後は上( $↑$ )に進む場合の経路」として数えることができます(最後の $\to↑$ により $K$ が $1$ 増えることに注意)．

ただし，このままでは下図のような経路も含まれてしまうのでこれらを引く必要があります．

$f_{\to\to} (N, M, L, K) = f_{\to↑} (N + 1, M, L + 1, K + 1) - f_{\to↑} (N, M, L, K + 1)$
$= (\binom{N - 1}{K - 1}) (\binom{M - 1}{K}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 1})$

$f_{↑↑} (N, M, L, K)$ は $f_{\to\to} (M, N, L, K)$ であるので，

$f_{↑↑} (N, M, L, K) = (\binom{N - 1}{K}) (\binom{M - 1}{K - 1}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 1})$

$f_{↑\to} (N, M, L, K)$ を求めます．下図は最初は上に $a$ 進み，最後は右に $b$ 進んだ場合の経路を表しています．

最初の $a$ ステップと最後の $b$ ステップを除くと $f_{\to↑} (N - a, M - b, L, K)$ となります．

$f_{↑↑} (N, M, L, K) = \sum_{a = L}^{N - 1} \sum_{b = L}^{M - 1} f_{\to↑} (a, b, L, K)$
$= (\binom{N - 1}{K}) (\binom{M - 1}{K}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K})$

これまでの結果をまとめると以下のようになります．

$f_{\to↑} (N, M, L, K) = (\binom{N - 1}{K - 1}) (\binom{M - 1}{K - 1}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 2})$
$f_{\to\to} (N, M, L, K) = (\binom{N - 1}{K - 1}) (\binom{M - 1}{K}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 1})$
$f_{↑↑} (N, M, L, K) = (\binom{N - 1}{K}) (\binom{M - 1}{K - 1}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K - 1})$
$f_{↑\to} (N, M, L, K) = (\binom{N - 1}{K}) (\binom{M - 1}{K}) - (\binom{L - 1}{K}) (\binom{N + M - L - 1}{K})$

したがって，求める最短経路数はこれらの和なので，

$(\binom{N}{K}) (\binom{M}{K}) - (\binom{L - 1}{K}) (\binom{N + M - L + 1}{K})$

となります．

右折が $K$ 回ある直線を跨がない最短経路

同様に右折が

K

回ある場合も考えてみます．

最初が右( $\to$ )，最後が上( $↑$ )となる最短経路において，右折回数を $K$ とすると左折回数は $K + 1$ となります．

最初が右( $\to$ )，最後が右( $\to$ )となる最短経路において，右折回数を $K$ とすると左折回数は $K$ となります．

最初が上( $↑$ )，最後が上( $↑$ )となる最短経路において，右折回数を $K$ とすると左折回数は $K$ となります．

最初が上( $↑$ )，最後が右( $\to$ )となる最短経路において，右折回数を $K$ とすると左折回数は $K - 1$ となります．

以上から，

$f_{\to↑} (N, M, L, K + 1) + f_{\to\to} (N, M, L, K) + f_{↑↑} (N, M, L, K) + f_{↑\to} (N, M, L, K - 1)$
$= (\binom{N}{K}) (\binom{M}{K}) - (\binom{L + 1}{K + 1}) (\binom{N + M - L - 1}{K - 1})$

となります．

右左折が $K$ 回ある直線を跨がない最短経路

同様に右左折が

K

回ある場合も考えてみます．

最初が右( $\to$ )，最後が上( $↑$ )となる最短経路において，右左折回数を $K$ とすると左折回数は $\frac{K + 1}{2}$ となります．( $K$ は奇数)

最初が上( $↑$ )，最後が右( $\to$ )となる最短経路において，右左折回数を $K$ とすると左折回数は $\frac{K - 1}{2}$ となります．( $K$ は奇数)

最初が右( $\to$ )，最後が右( $\to$ )となる最短経路において，右左折回数を $K$ とすると左折回数は $\frac{K}{2}$ となります．( $K$ は偶数)

最初が上( $↑$ )，最後が上( $↑$ )となる最短経路において，右左折回数を $K$ とすると左折回数は $\frac{K}{2}$ となります．( $K$ は偶数)

以上から，

${\begin{cases} (\binom{N - 1}{\frac{K}{2}}) (\binom{M - 1}{\frac{K}{2} - 1}) + (\binom{N - 1}{\frac{K}{2} - 1}) (\binom{M - 1}{\frac{K}{2}}) - 2 (\binom{L - 1}{\frac{K}{2}}) (\binom{N + M - L - 1}{\frac{K}{2} - 1}) & (K \equiv 0 (\mod 2)) \\ 2 (\binom{N - 1}{\frac{K - 1}{2}}) (\binom{M - 1}{\frac{K - 1}{2}}) - (\binom{L - 1}{\frac{K - 1}{2}}) (\binom{N + M - L - 1}{\frac{K - 1}{2}}) - (\binom{L - 1}{\frac{K - 1}{2} + 1}) (\binom{N + M - L - 1}{\frac{K - 1}{2} - 1}) & (K \equiv 1 (\mod 2)) \end{cases}$

複数の最短経路数の和

複数の点間の最短経路数の和は一つずつ求めずとも簡単に求まる場合があります．ここでは，そのような例について見ていきます．

対角線上の点までの最短経路

下図のような縦横

N

区画のグリッドがあり，左下の点(黒)から対角線上の各点(オレンジ)までの最短経路数の総和を求めます．下図は

N = 6

の例です．

この例では，最短経路数は左上の点から順に $(\binom{6}{0}), (\binom{6}{1}), (\binom{6}{2}), (\binom{6}{3}), (\binom{6}{4}), (\binom{6}{5}), (\binom{6}{6})$ なので答えは $64$ です．

一般に，二項定理より $(1 + 1)^{N} = \sum_{i = 0}^{N} (\binom{N}{i})$ であるので，総和は $2^{N}$ になります．

傾き-q/pの直線上の点までの最短経路

さらに一般化して，左下を原点，右を $x$ 軸正の方向，上を $y$ 軸正の方向とする平面の $y = - \frac{q}{p} x + N$ ( $p, q$ は互いに素)の直線上にある格子点までの最短経路数の総和を求めます．

下の図は $N = 5, p = 2, q = 3$ の例です．

結論のみ書きますが，形式的冪級数を用いて、

[x^{N}] \frac{(1 - x)^{p - 1}}{(1 - x)^{p} - x^{q}}

となります． $N = 6, p = 1, q = 1$ の場合，対角線上の点までの最短経路の例のように $64$ となることが分かります．

さらに，これを拡張して，直線を右に $k$ ずらし，点 $(k, N)$ を端点とする半直線上の格子点までの最短経路数の総和を考えます．以下は $k = 3$ の場合の例です．

これは累積和を $k$ 回取るだけなので，

[x^{N}] \frac{(1 - x)^{p - k - 1}}{(1 - x)^{p} - x^{q}}

と表されます．

グリッドの端の点までの最短経路

下図のような縦

N

区画，横

M

区画のグリッドがあり，左下の点(黒)からグリッドの端の各点(オレンジ)までの最短経路数の総和を求めます．下図は

N = 4, M = 6

の例です．

ここでグリッドの区画を右に増やします．そして各点を右の辺上に移動させます．このグリッドでの左下の点(黒)から各点(オレンジ)までの最短経路数の総和は元のグリッドでの最短経路数の総和と同じです．さらに，左下の点から右上の点(黒)への最短経路は必ずオレンジの点をただ一つ通るので，求める最短経路数の総和はこのグリッドでの左下の点から右上の点への最短経路数の総和と一致します．したがって， $(\binom{N + M + 1}{N})$ が答えとなります．

経路の上側の面積がKとなる最短経路

以下のように、赤い経路に対して，経路の上側の色が塗られたマスの数のことを，赤い経路に対する上側の面積とします．この例の場合，面積は

10

となります．

縦 $N$ 横 $M$ のグリッドで上側の面積が $K$ となるような最短経路の数は，簡単な対応付けにより「 $K$ を $N$ 個以下の" $M$ 以下の非負整数"に分割する方法の数」であることが分かります．*8
単純な動的計画法では $O (N M K)$ かかりますが，q二項係数と形式的冪級数を利用すると $O (K \log K)$ で求めることができます．(問題例のところに問題(Mojacoder)置いてます)

交差しない最短経路の組

縦

N

区画，横

M

区画のグリッドの最短経路のうち，互いに交差しないようなもの

K

個の選び方を求めます．

ただし， $2$ つの最短経路が交差するとは，以下のような状態のことを指すものとし，

以下のような不完全な交差(重なっているだけで上下が入れ替わっていないもの)は考えないものとします．

$K = 3$ のケースを用いて説明します．
以下のように最短経路をスライドすることによって，どの $2$ つの最短経路も重なっていないようなものを数え上げる問題になります．

この問題はLGV公式を用いて解くことができ，答えは

\prod_{i = 0}^{K - 1} \frac{(N + M + i)! (i)!}{(N + i)! (M + i)!}

となり，

O (N + M + K)

で求めることができます．

より詳しい解説はこの記事を参照してください．

ある領域を通らない最短経路

下図のような縦

N

区画，横

M

区画のグリッドがあり，左上の一部の領域を通らないような最短経路数を求めます．ただし，領域は図のように階段状になっている必要があり，領域の境界は通ってよいものとします．下図は

N = 6, M = 7

の例です．灰色の部分が通れない領域を示しています．

$d p_{i, j}$ を「上に $i$ ，右に $j$ 進んだ場所までの経路数」としたとき，単純な遷移では $O (N M)$ かかってしまいます．

通れる領域を真ん中付近で分割し，再帰的に求めていくことを考えます．以下のように，赤枠の部分を境目にしてオレンジの部分と水色の部分に分割されます．

オレンジの部分を再帰的に求めた後，以下の赤点の値が求まっています．赤点群の値から黄点群の値を求めることを考えます．詳しいことは書きませんが(TODO:書く)，畳み込みができる形になっているため，分割統治FFTの要領で $O ((N + M) \log^{2} (N + M))$ で求めることができます．

左上だけでなく右下の領域も通れない場合は

以下のように領域を分割することで先程と同様に求めることができます．

ちなみに，これは簡単な対応付けにより以下のような問題に言い換えることができます．

以下の条件を満たす長さ

N

の整数列

A, B

が与えられる．

$A_{i} \leq B_{i}$
$0 \leq A_{1} \leq A_{2} \leq \dots \leq A_{N} \leq M$
$0 \leq B_{1} \leq B_{2} \leq \dots \leq B_{N} \leq M$

$A_{i} \leq C_{i} \leq B_{i}$ を満たす長さ $N$ の広義単調増加整数列 $C$ の数を求めよ．

$A_{i} > A_{i + 1}$ であっても $A_{i} \leftarrow A_{i + 1}$ としても問題ないので以下の問題も同様に解けます．

0

以上

M

以下の整数からなる長さ

N

の数列

A, B

が与えられる．

A_{i} \leq C_{i} \leq B_{i}

を満たす長さ

N

の広義単調増加整数列

C

の数を求めよ．

実装例

問題例

*1:https://arxiv.org/pdf/1503.05930.pdf

*2:https://arxiv.org/pdf/1503.05930.pdf

*3:https://arxiv.org/pdf/1503.05930.pdf

*4:https://arxiv.org/abs/2406.09590v1

*5:Alon Regev, "A proof of Catalan’s Convolution formula", (2011).

*6:Dardy, "［Tutorial］ Catalan Numbers and Catalan Convolution".

*7:Counting lattice paths by crossings and major index I: the corner-flipping bijections

*8:https://manabitimes.jp/math/888

かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

グリッドの最短経路の数え上げまとめ

最短経路の数え上げとは

一般的な最短経路

ある点を通る最短経路

ある点を通らない最短経路

ある長方形領域を通らない最短経路

ある直線を跨がない最短経路

傾き1の直線を跨がない最短経路(直線1本)

傾き1の直線を跨がない最短経路(直線2本)

傾き1の2本の直線の間を通る最短経路

傾き1/μの直線を跨がない最短経路

傾きq/pの直線を跨がない最短経路

対角線上を $K$ 回通る最短経路

$K$ 回曲がる最短経路

右折が $K$ 回ある最短経路

右左折が $K$ 回ある最短経路

左折が $K$ 回ある対角線を跨がない最短経路

左折が $K$ 回ある直線を跨がない最短経路

右折が $K$ 回ある直線を跨がない最短経路

右左折が $K$ 回ある直線を跨がない最短経路

複数の最短経路数の和

対角線上の点までの最短経路

傾き-q/pの直線上の点までの最短経路

グリッドの端の点までの最短経路

経路の上側の面積がKとなる最短経路

交差しない最短経路の組

ある領域を通らない最短経路

問題例

最短経路の数え上げとは

一般的な最短経路

ある点を通る最短経路

ある点を通らない最短経路

ある長方形領域を通らない最短経路

ある直線を跨がない最短経路

傾き1の直線を跨がない最短経路(直線1本)

傾き1の直線を跨がない最短経路(直線2本)

傾き1の2本の直線の間を通る最短経路

傾き1/μの直線を跨がない最短経路

傾きq/pの直線を跨がない最短経路

対角線上をKK回通る最短経路

KK回曲がる最短経路

右折がKK回ある最短経路

右左折がKK回ある最短経路

左折がKK回ある対角線を跨がない最短経路

左折がKK回ある直線を跨がない最短経路

右折がKK回ある直線を跨がない最短経路

右左折がKK回ある直線を跨がない最短経路

複数の最短経路数の和

対角線上の点までの最短経路

傾き-q/pの直線上の点までの最短経路

グリッドの端の点までの最短経路

経路の上側の面積がKとなる最短経路

交差しない最短経路の組

ある領域を通らない最短経路

問題例

対角線上を $K$ 回通る最短経路

$K$ 回曲がる最短経路

右折が $K$ 回ある最短経路

右左折が $K$ 回ある最短経路

左折が $K$ 回ある対角線を跨がない最短経路

左折が $K$ 回ある直線を跨がない最短経路

右折が $K$ 回ある直線を跨がない最短経路

右左折が $K$ 回ある直線を跨がない最短経路