高校数学A 最短経路と順列—通過点と禁止点を移動の記号列に置き換える｜武蔵野個別指導塾

右と上の移動列を数え、通過点の前後を掛ける理由と、禁止点を通る経路を全体から除く手順を確かめます。

よくあるのは、高1が搬送ロボットの道順を調べ、指定された点までの道とその先の道を足し合わせる場面です。出発点から通過点に着いただけでは、目的地への道順は完成しません。前半の道のそれぞれに後半の道をつなぐと、完成した道が何通りできるでしょうか。曲がり角を眺める代わりに、右と上の移動を順に書き出して考えます。

何を数える問題か

碁盤目の道に沿って、出発点から右上の目的地へ進むことを考えます。道は格子の線上にあり、隣の交点までを1回の移動とします。異なる道順は別に数え、同じ道を移動した時刻やロボットの向きでは区別しません。ここでは道の長さを区間の数で測り、途中で引き返さない経路を調べます。

問題の型は大きく3つあります。出発点と目的地だけが与えられる型では、右と上の回数を決めてその並びを数えます。指定点を通る型では、そこで経路を前後に切り、前半と後半をつなぎます。禁止点を通らない型では、制限のない全体から禁止点を通る経路を取り除く方法が使えます。いずれも「完成した経路」を何通り数えているかが判断の軸です。

指定点が出発点から右上にあるか、目的地がさらにその右上にあるかも先に見ます。この位置関係が成り立たないと、右と上の移動だけでは指定点を経由できません。図を描くときは交点と区間を区別し、移動回数を数えます。交点の個数をそのまま移動回数にすると、端の分だけずれてしまいます。

移動の列と経路を対応させる

出発点から右へa区間、上へb区間離れた目的地を考えます。右と上はともに格子の線に沿う移動です。右向きの移動は少なくともa回、上向きの移動は少なくともb回必要なので、最短の移動回数はa + b回です。右にa回、上にb回だけ進めば実際にその回数で到着できます。左や下に進むと、それを打ち消す移動も必要になるので最短にはなりません。

右への1回をR、上への1回をUと書きます。最短経路は、a個のRとb個のUを並べた列で表せます。例えばRURUは右、上、右、上の順です。列を先頭からたどれば経路が1つ決まり、逆に経路をたどれば移動の列が1つ決まります。したがって経路と記号列は一対一に対応します。

図1のように、R同士やU同士には区別がありません。列の全a + bか所からRを置くaか所を選べば、残りはUと決まります。よって、最短経路の数は(a + b)Caです。Uの位置を選ぶ(a + b)Cbでも同じ数です。a、bは0以上の整数で、出発点と目的地が同じなら空の移動列が1通りあります。

この式を使う前に、各区間が同じ長さで、右と上の経路が実際に通れることを確かめます。通れない区間や余分な迂回がある問題では、移動の回数だけでは道の存在を保証できません。また、指定点までの最短経路と、指定点から目的地までの最短経路をつなぐには、指定点が両端の間の右上方向にあることが必要です。

指定点をPとすると、完成した経路をPで切る操作と、前半と後半の経路を1つずつ選んでつなぐ操作は逆になります。前半が3通り、後半が4通りなら、前半ごとに後半を4通り選べるので3・4通りです。3 + 4は断片の数で、出発点から目的地までの経路の数ではありません。

基本例題：区間の数から列を作る

搬送路は格子状で、出発点Aから目的地Bは右に4区間、上に2区間あります。格子の線上を進む最短経路は何通りですか。答えは整数の通り数で求めます。

最短なら右4回、上2回の合計6回です。図2の経路はそのうちの1つで、移動列はRRUURRです。上への移動は2回、右への移動は4回で、確かにBに着きます。別の列は、最初に異なる記号を置いた時点で異なる区間を進むため、同じ道にはなりません。

6か所のうちUを置く2か所を選びます。残りの4か所はRですから、同じ経路を重ねて数えることもありません。

6C2 = (6・5)/(2・1)
    = 15

答えは15通りです。右の位置を選ぶなら6C4で、Uの位置を選ぶ方法と残りの位置を対応させれば同じ15通りです。Rを4個、別々に名付けて並べた後に区別を外す方法もありますが、ここでは位置の選択だけで直接数えられます。

