組み分け全パターン


結構大変であるが,出来れば以下の少なくとも(9)までをマスターしたいものである。

問題 9個の玉を3組に分けることを考える。

(1) 9個の異なる玉を,Aさんに4個,Bさんに3個,Cさんに2個分ける方法は何通りあるか。

(2) 9個の異なる玉を,4個・3個・2個の3組に分ける方法は何通りあるか。

(3) 9個の異なる玉を,Aさんに3個,Bさんに3個,Cさんに3個分ける方法は何通りあるか。

(4) 9個の異なる玉を,3個・3個・3個の3組に分ける方法は何通りあるか。

(5) 9個の異なる玉を,1個・4個・4個の3組に分ける方法は何通りあるか。

(6) 9個の異なる玉を,3人に分ける方法は何通りあるか。ただし受け取らない人がいてもよい。

(7) 9個の異なる玉を,3人に分ける方法は何通りあるか。ただし受け取らない人はいないものとする。

(8) 区別のつかない玉9個を,3人に分ける方法は何通りあるか。ただし受け取らない人がいてもよい。

(9) 区別のつかない玉9個を,3人に分ける方法は何通りあるか。ただし受け取らない人はいないものとする。

(10) 区別のつかない玉9個を3組に分ける方法は何通りあるか。ただし組に区別は付けず,0個の組はあってはならない。

(11) 9個の異なる玉を3組に分ける方法は何通りあるか。ただし組に区別は付けず,0個の組はあってはならない。

 

★平成29年11月9日追加:(11)の問題に対し,読者の方から以前こちらで紹介していた解法よりも美しい考え方を教えて頂きました。当面この追記(この文)と,(11)の美しい解法を追加した状態でおいておきます。

 

 組み分けの問題には,いろいろなパターンがあるが,それらをひとまとめにして説明されたことはないと思う。そこでここではそれらをきちんとパターン分けしておこう。そして理解するべきことをまとめたのが次の表である。

 aは組の数,bは区別のつく組の数である。

 これでは何のことだかわからないであろうから,一つ一つ解説していくことにする。

(1) 9個の異なる玉をAさんに4個,Bさんに3個,Cさんに2個分ける方法は何通りあるか。

 とりあえず異なる9個から,Aさんに渡す玉を4個選ぼう。

 次に残った4個から,Bさんに渡す玉を3個選ぶ。

 最後に残った2個から,Cさんに渡す玉……これはもう選ぶ余地はなく,1通りである。

 この3つの作業は連続操作なので,全部掛け算して

とすればOKである。

(注:分ける数の少ないCさんの分から選ぶほうが,計算式は簡単になる。その場合の計算は

となる。)

 この問題では,9個の異なる玉を3人に分けるということなので,分けられるもの(玉)に区別があって,組(人間)にも区別があるというわけである。しかも組内の要素の個数が決まっているので,その組に決められた個数ずつ選んでゆくだけでよいのである。

(2) 9個の異なる玉を4個・3個・2個の3組に分ける方法は何通りあるか。

 実はこの場合も(1)とまったく同じで,まず異なる9個から4個の組を選んで通り,次に残った4個から3個の組を作って通り,最後に残った2個がそのまま2個の組になるわけなので,

でいいわけである。この場合も,4個の組・3個の組・2個の組が全部違う組(玉の個数が違う)なので,人に渡すのではないけれども,組の区別がつくという点で(1)と同じなのである。

(3) 9個の異なる玉をAさんに3個,Bさんに3個,Cさんに3個分ける方法は何通りあるか。

 これも方法は(1)や(2)とまったく同じである。Aさん,Bさん,Cさんは人間で区別があるので,まずAさんに与える3個を選んで通り。残った6個からBさんの3個を選べば通り。最後に残った3個がCさんのものになるから,

である。

(4) 9個の異なる玉を,3個・3個・3個の3組に分ける方法は何通りあるか。

 この場合は(1)や(2)や(3)とはちょっと違うのである。3つの組は個数が同じなので,それぞれの組に違いがないのである。組の区別がつかないわけである。

 しかしはじめから組に区別がないものとして分けるのは難しいので,各組に仮の看板A・B・Cをつけて分けることを考える。そうすれば(3)と同じなので

(通り)

と計算できる。ところが実際には組に区別がないので,9個の玉が,例えば次の表のように別れてしまった場合は,仮に付けておいた組の看板ABCをはずしてしまうと,まったく同じ組み分けになってしまうのである。

  分け方1 分け方2 分け方3 分け方4 分け方5 分け方6
A組
B組
C組

 上の表では,「A組」「B組」「C組」という看板があるからこそ,別々の分け方に見えるが,組名をはずしたら

  分け方1 分け方2 分け方3 分け方4 分け方5 分け方6
×組
×組
×組

