様々な学問/勉強課目を図解/アニメーション化したり、シミュレーションツールを用いて楽しく分かりやすく解説するサイトです!
⇒ 本ブログの詳細/連絡先はコチラ!
⇒ 本ブログは複数テーマ(色)を持つ階層構造になってます!
学問TOP 数学 経済学/投資 統計学/確率 物理学
  1. ホーム
  2. 〇学問/勉強
  3. 数学
  4. 順列/組み合わせ
  5. 数学入門:組み合わせの考え応用!最短経路選択問題をシミュレーターで理解しよう!
■注目記事一覧

コンピューターの全理基礎:半加算器の原理をシミュレーターで理解しよう!

なぜ全力買い(全額投資)はダメなのか?シミュレーション交えて解説!

統計学/確率入門:偏差値とは何か?をシミュレーターを用いて詳しく解説!

コンピューターの半理基礎:半加算器の原理をシミュレーターで理解しよう!

なぜ賭け/投資(株式/FX)市場はほとんどの人が勝てないのか?シミュレーションで解説!

本サイトの「サイコロ シミュレーター」が熊本の特別教育テレビ授業で使われました!

運動量保存の法則をwebシミュレーションで解説!
 
スポンサーリンク
Twitter(更新情報)

数学入門:組み合わせの考え応用!最短経路選択問題をシミュレーターで理解しよう!

$$\newcommand\CB[1]{\textcolor{blue}{#1}} \newcommand\CR[1]{\textcolor{red}{#1}} \newcommand\CG[1]{\textcolor{magenta}{#1}}$$

組み合わせ(C記号)の考え方のまとめ!経路選択問題を考えていきます!

この記事では、組み合わせパターンのまとめとして「経路選択問題」を考えてみます。
 
この経路選択問題をシミュレーターを用いて考え、組み合わせとは何かを復習していきたいと思います。

復習:組み合わせ問題は「n個のクジから、r個選ぶ」ときのパターン総数を考えること

前回までの記事で、順列と組み合わせの考え方について解説してきました。まず、順列というのは「n個のクジから、r個引く」時のパターンを考える問題であり、そのパターン数は以下のようになります(詳細はコチラの記事へ)

[総数nからr個引くパターン数]
\( {}_n P_r = n \cdot (n-1) \cdot … \cdot (n – r + 1) \)

これに対して組み合わせとは「n個のクジから、r個選ぶ」時のパターンを考えることです。似ていますが、違います。r個選ぶ、なので引いたものの順番は関係ないんです。

そしてその組み合わせのパターン数は以下のようになります(詳細はコチラの記事へ

[総数nからr個引く組み合わせ数]
\( \displaystyle {}_n C_r = \frac{n \cdot (n-1) \cdot … \cdot (n – r + 1)}{ r! } \)

簡単にいうと、順列は引いたクジの順番を区別しますが、組み合わせはそれを意識しません。ですので、引いたクジの順列パターン数r!だけ重複があるのです。その分を\({}_n P_r\)から割り引いたのが\({}_n C_r\)になります。

組み合わせの考えを応用して、経路選択問題を考えよう!

問題設定

それでは組み合わせの考えを応用して、経路選択問題を解いてみましょう。

経路選択問題とは、↓のような経路があるときに最短経路でSTARTからGOALにたどり着く経路が何パターンあるかという問題です。

↓がその経路の一例です。「上向き移動」と「右移動」を組み合わせてGOALに最短でたどり着いています。

考え方

まず、上記のような最短経路となる条件は「右と上の移動だけで進むこと」と言えます。左あるいは下にいくので、右と上への移動だけでたどり着くのが条件になります。
 
そして、上の例では縦方向に3マス、横方向に5マスあるので、「上方向に3回、右方向に5回移動する」ことが必要になります。合計8回移動するわけですね。

こう考えていくと、、、実はこの経路パターンを考えることは、組み合わせ問題を考えることと同じと見なせるのです。この経路パターンは「合計8回の移動の中で、上方向への移動3回をいつ行うか」という問題です。そのため「上へいつ移動するかをクジ引きで選択」すると考えます。例えば、クジを引いて1,3,6が出たら、↓のように1回目、3回目、6回目で上に移動することにします

すると、上記の問題は「8個のクジの中で、3つのクジを引くパターンは何パターンあるか」と読み替えることができます。クジによって、経路が1対1に決まるためです。引いたクジの番号で上移動、余ったクジの番号で右移動すると決めれば、このクジ引きのパターン数が経路のパターン総数と同値となるのです!

シミュレーターで経路選択問題と組み合わせパターンを理解しよう!

上記の考えを分かりやすくするために、経路選択問題をシミュレーションできるツールを作成しました!
 
↓のスライドバーで横マスと縦マス数を変更すると、自動的にシミュレーションが走ります!シミュレーターは上記の考えの通り、クジ引きをして経路パターンを決めます。そして、全てのパターンを列挙していきます。
 
色々値を変えて、実験してみましょう!

横マス
4

縦マス
3

[組み合わせパターン数]

↓数字はクジを引いた結果を表しており、青い部分が前回クジから変わった部分を示しています。

↓このスライドバーの値を変えると、シミュレーターを高速に実行できます。パターン数が多い場合は最高速度で動かすこと推奨です!

速度
1

 

まとめ:組み合わせパターンを考える問題は色んなところで出てきます!

最後にまとめです。今回の最短経路選択パターンを考える場合では、うまく考え方をかえることで、実はクジ引きでの組み合わせパターン問題と同値であるとが分かります。
 
このように、一見すると全くクジとは関係ないような問題が、実は組み合わせを考える問題と同値であったりします。(実は、式のたすき掛けもこの組み合わせ問題に絡んでいたり…その話は別記事で解説予定です)

ですので、このような順列/組み合わせを考えることは非常に重要であったりします。現実の問題でも、組み合わせの考えが必要になること多くなるので、階乗、P記号、C記号の計算は理解しておきましょう!

数学入門:順列、組み合わせ
1.順列とは、階乗
2.順列(P記号)
3.円順列
4.組み合わせ数(C記号)
5.グループ分け(組み合わせの発展)
6.最短経路選択問題(組み合わせの応用) (本記事)

⇒「順列/組み合わせ」カテゴリ記事一覧

その他関連カテゴリ

[関連コンテンツ]




お気軽にコメントお願いします!

Your email address will not be published.