立体の格子を最短で進む - 右と奥と上の並べ替え

立体の格子を、右へ 3、奥へ 2、上へ 1 進んで最短で行きます。道は 60 通り。

平面のときと考え方は変わりません。進む向きが 2 種類から 3 種類に増えただけで、分母に階乗が 1 つ足されます。

進む向きの列に置きかえる

最短で行くので、後戻りはしません。進む向きは右、奥、上の 3 つだけです。

右へ $a$、奥へ $b$、上へ $c$ 進むなら、進む回数は必ず $a+b+c$ 回。その並び順を決めれば道が 1 本決まります。

つまり「右右右奥奥上」のような文字列の並べ替えを数えることになる。同じものを含む順列です^[2]。

$$\frac{(a+b+c)!}{a!b!c!}$$

右 3、奥 2、上 1 なら $\frac{6!}{3!2!1!}=\frac{720}{12}=60$ 通りです。

例：立方体の格子

各方向に 2 区画ずつの格子で、対角の頂点まで行きます。右 2、奥 2、上 2。

$$\frac{6!}{2!2!2!}=\frac{720}{8}=90$$

90 通りです。平面の $2\times 2$ なら ${}_4{\mathrm{C}}_2=6$ 通りでしたから、方向が 1 つ増えるだけで 15 倍になります。

各方向 3 区画なら $\frac{9!}{3!3!3!}=1680$ 通り。増え方が急です。

例：立方体の辺だけを通る

格子ではなく、立方体の辺の上だけを通って対角の頂点へ行く場合もあります。

各方向に 1 区画ずつなので、右、奥、上を 1 回ずつ。$3!=6$ 通りです。

立方体の頂点から対角の頂点への最短の道は 6 本。実際に模型で数えても同じになります。

経由点があるとき

途中の点を必ず通る条件は、平面と同じく前半と後半に分けます。

出発点から $(3,2,2)$ まで行く道で、$(1,1,1)$ を必ず通るものを数えます。

前半は右 1、奥 1、上 1 で $3!=6$ 通り。後半は右 2、奥 1、上 1 で $\frac{4!}{2!1!1!}=12$ 通り。

前半のどの道からも後半が 12 通りなので、掛けて $6\times 12=72$ 通りです。

例：通ってはいけない点

同じ格子で、$(1,1,1)$ が通れないとします。

全体は右 3、奥 2、上 2 なので $\frac{7!}{3!2!2!}=\frac{5040}{24}=210$ 通り。

そこから、$(1,1,1)$ を通る 72 通りを引きます。

$$210-72=138$$

138 通りです。平面のときと手順は変わりません。

交点に数を書き込む

公式を使わずに、格子点へ順に数を書き込む方法も使えます。ある点へは、右、奥、上のいずれかの手前からしか来られない。

だから、その点の数は 3 つの手前の数を足した値になります。平面では 2 つでしたが、1 つ増える。

立体は図が描きにくいので、高さごとに層を分けて 3 枚の表にします。

いちばん右の層の右下に 90 が現れました。公式で出した値と一致します。

書き込み法の強みは、通れない点があっても手順が変わらないこと。その点を 0 にして、あとは同じように足していくだけです。

例：斜めに進める場合

右と奥を同時に進む斜めの道が加わると、進む回数が一定でなくなります。回数で場合分けが要る。

右 2、奥 2、上 1 の格子で、斜めの道を 1 回だけ使えるとします。

斜めを使わないなら $\frac{5!}{2!2!1!}=30$ 通り。斜めを 1 回使うと、右 1、奥 1、斜め 1、上 1 の 4 回で進むので $4!=24$ 通り。

合わせて 54 通りです。進む回数がそろわない問題では、まず回数で分ける。

例：方向がもっと増える場合

進む向きが 4 種類でも、式の形は変わりません。分母に階乗が 1 つ増えるだけです。

$$\frac{(a+b+c+d)!}{a!b!c!d!}$$

この形は、多項定理に出てくる係数と同じものです^[3]。展開式の係数と経路の数が一致します。

平面と立体の比べ方

平面では ${}_{a+b}{\mathrm{C}}_a$ と組合せの形で書けました。立体では組合せ 1 つでは書けません。

ただし、段階に分けて組合せを掛ける形にはできます。$a+b+c$ か所から右の $a$ か所を選び、残りから奥の $b$ か所を選ぶ。

$${}_{a+b+c}{\mathrm{C}}_a\times {}_{b+c}{\mathrm{C}}_b$$

右 2、奥 2、上 2 なら ${}_6{\mathrm{C}}_2\times {}_4{\mathrm{C}}_2=15\times 6=90$ で、階乗の式と一致します。

よくある誤り

平面の考え方がそのまま伸びます。向きの種類だけ分母を増やす、それだけです。

参考文献

^[1] が格子の上の経路、^[2] が同じものを含む順列、^[3] が多項係数、^[4] と ^[5] が各国語での整理です。