どの分け方でも「の組」と「の組」と「の組」があるだけである。

 仮の看板を付けていたときは,の組との組との組それぞれに,仮の看板A・B・Cの付け方の方法の数だけ余計に数えていたというわけである。その看板の付け方はA・B・Cの3文字の並べ方の数だけあるはずなので,3!通りあることになる。つまり,

組の区別があるときの3!通り → 組の区別がないときの1通り

という関係であることが分かる。これは「の組」と「の組」と「の組」のような,ほかの3個ずつの組についても,同じように看板付きのときは通り数えているわけなので,仮の看板を付けたときの分け方通りを,3!でわって(看板はずしして)

となるわけである。

(5) 9個の異なる玉を,1個・4個・4個の3組に分ける方法は何通りあるか。

 今度もまず仮の看板A,B,Cをつけて組み分けすることを考えよう。

(通り)

 今度の場合(4)と違うところは,中身が1個だけの組については,看板をはずしても他の4個の組とは個数の違いから区別がつくということである。

  分け方1 分け方2   分け方3 分け方4   分け方5 分け方6
A組
B組
C組

 上の表でA,B,Cの看板を外した場合,分け方1・2は同じ分け方になり,分け方3・4も同じ分け方になり,分け方5・6も同じ分け方になる。看板を外した場合に区別がなくなってしまうのはB組とC組の2組だけなので,余計に数えていたのは,看板BとCの付け方の方法の分だけということになる。その看板の付け方はB・Cの2文字の並べ方の分だけなので 通りである。つまり,

組の区別があるときの2!通り → 組の区別がないときの1通り

という関係である。そこで仮の看板を付けたときの分け方通りを,2!でわって(看板はずしして)

となるわけである。

(6) 9個の異なる玉を3人に分ける方法は何通りあるか。ただし受け取らない人がいてもよい。

 (3)との違いは,一人当たりの取り分が決まっていないことである。玉のゆくえを1つずつ追っていってみよう。

…… A,B,Cの3通りの行き場所がある。
…… 同じくA,B,Cの3通りの行き場所がある。
…… 同じくA,B,Cの3通りの行き場所がある。
…… 同じくA,B,Cの3通りの行き場所がある。
……以下同様

というわけで,どの玉も3通りの行き場がある。そして一人当たりの取り分が決まっていないので,たとえ全ての玉がAに行ってしまっても構わないわけである。(3)では許されなかったことである。

 するとこの計算方法は意外に単純で,3通りの行き道を持った異なる玉が9個あるので,

となるだけである。

(7) 9個の異なる玉を3人に分ける方法は何通りあるか。ただし受け取らない人はいないものとする。

 (6)は簡単でも,(7)のように「受け取らない人がいない」とした場合突如として難しくなるのである。多くの人が(9)からの連想で「とりあえずを3人に分けておけば,あとは貰わない人がいてもいいから……」と考えて失敗する。この考え方だと,の3個が必ず違う人に行くことになってしまうが,実際にはが全部Aさんに行っても,他の玉のうち最低一個ずつがBさんとCさんに行けば問題ないわけである。

 で,仕方がないので余事象で行くことにする。受け取らない人がいる場合というのは,2人が受け取らない(全部の玉が1人に行く)場合と,1人が受け取らない(2人で山分け状態)の2通りがある。これらの分け方の数を(6)の答からひいてやるのである。

 まず2人が受け取らず,全部の玉が1人に行く場合は,Aに全部行く場合とBに全部行く場合とCに全部行く場合の3通りだけである。

 厄介なのは1人が受け取らない場合である。例えばAが受け取れず,全ての玉をBとCの2人で分け合う分け方は,異なる9個の玉を2人に分けることを考えて,通りとなりそうなものだ。ところがこの通りの中には,全部がBに行く場合と全部がCに行く場合まで含まれているのである。これらは実際には1人占めとなるので,今計算しようとしている「1人だけが受け取らない場合」に当てはまらない。そこでAだけが受け取らない分け方の総数は,から2をひいて,

通り

となる。そして同じことがBだけが受け取らない場合とCだけが受け取らない場合についてもいえるので,結局誰か1人が受け取らない場合の総数は

通り

である。

 これらの使って,誰もが最低1個は受け取るような分け方を計算する。それには

全ての分け方全部が1人に行く分け方2人だけで分け合う分け方

と計算すれば良いので

39-3-(29-2)×3 = 39-3・29+3 = 18150 通り

となる。

(8) 区別のつかない玉9個を3人に分ける方法は何通りあるか。ただし受け取らない人がいてもよい。

(9) 区別のつかない玉9個を3人に分ける方法は何通りあるか。ただし受け取らない人はいないものとする。

 この2問についての説明は,「重複組み合わせ」を参照してもらいたい。それぞれの答は,次の通りである。

(8)

○(玉)……9個
■(仕切り)……2個  計11個を並べて

(9) まず玉3個を使って,3人に1個ずつを渡してしまい,残りの6個について,受け取らない人がいてもよいとして3人に分けることを考える。