答えを条件に戻すと、どの列もRが4個、Uが2個で、移動は6回です。右や上への移動だけで指定の距離を進むため、どの列も最短です。例えば最初の2か所をUにする列と最後の2か所をUにする列は、同じ終点でも異なる経路です。終点が同じことと道順が同じことを混同しないようにします。

標準例題：通過点で切ってつなぐ

格子状の搬送路で、AからBは右に5区間、上に3区間あります。Aから右に2区間、上に1区間の点Pを通る最短経路は何通りですか。答えは整数の通り数で求めます。

PはAとBの間にあり、AからPへは右2回、上1回です。PからBへは残りの右3回、上2回となります。どちらの区間も右と上だけで進めるため、前後の最短経路をつなぐと全体でも右5回、上3回の最短経路です。

前半と後半をそれぞれ数えます。

AからP = 3C1
        = 3
PからB = 5C2
        = (5・4)/(2・1)
        = 10
通過する経路 = 3・10
              = 30

答えは30通りです。前半の列はRRU、RUR、URRの3種類です。それぞれに後半の10種類をつなぐと、完成した経路は各10通りできます。どの完成経路もPまでの部分とPからの部分が一意に決まるため、異なる組が同じ経路になることはありません。

別の見方では、全8回のうち最初の3回にUが1回、残る5回にUが2回入る列を数えています。前半でUの位置を選ぶ方法が3通り、後半が10通りなので、同じ積になります。Pを通るという条件が、移動列の途中までに必要なRとUの個数に置き換わっています。

全体の制限を外すと8C3 = 56通りで、30はその範囲内です。さらに、選んだ列をつなぐと合計のRは2 + 3 = 5個、Uは1 + 2 = 3個となります。この確認は積の結果だけでなく、分割位置が正しかったかを調べるために役立ちます。

発展例題：禁止点を通る経路を引く

格子状の通路で、AからBは右に6区間、上に4区間あります。Aから右に2区間、上に2区間の点Qは通行できません。右と上に進むAからBへの最短経路のうち、Qを通らない経路は何通りですか。答えは整数の通り数で求めます。Q以外の交点と区間は通れます。

Qを避ける経路を直接場合分けすることもできますが、避け方の境界を決めないと同じ経路を数え直しやすくなります。ここでは制限を外した最短経路を全体とし、そこからQを通る経路を引きます。全体はQを通る経路と通らない経路に重なりなく分かれるからです。

全体はRが6個、Uが4個の列です。

全体 = 10C4
     = (10・9・8・7)/(4・3・2・1)
     = 210

Qまでの移動は右2回、上2回です。QからBへは右4回、上2回です。どちらも右上方向に進めるので、Qを通る全体の最短経路は前後の最短経路の組に対応します。

AからQ = 4C2
        = 6
QからB = 6C2
        = 15
Qを通る経路 = 6・15
              = 90
Qを通らない経路 = 210 - 90
                  = 120

答えは120通りです。取り除いた90通りは実際にQを通り、右の移動は合計6回、上は合計4回です。引いた残りはQを通らず、それ以外の道は通れるので問題の条件を満たします。210通りの中で通るか通らないかは必ず決まり、両方に入る道はないため、差を取って過不足がありません。

分かれ目は「点を通る」のか「点を通らない」のかです。前者なら前後の積をそのまま答えにし、後者なら全体からその積を引きます。もし禁止点が最短経路の範囲外にあれば、右と上だけではそこを通れず、引く数は0です。さらに、禁止点が複数ある場合に各点を通る数を単純に引くと、複数の禁止点を通る経路を重ねて引くことがあります。重なりを確かめてから分類する必要があります。

足し算と引き算を取り違えたら

標準例題で「AからPが3通り、PからBが10通りなので3 + 10 = 13通り」とする誤答を考えます。原因は、前半の道と後半の道をそれぞれ完成した道として数えていることです。例えば前半をRRUに固定しても、その後に異なる後半を10通りつなげられます。

図3のように、前半の1つから後半の候補を選んで初めてAからBまでの道が完成します。前半の別の2通りについても、それぞれ後半を10通り選べます。したがって3 + 10を3・10に直します。足し算が使えるのは、完成した経路を重なりのない複数の種類に分けたときです。

