箱にカードを入れるという考え方（別解の研究）
Copyright (C) virtual_high_school, 1996-2017
ある生徒は次のような感想を述べる。
「問題集の順列・組合せの部分を解いて答合わせをすると、答は合うのに解き方がまったく違うのでがっくり来る。なぜ、自分の考え方ではいけないのかが分からない。」
問題集ではなぜ別の解き方をしてあるのかのあたりを研究してみると有益な結論が引き出せるかもしれない。
別解を考えることによって、その問題の全体像が分かりやしないかという予感がする。別解を「そういう考えもあるね」程度にほうっておくのは勿体ない。そこをつついてみよう。
【いっけん重複順列】
「重複順列」は積の法則を単純に使えば出てくるので、最も簡単ということになりそうだ。そこで、最初にこれを取り上げる。
（例題１） (投票結果)
5人の仲間で、夏休みは海へ行こうか、山に行こうか、それとも湖に行くかと話し合っている。話がつかないので各自記名の上、投票して決めることにした。投票の方法は何通りあるか。---
(本解)A,B,C,D,Eの5人のそれぞれが、海・山・湖の3通りの投票ができるので、積の法則により、
$ 3^{5} = 243 \mbox{通り} $
つまり、5つの変数が{海,山,湖}の3つの値のうちのひとつを取る、と考えた訳である。■
(別解)はたして、この5人はどこに行くんだろう。それが一番心配なのだから、海、山、湖の3つを変数とする。つまり、空箱を3つ用意して、そこにA,B,C,D,Eと書かれた5枚のカードを入れるのだ。投票結果は、
- 5人とも同じものに投票(これだと仲間割れも起こらない)。
- 2つのものに票が集中。票の割れ方は(4,1),(3,2)の2種類がある。
- 3つに票が割れる。割れ方は、(3,1,1),(2,2,1)の2種類だ。
が考えられる。全部で何通りかを計算すると、
$ 3 + (_{5}C_{4} \times 3! + _{5}C_{3} \times 3!) +(\frac{5!}{3!1!1!}
\times 3! \div 2 + \frac{5!}{2!2!1!} \times 3! \div 2)$
$= 3 + (30 + 60) + (60 + 90) = 243 \mbox{ ■} $
別解の方は計算するのも頭が痛い。重複順列の問題で、別解を考えるととてつもなく難しくなることがあることは注意すべきだろう。そうすると、さきほど重複順列は最も簡単と言いかけたことは、本当かどうか疑わしくなってきた。
ともかく、投票する者(人間)と投票されるもの(行き先)のうちのどちらを変数（空箱）にし、どちらを箱に入れるカード(値集合)にするかを逆転しただけで、こんなにも解答が異なることが分かった。
（例題２） (ベキ集合)
要素$n$個の集合の部分集合は、全部でいくつあるか。---
(本解) 各要素に {取る,取らない} の2種類のどちらかを選んで並べる「重複順列」だから、$2^{n}$個である。■
(別解) $n$個のものを「取る」箱と「取らない」箱に入れる方法だから、割れ方が
$ (n,0),(n-1,1),\cdots,(0,n) $
とあるので、
$ _{n}C_{n} + _{n}C_{n-1} + \cdots + _{n}C_{0} = 2^{n} $
右辺に直せることは二項定理のところでを習う。■
【いっけん順列】
(例題３) （Perfumeの並び方）
あ〜ちゃん、かしゆか、のっちの3人を横1列に並べる方法は何通りか---
(本解) 1番,2番,3番の箱に「あ〜ちゃん」、「かしゆか」、「のっち」と書かれたカードを入れる3次の置換の問題と考えて
$ _{3}P_{3} = 3! = 3 \times 2 \times 1 = 6 $
とやる。■
(別解)「あ〜ちゃん」、「かしゆか」、「のっち」という名の3つの箱があって、ここに1,2,3と書かれた番号札を入れる。これでも、計算法はまるで同じで
$ _{3}P_{3} = 3! = 3 \times 2 \times 1 =6 \mbox{ ■} $
この例題では、どちらの解答でも計算式は同じになる。
（例題４）(数字の順列)
$1,2,3,4,5$の$5$つの数字を使って$3$桁の整数は何個できるか。ただし、同じ数字は$2$度使えない。---
(本解) 百位、十位、一位と書かれた3つの箱に、{1,2,3,4,5} のカードのうちのどれかを重複せずに入れる。5個から3個取って並べる「順列」だから、
$ _{5}P_{3} = \frac{5!}{2!} = 60 \mbox{ ■} $
(別解) 1,2,3,4,5の箱があって、ここに {百,十,一} の3枚のカードを入れる。2つの箱には何も入らないのだが、それをはっきりさせるためにジョーカー(J)のカードを入れよう。結局、
{百,十,一,J,J}
を一列に並べる「同じものを含む順列」となって、
$ \frac{5!}{1! 1! 1! 2!} = \frac{5!}{2!} = 60 \mbox{ ■} $
【いっけん組合せ】
（例題５）(選手の選び方)
$7$人の中から$4$人のレギュラー選手を選ぶ。選び方は何通りか。---
(本解) 空箱を4つ用意する。袋の中には7枚のカード（7人）が入っていて、ここからカードを抜いて箱に入れる。箱は区別しないから「組合せ」になる。
$ _{7}C_{4} = \frac{7!}{4! 3!} =35 \mbox{ ■} $
(別解) 箱を7つ（7人分）用意する。候補者は7人で定数4の選挙を行なう。当選者にはバラの花をつけてあげよう。という訳で、7つの箱に○を4つ、×を3つ入れる「同じものを含む順列」になって、
$ \frac{7!}{4! 3!} = 35 \mbox{ ■} $
【いっけん同じものを含む順列】
次に、「同じものを含む順列」を取り上げる。
（例題６）
$(x+y+z)^{7}$の展開式において、$x^{3}y^{2}z^{2}$の項の係数はいくらか。---
(本解) $(x+y+z)$という同じ式が7つあり、各括弧の中から1つずつ項を出して掛け合わる。そのときできる同類項の個数が、展開式における係数である。
箱を7つ用意して、1番目の括弧の中から$y$を取ったなら、それを1番の箱に入れる、2番の括弧から取ったものは2番の箱に入れる。
このように、1番から7番の箱の中にカードを入れていけば、例えば
$ (1,2,3,4,5,6,7) = (y,z,y,x,x,z,x) $
のように$x,y,z$が番号のついた箱に収まる。だから、「同じものを含む順列」になって、係数は
$ \frac{7!}{3! 2! 2!} = 210 $
である。この事実を「多項定理」といい、上の係数を「多項係数」と言う。■
(別解) この問題を次のように考える人もいる。
$x,y,z$の3種類の箱を用意しておいて、7つの括弧から取り出したものをこの箱に仕分けして入れる訳だ。例えば
$ (x,y,z) = (\{4,5,7\},\{1,3\},\{2,6\}) $
という入れ方ができる。これは、カードでなく箱の中の小箱を区別しないことになる。
総数は、積の法則を2回使って
$ _{7}C_{3} \times _{4}C_{2} \times _{2}C_{2} = \frac{7!}{3! 2! 2! }
$
と組合せの積になる。結局、本解と同じになってしまう。■
【いっけん重複組合せ】
（例題７） (投票結果2)
5人の仲間が、海か山か湖かを無記名投票することにした。投票の方法は何通りあるか。---
(本解) {海,山,湖} の3種類から5個取る「重複組合せ」だから
$ _{3}H_{5} = _{3+5-1}C_{5} = 21 $
とやってもよいし、海・山・湖の3つの空箱に、○を5個（白紙のカードを5枚）入れる。そうすると、○5個、仕切り板2枚の「同じものを含む順列」だから
$ \frac{7!}{5! 2!} = 21 $
でもできる。■
(別解) 人間を変数（箱）にしてみる。無記名だから
$ (A, B, C, D, E) = (\mbox{海,海,山,山,湖}) $
は、
$ (A, B, C, D, E) = (\mbox{山,山,湖,海,海}) $
と同じになってしまう。そうなると、すべての割れ方を考えて
$ (5,0,0),(4,1,0),(3,2,0),(3,1,1),(2,2,1) $
となる。（この割れ方に共通しているのは、和が5ということだ。これは不定方程式 $x_{1} + x_{2} + x_{3} = 5$ の非負整数解の個数である。「不定方程式と来たら重複組合せ」というのは合言葉なので、これに気づけば本解が生まれる。）
上の割れ方から計算すると、
$ 3+ 3! + 3! + 3 + 3 = 21 \mbox{ ■} $
【部屋割問題】
ところで、区別・非区別で難しい問題に次のものがある。
（例題８）
$9$人を$3$人ずつに分けて、松の間、竹の間、梅の間に泊まらせる。何通りの方法があるか。
また、$9$人を$3$人ずつのグループに分ける方法は何通りか。---
(解) 9人分の箱を用意する。ここに、松、竹、梅各3枚のカードを入れる。これは「同じものを含む順列」である。だから
$ \frac{9!}{3! 3! 3!} = 1680 \mbox{通り。} $
後半のように、単に3人グループに分けるだけだと、さらに部屋の区別もないものと思えばよいので、松・竹・梅を並べ換える方法の数で割って、
$ \frac{1680}{3!} = 280 \mbox{通り} $
となる。■
後半の解答は、区別をつけないことで同値類が何個ずつできるかを考え、「クラス分けの論理」で割り算をすればよい。
例えば
(松,竹,梅) = ((A,B,C),(D,E,F),(G,H,I))
(松,竹,梅) = ((D,E,F),(A,B,C),(G,H,I))
の2つは、部屋割りとして見ると異なるが、グループ分けとして見ると同じ(同値関係にある)である。
しかし、4人+3人+2人の３グループに分ける問題の場合は、$3!$などで割ったりする必要はない。
【箱とカードの区別・非区別】
箱(変数)を区別する・しないと、箱に入れるカード(変数の取り得る値)の区別・非区別によって、解法はどう変わるか見てみよう。
- {a,b,c,d,e,f,g} から7つ取る問題。
・ 箱を区別すれば「全部を1列に並べる順列(=置換)」$7!$
・ 非区別の方は、答が1通りだから問題にならない。
- {a,b,c,d,e,f,g} から5つ取る問題。
・ 箱を区別すれば順列$_{7}P_{5}$
・ 非区別なら組合せ$_{7}C_{5}$
- {a,a,a,b,b,c,c} から7つ取る問題。
・ 箱を区別すれば同じものを含む順列$\frac{7!}{3! 2! 2!}$
・ 非区別は問題にならない。
- {a,a,a,b,b,c,c} から5つ取る問題。
・ 箱を区別する場合もしない場合も、こういったものに対して名前がつけられていない。しかも解くのが難しい。これについては後述する。
- {a,… ; b, … ; c, …} (カードは各種類とも無尽蔵にある)から$r$個取る。
・ 箱を区別すれば重複順列$3^{r}$
・ 非区別なら重複組合せ$_{3}H_{r}=_{3+r-1}C_{r}$
【分類名のない問題】
上の分類中で「後述する」とした問題を解いてみよう。
(例題９)
オレンジ・ジュースが3本、グレープ・ジュース、アップル・ジュースが各2本ある。ここから5本を選ぶ方法は何通りか。
また、5人の人間に１本ずつ与える方法は何通りか。---
(解)前半が箱を区別しない問題だ。ジュースが各種類とも無尽蔵にあれば
$_{3}H_{5}$
なのだが、そうではない。3種類のジュースへの割れ方は、
$ (3,2,0),(3,1,1),(2,2,1) $
で、これらに3種類のジュースを当てはめていくが、3本取れるのはオレンジに限られる点に注意する。
$ 2! + 1 + _{3}C_{2} = 6 $
が前半の答。
後半の答えは、上の計算式を再利用して
$ \frac{5!}{3! 2!} \times 2! + \frac{5!}{3! 1! 1!} \times 1 + \frac{5!}{2!
2! 1!} \times _{3}C_{2} $
$ = 20+ 20 + 90=130 \mbox{ ■} $
【高校生講座：「順列・組 合せ」のページ】 ←ここをクリック！