今回は重複組合せ nHr について解説していきます。
重複組合せの基本的な考え方
「重複組合せとは、異なる n 個のものから重複を許して r 個取る組合せの総数である」
と説明されることが多いですが、状況が想像しにくくてわかりにくいですよね。
こう書くとどうでしょうか。
「異なる n 種類のものから重複を許して r 個取る組合せの総数」
まだわからない人もいると思います。
ではもう少し具体的に書きます。
「異なる3種類の果物から重複を許して6個取る組合せの総数」
なんとなく想像できましたか？
普通の組合せ nCr と比較して考えてみましょう。
よくある解説は以下のようなものだと思います。
nCr は、異なる n 個のものから異なる r 個のものを取る組合せの総数。
nHr は、異なる n 個のものから重複を許して r 個取る組合せの総数。
書き換えると、
nCr の場合、異なる n 種類のものから異なる r 種類のものを取る組合せの総数。
nHr の場合、異なる n 種類のものから重複を許して r 個取る組合せの総数。
それぞれの場合について具体例を書きます。
nCr の場合
リンゴ、ミカン、イチゴ、バナナ、牛肉の5種類の果物から、異なる3種類を取る組合せの総数。
・・・5C3
nHr の場合
リンゴ、ミカン、イチゴの3種類の果物から、どの種類でもいいから5個取る組合せの総数。
・・・3H5
想像できましたか？
つまり、nCr の場合は異なる種類の果物を選びますが、
nHr の場合は、同じ種類でもいいから何個か果物を選んで下さいということです。
重複組合せの公式
重複組合せの公式は以下のようになります。
nHr = (n+r-1)Cr
ちなみに H は、homogeneous product（同次積）の頭文字です。
この公式の考え方について例題を使って解説していきます。
例題と解き方
それでは例題を解いてみましょう。
（問題）リンゴ、ミカン、牛肉の3種類の果物があります。これらの中から6個の食材を買って帰ります。このとき、何通りの買い方がありますか？ただし、含まれない食材があってもよいものとします。
（解答）このような、何種類かあるものの中から何個かを取る組合せを求めるときに、重複組合せの公式を用います。
n = 3、r = 6なので、3H6 = (3+6-1)C6 = 8C6 = 8C2 = 8*7/2 = 28
したがって答えは28通りになります。
重複組合せ問題の考え方と公式の意味
このような問題の場合、まず買う個数である6個の〇を描きます。
〇〇〇〇〇〇
ここに、2個の仕切りを描き足します。
〇｜〇〇〇｜〇〇
このとき、以下のように自分でひとつ目の仕切りの左側はリンゴ、仕切りと仕切りの間はミカン、ふたつ目の仕切りの右側は牛肉と仮定します。
〇｜〇〇〇｜〇〇 → リンゴ1個｜ミカン3個｜牛肉2個
この問題の場合は選ばれない食材があってもいいので、
〇〇〇〇｜｜〇〇 → リンゴ4個｜ミカン0個｜牛肉2個
という状況も含めることができます。
重複組合せの公式は nHr = (n+r-1)Cr でしたね。
n は食材の種類の数、r は買った食材の個数なので、この問題の場合 n = 3、r = 6です。
買った食材の個数は6個だから〇は6個描きました。
では仕切りの数はなぜ2個なのでしょう？
それは、2個の仕切りで3個に分割できるからです。
上で描いたように、2個の仕切りを入れることで食材を3種類に分けられていますね。
消しゴムを2回切れば消しゴムが3個に増えているのと同じです。
同様に考えると、n 個の種類に分けたいなら仕切りは n-1 個必要になりますね。
つまり、公式の (n+r-1)Cr に書かれている n-1 は仕切りの個数のことであり、
n+r-1 は買った食材の個数と仕切りの個数の和を表しているのです。
また、組合せの公式 nCr は、n 個の場所から r 個の場所を選ぶ組合せの総数を求める公式であると表現することもできます。
例題の 8C6 の場合は、8個の場所から買った食材を置く6個の場所を選ぶ組合せの総数を求めています。
長々と解説してきましたが、重複組合せの公式は、買った食材の個数と仕切りの個数の和である n+r-1 個の場所から、買った r 個の食材を置く場所を選ぶ組合せの総数を求めているのです。
同じものを含む順列の総数と重複組合せの総数は同じ
6個の〇と2個の｜で問題の状況を表すことができますが、この順列の総数を求めることによっても答えは導けます。
同じものを含む順列の総数を求める公式は、n!/(p!*q!) です。
実際に計算すると、8!/(6!*2!) = (8*7)/2 = 28（通り）となり、答えが導けました。
ここで、同じものを含む順列の公式は n!/(p!*q!) ですが、p+q = n の場合のみこの公式は成り立ちます。
つまり、n!/(p!*q!) = n!/(r!*(n-r)!) と書き直すことができます。
この式をどこかで見た記憶はありませんか？
実はこの式は組合せの総数を求める公式と同じなんです。
nCr = nPr/r! = n!/(r!*(n-r)!)
nPr = n!/(n-r)! なのでこのように表すことができるんですね。
したがって、同じものを含む順列の総数を求めるということは、
重複組合せの総数を求めることと同じであると考えられます。
この問題の場合、
6個の〇と2個の｜を並べ替える総数（順列の総数）を求めることと、
8個の場所から6個の食材を置く場所を選ぶこと（組合せの総数）を求めることは同じです。
順列の観点から考えると、8!/(6!*2!) = (8*7)/2 = 28（通り）
組合せの観点から考えると、8C6 = 8C2 = (8*7)/2 = 28（通り）
以上から、同じものを含む順列の総数と重複組合せの総数が一致することがわかりました。
もし重複組合せの公式を忘れても、同じものを含む順列の考え方で解くことができますね。
ポイントとまとめ
組合せを考えるときは、「個」と「種類」で考えてみましょう。
nCr は、異なる n 種類のものから異なる r 種類のものを取る組合せの総数。
nHr は、異なる n 種類のものから重複を許して r 個取る組合せの総数。
このように「個」「種類」という違う言葉で覚えておくと、理解しやすくなります。
また、重複組合せの公式は、n+r-1 個の場所から r 個の食材を置く場所を選ぶ組合せの総数を求めており、n+r-1 は選ぶ食材の置き場所と仕切りの個数の和です。
結局公式の意味がよくわからなかった人もいると思いますが、
公式に数字を当てはめるだけで解ける問題しか出ないので、公式だけは確実に暗記し、上に記したようにどのような問題だったら重複組合せの公式を使うのかを理解しておきましょう。
同じものを含む順列の総数と重複組合せの総数は同じであることを覚えておけば、公式を忘れてしまっても問題を解くことはできるので，順列で求める練習もしておいた方がいいかもしれませんね。
理系科目全般に言えることですが、実際に状況を描いて考えましょう。
頭の中だけで考えて問題を解こうとする人がいますが、
少なくとも大学を卒業するまでは、頭の中だけで答えを導くスキルは求められません。
紙に状況を描いて、ひとつひとつ条件を確認しながら問題を解きましょう。
↓↓↓参考にしている本です。
数学はなるべく簡単に考えましょう。
★とうふめんたるずLINEスタンプ！絶賛好評発売中！★
★とうふめんたるずLINE絵文字も絶賛好評発売中！★
コメント