道順の個数(最短距離で目的地に達する道順の総数)

道順の個数

 図のように東西 4 条、南北 6 条で区画された市街地があります。

 Excel道順の個数①

 A 地点から出発してから B 地点に 最短距離で到達する道順 が何通りあるのか考えてみましょう。上図の赤い線は道順の 1 例です。1 回通った道を引き返さない限り、どこを通っても最短距離となります。そこで横方向への移動を X , 縦方向の移動を Y という記号で書くことにすれば、図の赤い線は

X X Y X Y X X Y

というように表すことができます。どのような道順であっても X の総数は 5 , Y の総数は 3 となっています。つまり

□□□□□□□□□□

という 8 個の空欄に、Y を 3 つ入れると残りは X となって道順が 1 つ定まることになります。つまり空欄を 3 つ取り出す組合せの総数が道順の総数に一致するので、求める個数は
 
\[_8\mathrm{C}_3=56\]
と計算できます。

 目的地まで縦の道数が $m$ 個、横の道数が $n$ 個あるとき、最短距離で目的地に達する道順の総数は

\[_{m+n}\mathrm{C}_m=_{m+n}\mathrm{C}_n\]で与えられます。

 しかし、この道順問題はもっとパズル的に解く方法が知られています。

 道順の個数②

 上の図のように各マスの隅に、そこまでに至る道順の数を書き込んでいけば、簡単に目的地に達する道順の総数を求めることができます。複雑な問題では、組合せ公式を使うと面倒な場合分けが必要ですが、この「書き込み方式」を使えば、ほとんどの問題を簡単に解決することができます。

道順の例題 ①

 いくつかの例題で練習してみましょう。

 道順の個数③PQを通る条件

 今度は PQ (青い線) を必ず通らなくてはならない、という条件をつけてみます。この場合は A から P までの道順の数と、Q から B までの道順の数をかければ答えが得られますね。
 
\[_5\mathrm{C}_{2}\times\: _{3}\mathrm{C}_1=10\times 3=30\]
 書き込み方式で解くと下の図のようになります。

 道順の個数④

道順の例題 ②

 次は下の図のような形をした市街地です。

 道順の個数⑤

 こういう変な形になると、組合せ公式では面倒ですので、迷わずに「書き込み方式」を選択しましょう。

 道順の個数⑥

 答えは 105 通りとなります。 ≫ 数学事典

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください