下の図をご覧になって「●の地点から、★の地点まで至る経路で…」とあれば採点経路の手順をすぐに思い浮かべる方もいるかと思います。
今回は少し違ったパターンを見て、最短経路問題と比較しておきましょう。
問:●の地点から、★の地点まで至る経路は何通りあるか?右から左への移動をすることはできないが、最短経路でなくてもかまわない。
右から左への移動をすることはできないということは、「←」のような方向には進めないわけですね。
最短経路問題では「遠回り」をすることも認められませんから、下の図内での矢印のような移動ができませんでした。
しかし、この問いであれば、右から左への移動をしているわけではないので、可能になります。だとすると、考え方はこうなります。
例えば、ひとつ右に移動するにあたって、通れる道は3通りあります。
★に到達するためにこれを3回行う必要がありますから3通りを3回。
すなわち数式として以下のようになり、答えが導けます。
答、27通り。
重複順列の問題は講義内でも取り扱っているので、気づけた方も多いかもしれませんね。