○(玉)……6個
■(仕切り)……2個  計8個を並べて

(10) 区別のつかない玉9個を3組に分ける方法は何通りあるか。ただし組に区別は付けない。

 各組にA,B,Cという看板をつけて玉を分けておいて,後から看板をはずせばよさそうなものだが,各組の個数が決まっていないときは危険なのである。(4)と(5)でやったように,同じ個数が入った組がいくつあるかによって,看板外しのために分母に持ってくる階乗が変わるからである。例えば2個・3個・4個に分かれる分け方は,看板がある場合は次の3!通りであり,

  分け方1 分け方2 分け方3 分け方4 分け方5 分け方6
A組 ○○ ○○ ○○○ ○○○ ○○○○ ○○○○
B組 ○○○ ○○○○ ○○ ○○○○ ○○ ○○○
C組 ○○○○ ○○○ ○○○○ ○○ ○○○ ○○

この場合は

看板がある場合は3!通り → 看板がない場合は1通り

となるので,3!でわらなければならないはずである。ところが例えば1個・4個・4個に分かれる分け方は,看板がある場合でも次の3通りしかない。

  分け方1 分け方2 分け方3
A組 ○○○○ ○○○○
B組 ○○○○ ○○○○
C組 ○○○○ ○○○○

 このように,3組の玉の数が全部違う場合と,同じ個数の組がある場合で,看板がついているときの分け方の数が違うので,看板をつけて分けた場合の数をあっさりでわることができない。そこでこのような「分けるものに区別なし,組に区別なし,個数も決まっていない」場合は,数え上げの道しか残っていない。個数の少ない組から並べていく順番で,数え上げよう。

「○」 「○」 「○○○○○○○」 (1, 1, 7)

「○」 「○○」 「○○○○○○」 (1, 2, 6)

「○」 「○○○」 「○○○○○」 (1, 3, 5)

「○」 「○○○○」 「○○○○」 (1, 4, 4)

「○○」 「○○」 「○○○○○」 (2, 2, 5)

「○○」 「○○○」 「○○○○」 (2, 3, 4)

「○○○」 「○○○」 「○○○」 (3, 3, 3)

以上の計7通りである。

 念のため付け加えておくが,ダブりを避けるために個数の少ない順に並べているので,(1, 4, 4)個の組み合わせのあとは,(1, 5, 3)ではなく(2, 2, 5)であるし((1, 5, 3) の組み合わせは(1, 3, 5)個の組み合わせと同じである),同じ理由から(2, 3, 4)のあとは(2, 4, 3)ではなく(3, 3, 3)なのである。

(11) 9個の異なる玉を3組に分ける方法は何通りあるか。ただし組に区別はつけず,0個の組はあってはならない。

★以下は平成29年11月19日に追記した解法です。

 この場合は(10)とは違って,「看板がある場合はn!通り → 看板がない場合は1通り」を考えれば良い。なぜなら,例えば2個・3個・4個に分かれているときはもちろん「看板がある場合は3!通り → 看板がない場合は1通り」となるが,

  分け方1 分け方2 分け方3 分け方4 分け方5 分け方6
A組
B組
C組

1個・4個・4個のように,個数が同じである組があっても,中身が異なるのでやはり「看板がある場合は3!通り → 看板がない場合は1通り」となる。

  分け方1 分け方2 分け方3 分け方4 分け方5 分け方6
A組
B組
C組

 結局,どんな個数の組分けであっても,「看板がある場合はn!通り → 看板がない場合は1通り」となる

 そこで,「9個の異なる玉を区別のある3組に分ける方法(0個の組はない)」を 3! で割れば良いことになるのだが,「9個の異なる玉を区別のある3組に分ける方法(0個の組はない)」は (7)で答えたものであるから,それを分子として 3! で割れば良いことになる。従って,

となる。

 

★以下は平成29年11月19日以前から掲載していた解法です。

 これはかなり難しい。各組に仮の看板をつけて玉を分けておいて,後から看板をはずすのが危険なのは(10)と同じである。かといって数え上げようとすると異なる玉であるだけに分け方があまりに多くて大変である。仕方がないのでまず各組の個数を決めてから,各組に分けていくという段階を踏んでいこう。

 各組の個数の決め方は(10)と同じである。そしてそれぞれの個数の分け方について,組み合わせの数を考える。個数が決まっていて,各組の区別がない場合の分け方を計算するのである。

 まず,各組の個数が(1, 1, 7)と分かれるなる分け方は

 

次に (1, 2, 6)となる分け方は

(1, 3, 5)となる分け方は

(1, 4, 4)は

(2, 2, 5)は

(2, 3, 4)は

(3, 3, 3)は

以上を全てたして,

となった。


[御意見簡易送信窓]批判・激励・文句,なんでも歓迎。

 メール(任意)
 名前(任意)

本文公開可 非公開希望 私信

確認欄←ここに""と入力してから、「OK」を押してください