禁止点の問題では逆に、Qを通る90通りをそのまま答える誤りも起こります。その数は除外する側です。求める条件を「通る」「通らない」のどちらかで式の横に書き、最後に答えと問題文を照合します。通れない点を経由する経路の数が求める数より小さいとは限らないので、大小だけでは取り違えを発見できません。

もう1つの誤りは、AからPまでの移動を数え、PからBまでにもAからの距離をそのまま使うことです。後半に必要なのは全体から前半を除いた距離です。横と縦を別々に引き、前後の移動回数を足して元の距離に戻るかを確かめます。

練習問題

いずれも道は等間隔の格子の線上にあり、隣の交点間を1区間とします。指定のない交点と区間は通れます。経路は通る道順で区別し、答えは整数の通り数で求めてください。

1. 資料を運ぶ台車が、始点から右に3区間、上に3区間の終点へ進みます。最短経路は何通りですか。
2. 点検車が始点から右に4区間、上に3区間の終点へ進みます。始点から右に1区間、上に2区間の点を通る最短経路は何通りですか。
3. 配送車が始点から右に5区間、上に2区間の終点へ進みます。始点から右に2区間、上に1区間の点を通らない最短経路は何通りですか。
4. 巡回車が始点から右に4区間、上に4区間の終点へ進みます。始点から右に1区間、上に1区間の点と、右に3区間、上に2区間の点をこの順に通る最短経路は何通りですか。
5. 運搬機が始点から右に3区間、上に2区間の終点へ進みます。始点から右に4区間、上に1区間の点を通る最短経路は何通りですか。

練習問題の答えと解き方

1. 右3回、上3回の計6回の列を作ります。Uの3か所を選ぶので、次のようになります。

6C3 = (6・5・4)/(3・2・1)
    = 20

答えは20通りです。どの列も右3回と上3回を含み、終点に6回で到着します。Uの位置が違えば途中の経路も異なります。

2. 指定点までは右1回、上2回で、3C1 = 3通りです。そこから終点へは右3回、上1回で、4C1 = 4通りです。前後を1つずつつなぎます。

3・4 = 12

答えは12通りです。前後の移動を足すと右4回、上3回になり、指定点を経由して最短で着きます。前半が同じでも後半が違えば、完成する経路は別です。

3. 制限のない全体は7C2 = 21通りです。指定点までが3C1 = 3通り、そこから終点までが4C1 = 4通りなので、指定点を通るのは12通りです。

21 - 3・4 = 9

答えは9通りです。引いた道は右に2 + 3回、上に1 + 1回進む最短経路で、指定点を通ります。残りはその点を避け、終点に着きます。

4. 1つ目の点までは右1回、上1回で2C1 = 2通りです。2点の間は右2回、上1回で3C1 = 3通り、2つ目から終点までは右1回、上2回で3C1 = 3通りです。

2・3・3 = 18

答えは18通りです。3区間の右の回数の合計は1 + 2 + 1 = 4回、上も1 + 1 + 2 = 4回です。各点で切った3つの道の組が、完成した道に一対一に対応します。

5. 指定点は終点より右に1区間あります。そこから終点へ行くには少なくとも左への移動が必要で、右と上のみの最短経路では通れません。

通過する最短経路 = 0

答えは0通りです。指定点に着けることだけを見ず、そこから終点までの向きも調べます。左に戻る道を許しても、最短移動回数より多くなるため条件を満たしません。

覚えておくこと

右a回、上b回の最短経路は(a + b)Ca通りです。 通過点が両端の間にあるとき、前後の経路数を掛けます。 禁止点を避ける経路は、全体からその点を通る経路を引けます。 移動回数と、通過点から終点まで進める向きを確かめます。

つまずきの見分け方

式に和が現れたら、それぞれが完成した経路を表すのか、途中までの断片を表すのか尋ねます。断片なら、前半の1つを固定したときに後半を何通り選べるか、実際に2本ほど描いて確かめます。図を描けても式に移れないときは、各区間をRとUでたどり、同じ記号の位置を選ぶ操作に戻ります。

個別に確認するときは、答えだけでなく、指定点の前後の右と上の回数を本人に示してもらいます。各回数を足して元の距離に戻らなければ、分割した場所か残りの数に誤りがあります。禁止点なら、引く前の数がどんな道を表すかも言葉にします。経路の条件を移動の列に戻せば、式の意味を検証できます。