「重複組み合わせ」の公式・計算の考え方がイマイチ分かっていない
重複組み合わせ or 組み合わせ or 順列 の問題の見分け方を教えてほしい!
教科書よりもわかりやすく解説してほしい!
こういった要望に応えます。
このページを読めば
- 「重複組み合わせ」の 公式 と使い方
- 「重複組み合わせ」の 計算の考え方(仕切りあり・なし)
- 「重複組み合わせ」の 見分け方
- 「重複組み合わせ」の 整数解 の個数
などがバッチリ学べます。
重複組み合わせの公式 $_n H_r $
まず「重複組み合わせの公式」はこちら。
異なる $n$ 種類から、重複を許して $r$ コ選ぶ方法
$ $ $_n H_r = \, _{n+r-1} C_r $
※ 重複 $=$ 同じものを繰り返し用いること
※ $0$ 回のものがあっても(使わない種類があっても)OK
ふつうの重複を許さない「組み合わせ $ _n C_r$」の場合は、必ず $n≧r$ になります。
一方、「重複組み合わせ $_n H_r$」の場合は $n<r$ でもOKです。
重複組み合わせの計算①:公式を使う
まずは「重複組み合わせの公式 $_n H_r = \, _{n+r-1} C_r $」を使った問題の解き方を解説します。
【例題1】$A, \ B, \ C$ の $3$ 種類のケーキを合計 $5$ 個買うときの選び方の総数を求めよ。ただし、$0$ 個のものがあってもよい。
【解答】
$A, \ B, \ C$ の異なる $3$ 種類から、重複を許して $5$ コ選ぶ 組み合せなので
$ $ $_3 H_{5} = \, _{3+5-1} C_{5} $
$ $ $ = \, _{7} C_{5} $
$ $ $ = \, _{7} C_{2} $
$ $ $ \displaystyle{ = {7 \cdot 6 \over 2 } } $
$ $ $ = 21 $(通り)
「重複組み合わせの公式」に当てはめるだけですね。
【例題2】$ x+y+z=5, \ x≧0, \ y≧0,\ z≧0 $ をみたす整数 $x, \ y, \ z $ の組 $(x, \ y, \ z )$ は、全部で何組あるか。
実は、これは言い方は違えど【例題1】とまったく同じ内容の問題です。
なので
$x, \ y, \ z$ の $3$ 種類のケーキを合計 $5$ 個買うときの選び方の総数を求めよ。ただし、$0$ 個のものがあってもよい。
と言い換えることができます。
【解答】
$x, \ y, \ z$ の異なる $3$ 種類から、重複を許して $5$ コ選ぶ 組み合せなので
$ $ $_3 H_{5} = \, _{3+5-1} C_{5} $
$ $ $ = \, _{7} C_{5} $
$ $ $ = \, _{7} C_{2} $
$ $ $ \displaystyle{ = {7 \cdot 6 \over 2 } } $
$ $ $ = 21 $(組)
これは、整数解 における「重複組み合わせの公式」として覚えておきましょう。
整数解の「重複組み合わせの公式」
$ x+y+z=r, \ x≧0, \ y≧0,\ z≧0 $ をみたす整数解 $( x, \ y, \ z )$ の個数は
異なる $3$ 種類から、重複を許して $r$ コ選ぶ組み合わせなので
$ $ $_3 H_{r} = \, _{3+r-1} C_{r} $(個)
次に、このような公式・計算がなぜ成り立つのか?を説明します。
重複組み合わせの計算②:仕切りを使う
重複組み合わせ は「仕切りを使う」考え方でも計算できます。
さっきと同じ例題を考えてみます。
【例題1】$A, \ B, \ C$ の $3$ 種類のケーキを合計 $5$ 個買うときの選び方の総数を求めよ。ただし、$0$ 個のものがあってもよい。
【解答】
$5$ 個の「○」を用意する。
$ \enspace ○ \enspace \ ○ \enspace \ ○ \enspace \ ○ \enspace \ ○ \enspace \ $
その間と両端の $6$ カ所から $2$ カ所えらんで
仕切り「|」を入れる。
$ \displaystyle{\mathop{\,}_{\wedge} } ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} $
左からそれぞれ $A, \ B, \ C$ の個数と見る。
例:
$ \enspace \underbrace{ ○ }_{A \ 1コ} \ | \ \underbrace{ ○ \enspace \ ○ }_{B \ 2コ} \ | \ \underbrace{ ○ \enspace \ ○ }_{C \ 2コ} $ → $ \enspace A \ | \ B \enspace B \ | \ C \enspace \ C $
$ \enspace \underbrace{ ○ \enspace \ ○ }_{A \ 2コ} \ | \ | \ \underbrace{ ○ \enspace ○ \enspace \ ○ }_{C \ 3コ} $ → $ \enspace A \enspace \ A \ | \ | \ C \enspace C \enspace C $
$ | \ \underbrace{ ○ \enspace \ ○ }_{B \ 2コ} \ | \ \underbrace{ ○ \enspace ○ \enspace \ ○ }_{C \ 3コ} $ → $ | \ B \enspace \ B \ | \ C \enspace C \enspace \ C $
$ \left\{ ○, \ ○, \ ○, \ ○, \ ○, \ |, \ | \right\} $ の順列なので
$ $ $ _{7} C_{5} = 21 $(通り)
(注)同じものを含む順列 $\displaystyle{ {7! \over 5! \cdot 2!} } $ と考えてもOK
【例題2】$ x+y+z=5, \ x≧0, \ y≧0,\ z≧0 $ をみたす整数 $x, \ y, \ z $ の組 $(x, \ y, \ z )$ は、全部で何組あるか。
この問題も、仕切り「|」を使って考えてみます。
【解答】
$5$ 個の「○」を用意する。
$ \enspace ○ \enspace \ ○ \enspace \ ○ \enspace \ ○ \enspace \ ○ \enspace \ $
その間と両端の $6$ カ所から $2$ カ所えらんで
仕切り「|」を入れる。
$ \displaystyle{\mathop{\,}_{\wedge} } ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} ○ \mathop{\,}_{\wedge} $
左からそれぞれ $x, \ y, \ z$ の値と見る。
例:
$ \enspace \underbrace{ ○ }_{x=1} \ | \ \underbrace{ ○ \enspace \ ○ }_{y=2} \ | \ \underbrace{ ○ \enspace \ ○ }_{z=2} $ → $ \enspace x \ | \ y \enspace y \ | \ z \enspace \ z $
$ \enspace \underbrace{ ○ \enspace \ ○ }_{x=2} \ | \ | \ \underbrace{ ○ \enspace ○ \enspace \ ○ }_{z=3} $ → $ \enspace x \enspace \ x \ | \ | \ z \enspace z \enspace z $
$ | \ \underbrace{ ○ \enspace \ ○ }_{y=2} \ | \ \underbrace{ ○ \enspace ○ \enspace \ ○ }_{z=3} $ → $ | \ y \enspace \ y \ | \ z \enspace z \enspace \ z $
$ \{ ○, \ ○, \ ○, \ ○, \ ○, \ |, \ | \} $ の順列なので
$ $ $ _{7} C_{5} = 21 $(組)
こんな感じで「仕切りを使う」考え方でも重複組み合わせは求められますが
やはり「公式」を使った方が早く解けてオススメです。
重複組み合わせの見分け方
ここで「重複組み合わせの見分け方」をアドバイスしておきます。
重複組み合わせ $_n H_r $ が使える問題のときは、以下の条件が与えられています。
- 同じものを何回選んでもOK(重複OK)
- $0$ 回のものがあってもOK
逆に言えば、以下のような条件のときは 重複組み合わせでない ということになります。
- 同じものを $1$ 回しか選べない → 組み合わせ
- 選んで並べる(順番を考慮する) → 順列
ただし
というパターンもあるので覚えておきましょう。
これらの見分け方をもとに問題を解いていきましょう!
重複組み合わせの問題(整数解の個数)
さきほどの【例題1、2】は「$0$ 回のものがあってもOK($x≧0, \ y≧0,\ z≧0 $)」という条件だったので純粋な 重複組み合わせ でしたが
次の問題は「どれも少なくとも $1$ 回は選ぶ($x≧1, \ y≧1,\ z≧1 $)」という条件なので工夫がいります。
【例題3】$ x+y+z=8$ をみたす正の整数 $x, \ y, \ z $ の組 $(x, \ y, \ z )$ は、全部で何組あるか。
問題文の「正の整数 $x, \ y, \ z $」より「$ x \color{red}{≧1}, \ y \color{red}{≧1},\ z \color{red}{≧1} $」なので
このままだと重複組み合わせの公式が使えません。
そこで「$ X \color{red}{≧0}, \ Y \color{red}{≧0},\ Z \color{red}{≧0} $」に変形することを考えます。
【解答】
$ $ $ \begin{cases}
x+y+z=8 \\
\\
x≧1 \\
\\
y≧1 \\
\\
z≧1 \\
\end{cases}$ より
$ $ $ \begin{cases}
(x−1)+(y−1)+(z−1)=5 \\
\\
x−1≧0 \\
\\
y−1≧0 \\
\\
z−1≧0 \\
\end{cases}$ ・・・①
また
$ $ $ \begin{cases}
X = x−1 \\
\\
Y = y−1 \\
\\
Z = z−1 \\
\end{cases}$
とすると、① は
$ $ $ \begin{cases}
X+Y+Z=5 \\
\\
X≧0 \\
\\
Y≧0 \\
\\
Z≧0 \\
\end{cases}$
よって、$X, \ Y, \ Z$ の異なる $3$ 種類から 重複を許して $5$ 個選ぶ 組み合わせなので
$ $ $_3 H_{5} = \, _{3+5-1} C_{5} $
$ $ $ = \, _{7} C_{5} $
$ $ $ = \, _{7} C_{2} $
$ $ $ = 21 $(組)
こんな感じで「重複組み合わせの公式」が使える形に持ち込めばラクに解くことができます。
解法パターンとしてしっかり身につけておきましょう!
重複組み合わせの問題【基本】
ここまで学んだことを活かして、実際に 重複組み合わせの問題 をやってみましょう!
【問題1】$x, \ y, \ z$ の $3$ 種類の文字から作られる $5$ 次の項は何通りできるか。
$x, \ y, \ z$ の $3$ 種類の文字から作られる $5$ 次の項というのは、例えば
のように、$x, \ y, \ z$ の $3$ 種類から、重複を許して $5$ 個選んで作ります。
- 【解答】を見る
-
【解答】
$x, \ y, \ z$ の $3$ 種類から、重複を許して $5$ 個選ぶ 組み合わせなので
$ $ $ _3 H_5 = \ _{3+5-1} C_5$
$ $ $ = \ _{7} C_5$
$ $ $ = \ _{7} C_2$
$ $ $ \displaystyle{ = {7 \cdot 6 \over 2 } } $
$ $ $ = 21$(通り)
【問題2】候補者が $3$ 名で、選挙人が $45$ 名いる無記名投票で、$1$ 人 $1$ 票を投票するときの票の分かれ方は何通りあるか。ただし、候補者は投票しない。
例えば、A、B、Cの $3$ 名の候補者がいて、$45$ 名が投票すると
のように、A、B、C の $3$ 名から、重複を許して $45$ 回 選ぶと考えられます。
- 【解答】を見る
-
【解答】
候補者の $3$ 名から、重複を許して $45$ 回選ぶ 組み合わせなので
$ $ $ _3 H_{45} = \ _{3+45-1} C_{45}$
$ $ $ = \ _{47} C_{45} $
$ $ $ = \ _{47} C_2$
$ $ $ \displaystyle{ = {47 \cdot 46 \over 2 } } $
$ $ $ = 1081$(通り)
【問題3】$1$ つのさいころを $2$ 回投げて出た目を順に $a, \ b$ とするとき $a≦b$ となるような目の出方は何通りあるか。
問題文をそのまま読むと
- 1回目:$a$
- 2回目:$b$
- $a≦b$ となる場合を数え上げる
という順番で考えてしまいそうですが、ちょっと大変です。
なので、逆転の発想で
- $1〜6$ の目から、重複を許して $2$ 個えらぶ(例:$1, \ 5$)
- $a≦b$ となるように $a,\ b$ の数を決める(例:$a=1, \ b=5$)
というルールにすれば、ラクに考えられます。
- 【解答】を見る
-
【解答】
$1〜6$ の目から、重複を許して $2$ 個えらんで
$a≦b$ となるように $a,\ b$ の数を決めればよいので
$ $ $ _6 H_{2} = \ _{6+2-1} C_{2}$
$ $ $ = \ _{7} C_{2} $
$ $ $ \displaystyle{ = {7 \cdot 6 \over 2 } } $
$ $ $ = 21$(通り)
以上です。お疲れ様でした!
【まとめ】重複組み合わせの公式
最後に「重複組み合わせの公式」をまとめておきます。
異なる $n$ 種類から、重複を許して $r$ コ選ぶ方法
$ $ $_n H_r = \, _{n+r-1} C_r $
※ 重複 $=$ 同じものを繰り返し用いること
※ $0$ 回のものがあっても(使わない種類があっても)OK
また、整数解 における「重複組み合わせの公式」はこちら。
整数解の「重複組み合わせの公式」
$ x+y+z=r, \ x≧0, \ y≧0,\ z≧0 $ をみたす整数解 $( x, \ y, \ z )$ の個数は
$ $ $_3 H_{r} = \, _{3+r-1} C_{r} $(個)
質問・要望があれば気軽にコメントください👍