重複組み合わせ

問題1

 りんご12個を3人に分ける。

(1) 受け取らない人がいても良いものとするとき,何通りの分け方があるか。

(2) 受け取らない人がいてはいけないとするとき,何通りの分け方があるか。

(3) 誰もが最低2個は受け取るとするとき,何通りの分け方があるか。

問題2

 りんご,なし,みかんがたくさんある。これらから合計12個の果物を組み合わせてかごに詰める。

(1) 含まれない果物があってもよいとするとき,詰め方は何通りあるか。

(2) どの果物も最低1つは詰めるとするとき,詰めかたは何通りあるか。

(3) どの果物も最低2つは詰めるとするとき,詰めかたは何通りあるか。

問題1では,同じ物(りんご)12個を3人に分ける。同じ物を分けるときは何個ずつ分けるかがきまれば,分け方そのものが決まってしまう(例えばAさんに3個,Bさんに7個,Cさんに2個と決めれば,それが一通りの分け方になる)。そこで,問1の(1)では,12個の同じ物を3人に分けるために,2個の仕切りを混ぜて並べることを考えよう。(なぜ2個の仕切りなのかについてはあとでわかる。)

○(りんごを表わす)……12個

■(仕切りを表わす)…… 2個  計14個

そうしてこれらを並べたとき,例えば次の図のように並んだら,Aに3個,Bに7個,Cに2個分けることを意味すると考える。

また次の図のように並んだら,Aに7個,Cに5個を分け,Bは0個(二つの仕切りの間に○がないのでBはなし)と考えてやればいいわけだ。

要するに,一列に並んだ12個の玉を,3人に分けるために2枚の仕切りで分けてやるようなものだ。

さて,その並べ方の数だが,

○(りんごを表わす)……12個

■(仕切りを表わす)…… 2個  計14個

を並べるのだから,

となるわけだ。

 (2)や(3)では,全員に最低1つまたは2つのりんごを与えなければならない。ところが(1)の解き方では1つももらわない人がいる場合も数えてしまうのは,既に説明した通りだ。そこで例えば(2)の場合は,最初にあらかじめ1個ずつあげてしまうことにすればよいのだ。そうすれば残り9個のりんごについては,もらわない人が出てしまっても大丈夫なので,(1)と同じように分け方を考えてやればいいわけだ。最初に全員に1個ずつ,計3個のりんごを分けてしまったので,残っているりんごは9個で,そこに仕切りを2個混ぜる。

○(りんごを表わす)……9個

■(仕切りを表わす)……2個  計11個

だからその並べ方の数は

となる。また(3)では,全員が最低2個のりんごを受け取るので,最初に全員に2個ずつ計6個のりんごを分けてしまい,残りの6個に仕切り2個を混ぜて,

○(りんごを表わす)……6個

■(仕切りを表わす)……2個  計8個

だからその並べ方は

となる。

問題2は問題1とは設定が全く違うが,実は計算の方法は同じなのだ。

問題2では何をいくつ選ぶかは決まっていないが,合計12個にすることだけは決まっている。そこでまず,自分が12枚の「果物引換券」を持っていると考えよう。これを「りんご」・「みかん」・「なし」に好きなように交換するのだ。それぞれに何枚ずつ配分するか,その配分の仕方の数は12枚の同じ券を3組に分ける分け方と同じだ。分け方一通りにつき,手にする果物の組み合わせも一通りで,分け方が違えば組み合わせも違うわけだ。

(1)では

引換券

  ……12枚

■(仕切り)…… 2枚  計14枚

を並べるから,

となる。

(2)では,どの果物も最低1個は詰めなければならないから,はじめに引換券3枚を使ってりんご・みかん・なし1つずつに引き換えて詰めてしまえば,あとの9枚の引換券はどう分けてもいい(引き換えない果物があっても良い)ので,

引換券

  ……9枚

■(仕切り)……2枚  計11枚

を並べる並べ方を考える。すると,

となる。

(3) では,はじめに引換券6枚を使って,りんご・みかん・なし2つずつに引き換えて詰めてしまい,残りの6枚の引換券をわけるから,

引換券

  ……6枚

■(仕切り)……2枚  計8枚

で,その計算は

となる。

 本来重複組み合わせとは,問題2のようにn種類のものから重複を許して(何個ずつ取っても良いとして)合計r個の組み合わを作ることを指すものである。しかし実際の計算では,区別のつかない物r個を,区別のつくn組に分けることを考えて計算することになるわけである。そのとき重要なことが,合計の個数分だけ引換券を用意してそれをn組に分ける,と考えることなのだ。

まとめ

  区別のつかない物r個を,区別のつくn組に分ける分け方の数は,

○……r個

■……個  計

 の並べ方の数と同じである。

  また,n種類のものから重複を許して(何個ずつ取っても良いとして)合計r個を組み合わせる組み合わせ方は,任意の種類のもの1個に対応する引換券をr枚用意して,それをn組に分けることを考えれば

引換券

……r個

■  ……個  計

 の並べ方と同じである。

練習問題

問題1 [易] 100人の選挙権を持った人々が,3人の候補者から1人の当選者を選ぶために無記名投票を行なう。票数の分かれ方は何通りあるか。

問題2 [易] コーラ,サイダー,烏龍茶,オレンジジュースの缶飲料があって,どれも100円である。これらを1000円分買うとき,どの種類も最低1つは買うことにすると何通りの買い方があるか。

問題3 [難] 3個のりんごを5人で取り合うとき,りんごの分かれ方は何通りあるか。

問題4 [標準〜難] りんご,みかん,なしが9個ずつある。

(1) 9個を組み合わせて果物詰合せを作るとき,何通りの詰めかたがあるか。ただし詰めない果物があっても良い。

(2) 10個のときはどうか。ただし詰めない果物があっても良い。

(3) 7個のときはどうか。ただしどの果物も最低1個は詰めるものとする。

(4) 8個のときはどうか。ただしどの果物も最低1個は詰めるものとする。


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

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

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

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