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

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

最短経路の数え上げとは
一般的な最短経路
ある点を通る最短経路
ある点を通らない最短経路
ある長方形領域を通らない最短経路
ある直線を跨がない最短経路
対角線上をK回通る最短経路
K回曲がる最短経路
複数の最短経路数の和
1. 対角線上の点までの最短経路
2. グリッドの端の点までの最短経路
経路の上側の面積がKとなる最短経路
交差しない最短経路の組
ある領域を通らない最短経路
問題例

最短経路の数え上げとは

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

一般的な最短経路

例として，以下の縦 ${4}$ 区画，横 ${6}$ 区画のグリッド上の最短経路を考えます．

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

ある点を通る最短経路

グリッド上の最短経路のうち，ある点 ${P}$ を通るようなものの数は，(左下から点 ${P}$ までの最短経路の数)×(点 ${P}$ から右上までの最短経路の数)となります．

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

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

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

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

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

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

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

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

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

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

この場合の最短経路数は ${\displaystyle\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対応するからです．

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

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

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

${\displaystyle\binom{N+M}{N}-\binom{N+M}{K-1}}$

となります．

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

$C_N=\binom{2N}{N}-\binom{2N}{N-1}=\frac{1}{N+1}\binom{2N}{N}$

と表されます．

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

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

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

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

${\displaystyle\sum_{k\in\mathbb{Z}}\binom{N+M}{N+kP}-\binom{N+M}{K-1+kP}}$

となります．

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

${s\leq t}$ を整数として，直線 ${y=x+s}$ と ${y=x+t}$ の間を通る(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で ${(a,b)}$ から ${(c,d)}$ に移動する経路数は
${\displaystyle\sum_{k\in\mathbb{Z}}\left(\binom{c+d-a-b}{c-a-k(t-s+2)}-\binom{c+d-a-b}{c-b-k(t-s+2)+t+1}\right)}$

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

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

${\mu}$ を正負整数として，直線 ${y=\frac{1}{\mu}x}$ を跨がない(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で ${(a,b)}$ から ${(c,d)}$ に移動する経路数は

${\binom{c+d-a-b}{c-a}-\sum_{i=\lfloor a/\mu\rfloor +1}^{d}\binom{i(\mu +1)-a-b-1}{i-b}\frac{c-\mu d+1}{c+d-i(\mu +1)+1}\binom{c+d-i(\mu +1)+1}{d-i}}$
もしくは
${\sum_{i=0}^{\lfloor a/\mu\rfloor -b}(-1)^i\binom{a-\mu(b+i)}{i}\times\frac{c-\mu d+1}{c+d-(\mu +1)(b+i)+1}\binom{c+d-(\mu +1)(b+i)+1}{d-b-i}}$

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

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

${\displaystyle\frac{c-\mu d+1}{c+d+1}\binom{c+d+1}{d}}$
となります．

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

${p,q}$ を互いに素な正整数として，直線 ${y=\frac{q}{p}x}$ を跨がない(直線上は通ってもよい)条件のもとで，格子点上を上か右のみの移動で ${(0,0)}$ から ${(p,q)}$ に移動する経路数は

${\displaystyle\frac{1}{p+q}\binom{p+q}{p}}$

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

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

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

縦横 ${N}$ 区画のグリッドの左下から右上への最短経路のうち，グリッドの対角線上の(始点と終点を除く)点ををちょうど ${K}$ 回通るものの数を数えます．例えば以下の最短経路は対角線上の点を ${3}$ 回通っています．

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

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

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

${\displaystyle\sum_{t_1+t_2+\cdots +t_{K+1}=N}(2C_{t_1-1})(2C_{t_2-1})\cdots (2C_{t_{K+1}-1})\\ =\displaystyle 2^{K+1}\sum_{t_1+t_2+\cdots +t_{K+1}=N}C_{t_1-1}C_{t_2-1}\cdots C_{t_{K+1}-1}}$

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

${\displaystyle\binom{2N-K-2}{N-1}-\binom{2N-K-2}{N}=\frac{K+1}{2N-K-1}\binom{2N-K-1}{N}}$
であることが知られています．*4 *5

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

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

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

${K}$ 回曲がる最短経路

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

下図のような縦 ${N}$ 区画，横 ${M}$ 区画のグリッドの最短経路のうち，右折( ${\uparrow\rightarrow}$ )の数を数えます．例えば以下の例では ${N=4,M=6}$ で右折回数は3回となります。

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

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

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

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

形式的冪級数による解釈

最初に右に0回以上進み，右折を ${K}$ 回行って，最後に上に0回以上進む．
${f=(x+x^2+x^3+\cdots)(y+y^2+y^3+\cdots)}$
${f_x=(1+x+x^2+x^3+\cdots)}$
${f_y=(1+y+y^2+y^3+\cdots)}$
としたときの ${[x^{N}y^{M}]f_{x}f^{K}f_{y}}$ が求める値．
${\displaystyle\frac{1}{(1-x)^{K+1}}=\sum_{0\leq i}\binom{K+i}{K}x^i}$ なので ${\displaystyle\binom{N}{K}\binom{M}{K}}$ となる．

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

右折( ${\uparrow\rightarrow}$ )と左折( ${\rightarrow\uparrow}$ )両方の数の和が ${K}$ となる最短経路の数を数えます．例えば以下の例では ${K=5}$ です．

まず，始点から最初に上( ${\uparrow}$ )か右( ${\rightarrow}$ )どちらに進むかで別々に考えます．上に進む場合を考えると，右折回数は ${\lceil\frac{K}{2}\rceil}$ 回，左折回数は ${\lfloor\frac{K}{2}\rfloor}$ 回となります．最後の右折(左折)を無視する( ${K}$ によって最後どの列で右折(左折)するかは決まっているため)と，下図の左の矢印から右折する列を ${\lceil\frac{K-1}{2}\rceil}$ 個，下の矢印から左折する列を ${\lfloor\frac{K-1}{2}\rfloor}$ 個選ぶと最短経路が一意に定まります．

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

したがって，経路数は ${\displaystyle\binom{N-1}{\lfloor\frac{K-1}{2}\rfloor}\binom{M-1}{\lceil\frac{K-1}{2}\rceil}+\binom{N-1}{\lceil\frac{K-1}{2}\rceil}\binom{M-1}{\lfloor\frac{K-1}{2}\rfloor}}$ となります．

形式的冪級数による解釈

最初に右に進む場合，右に1回以上進むのを ${\lceil\frac{K+1}{2}\rceil}$ 回，上に1回以上進むのを ${\lfloor\frac{K+1}{2}\rfloor}$ 回交互に繰り返すことになると考えると，右折がK回ある最短経路と同様に求めることができる．

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

縦横 ${N}$ 区画のグリッド上の対角線を跨がない(下側のみを通る)最短経路のうち，左折( ${\rightarrow\uparrow}$ )を ${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公式を用いて求めると ${\displaystyle\frac{1}{N}\binom{N}{K}\binom{N}{K-1}}$ となります．

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

より一般に，以下のように縦 ${N}$ 区画，横 ${M}$ 区画のグリッドの上から ${L}$ 区画にかけて下図のように直線がある場合，その直線を跨がない最短経路のうち，左折( ${\rightarrow\uparrow}$ )が ${K}$ 回あるようなものの数を数える．

これは下図のように辺を延長することで左折がK回ある対角線を跨がない最短経路と同様に考えることができます．

具体的には最初に右に ${N-L}$ 回進み，最後に上に ${M-L}$ 回進んだことにしてやればよいです．
${\displaystyle\binom{N}{K}\binom{M}{K}-\binom{L-1}{K}\binom{N+M-L+1}{K}}$ となります．
${N=M=L}$ のとき左折がK回ある対角線を跨がない最短経路と一致することがわかります．

複数の最短経路数の和

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

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

下図のような縦横 ${N}$ 区画のグリッドがあり，左下の点(黒)から対角線上の各点(オレンジ)までの最短経路数の総和を求めます．下図は ${N=6}$ の例です．

この例では，最短経路数は左上の点から順に ${\displaystyle\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}$ になります．

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

下図のような縦 ${N}$ 区画，横 ${M}$ 区画のグリッドがあり，左下の点(黒)からグリッドの端の各点(オレンジ)までの最短経路数の総和を求めます．下図は ${N=4,M=6}$ の例です．

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

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

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

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