以前、数実研で重複組合せの指導の一例を、レポートとしてまとめ発表したことがあります(「数学のいずみ」の中に収められていると思いますが)。同次積とみるのではなく、組合せの応用と捉えて
ところで、この内容について、後に菅原先生(藻岩高校)と数実研の懇親会で四方山談義をしていたときに、先生から、「経路として考える方法もありますね」と指摘されたことがあります。最短経路問題は、組合せの代表的なものですが、そもそも最短経路の問題を重複組合せの定義として説明しているS社の参考書もありますから、これを触れないのはやはり片手落ちでした。実はレポートをまとめたときは「並べ方」の方法および「基準数」の求め方に論点を置いてしまったために、経路による方法はまったく頭の中に思いつかなかったのです。
しかし、実際にレポート内容を実践に移していくと、「仕切り分配法」では扱い難い問題に直面してしまいました。もともと、重複組合せの問題は、「どういった問題が重複組合せなのか」ということの判断が意外と難しいものです。そこで原点に戻って考えてみると、経路問題として捉えると随分すっきりとまとめられることが分かりました。
そこで、重複組合せの4番目の指導法として、次の「棒グラフ分配法」について考えてみます。
棒グラフ分配法
ex)6個の林檎をA,B,C3人に分配する方法は何通りか。 |
前回と同じ問題で考えてみましょう。
さて、3人に配る林檎を図1のように棒グラフとして分けてみましょう。図は、A,B,Cにそれぞれ2個,1個,3個と分ける場合です。次に図2のように、林檎をずらしてみましょう。
この棒グラフを次のようにモデル化します。
結局、林檎の分け方は、下図の点Pから点Qへの最短経路となることが分かります。
以上より、8C2=28 (通り)となります。
もちろん、この場合の最低分配個数は0個となることは、A,B,Cがそれぞれ4個,0個,2個の場合は右図のように考えればいいことから分かります。
棒グラフ分配法から経路分配法へ
この分配法は、前回の@〜Bが1次元的分配法であるのに対し、2次元的分配法とみることができます。重複組合せの代表例として、無記名投票の問題がありますが、「10人の選挙人が、4名の候補者に無記名で投票する方法は何通りか」を、縦に候補者4名の名前を並べ、得票数を棒グラフで表してみると分かり易くなります。経路の縦線、横線は、個数と人数という異なる要素とみた2次元的配列と捉えればよいのです。そして、この配列からは、個数の最適化が柔軟に扱うことが可能となります。
Ex) x+y+z=8を満たす整数解(x、y、z)の個数を次の場合について求めよ。
|
解)
よって、7C2=21通り。
ところで、(2)の設問は、図をみると必ずしも
x≧1,y≧1,z≧1
である必要はないことが分かります。
x≧2,y≧0,z≧1
であっても出発点に変わりはないのです。(図3)
一般に
x≧a,y≧b,z≧c
の場合は、a+b+cだけstart地点を右にずらせばいい訳です。
であるから、右に2だけstart地点をずらせば、
8C2=28通り
となります。(図4)
まとめ
各項が、1,2,3,4のどれかである5個の数の列(a1,a2,a3,a4,a5)で a1≦a2≦a3≦a4≦a5であるものの個数を求めよ。 |
この問題に対して、丸棒分配法や仕切り分配法を使おうとすると(不可能ではないですが)無理があります。もともと丸棒や仕切りは「ものを並べて」という問題への対処の仕方ですから、この問題のように重複組合せの要点をずばり問い掛けるようなものには対応し難いのです。そうすると順序組分配法ということになってしまいますが、この方法が理解しにくいのは前回のレポートの通りです。
ところが、これらの分配法に対して、棒グラフ分配法は、
をとっていけば、容易に選び方を視覚化できます。この問いの場合は、
8C3=56通り
となります。このように理想的なモデル化ができるのは、「最短経路問題」がもともとは重複組合せの問題であるからです。通常は、この種の問題は教科書では同じものを含む順列で扱われ、さらに縦と横の選び方とみて組合せとして求める(ヨタヨタ法と呼ばれる方法で)のが一般的でしょう。
右図のような場合には、
となりますが、これを、5つの横線を重複を許して、5個とると見れば、
5H5=9C5
で得られることがわかります。
ただいきなり最短経路に結び付けてしまうと、指導の流れとして混乱を起こす危険性はあるでしょう。そこで、もっと現実的に個々の要素の(成績)を積み上げた棒グラフとみてモデル化をすると、理解が容易になるのではないでしょうか。