重複組み合わせの応用問題を解いておきたい!
重複組み合わせで整数解の個数を求める問題はどんなのがあるの?
解き方をわかりやすく教えてほしい!
こういった要望に応えます。
重複組み合わせの応用問題【整数解の個数】
まずは、整数解 における「重複組み合わせの公式」のおさらいです。
整数解の「重複組み合わせの公式」
$ 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、D の $4$ 種類の商品を、それぞれ $a$ 個、$b$ 個、$c$ 個、$d$ 個、合わせて $10$ 個買うものとする。ただし、$a≧1, $ $ b≧1, $ $c≧1,$ $d≧1$ とする。
(1) 買い方は全部で何通りあるか。
(2) $a=3$ となる買い方は全部で何通りあるか。
(3) $2≦a≦4$ となる買い方は全部で何通りあるか。 [類 近畿大]
(1) 買い方は全部で何通りあるか。
問題文を読んで「重複組み合わせの公式」の形を作りましょう。
- 【解答】を見る
-
【解答】
$ $ $ \begin{cases}
a+b+c+d=10 \\
\\
a≧1 \\
\\
b≧1 \\
\\
c≧1 \\
\\
d≧1 \\
\end{cases}$ より$ $ $ \begin{cases}
(a−1)+(b−1)+(c−1)+(d−1)=6 \\
\\
a−1≧0 \\
\\
b−1≧0 \\
\\
c−1≧0 \\
\\
d−1≧0 \\
\end{cases}$ ・・・①また
$ $ $ \begin{cases}
A = a−1 \\
\\
B = b−1 \\
\\
C = c−1 \\
\\
D = d−1 \\
\end{cases}$とすると、① は
$ $ $ \begin{cases}
A+B+C+D=6 \\
\\
A≧0 \\
\\
B≧0 \\
\\
C≧0 \\
\\
D≧0 \\
\end{cases}$ ・・・②よって、$ A, \ B, \ C, \ D $ の異なる $4$ 種類から 重複を許して $6$ 個選ぶ 組み合わせなので
$ $ $_4 H_{6} = \, _{4+6-1} C_{6} $
$ $ $ = \, _{9} C_{6} $
$ $ $ = \, _{9} C_{3} $ ・・・(注)
$ $ $ \displaystyle{ = \require{cancel} { \displaystyle{ \mathop{ \bcancel{9} }^3 } \cdot \displaystyle{ \mathop{ \cancel{8} }^4 } \cdot 7 \over \bcancel{3} \cdot \cancel{2} } } $
$ $ $ = 84 $(通り)
(注)二項係数の性質
$ $ $ _n C_r = \, _n C_{n-r} $
(2) $a=3$ となる買い方は全部で何通りあるか。
- 【解答】を見る
-
【解答】
$a=3$ のとき $A = 2$
② は
$ $ $ \begin{cases}
B+C+D=4 \\
\\
B≧0 \\
\\
C≧0 \\
\\
D≧0 \\
\end{cases}$よって、$ B, \ C, \ D $ の異なる $3$ 種類から 重複を許して $4$ 個選ぶ 組み合わせなので
$ $ $_3 H_{4} = \, _{3+4-1} C_{4} $
$ $ $ = \, _{6} C_{4} $
$ $ $ = \, _{6} C_{2} $
$ $ $ \displaystyle{ = \require{cancel} { \displaystyle{ \mathop{ \bcancel{6} }^3 } \cdot 5 \over \bcancel{2} } } $
$ $ $ = 15 $(通り)
(3) $2≦a≦4$ となる買い方は全部で何通りあるか。
(2) がヒントになっています。
- 【解答】を見る
-
【解答】
$a=2$ のとき $A = 1$
② は
$ $ $ \begin{cases}
B+C+D=5 \\
\\
B≧0 \\
\\
C≧0 \\
\\
D≧0 \\
\end{cases}$∴ $_3 H_{5} = \, _{3+5-1} C_{5} $
$ $ $ = \, _{7} C_{5} $
$ $ $ = \, _{7} C_{2} $
$ $ $ \displaystyle{ = \require{cancel} { 7 \cdot \displaystyle{ \mathop{ \bcancel{6} }^3 } \over \bcancel{2} } } $
$ $ $ = 21 $(通り)
$a=24$ のとき $A = 3$
② は
$ $ $ \begin{cases}
B+C+D=3 \\
\\
B≧0 \\
\\
C≧0 \\
\\
D≧0 \\
\end{cases}$∴ $_3 H_{3} = \, _{3+3-1} C_{3} $
$ $ $ = \, _{5} C_{3} $
$ $ $ = \, _{5} C_{2} $
$ $ $ \displaystyle{ = \require{cancel} { 5 \cdot \displaystyle{ \mathop{ \bcancel{4} }^2 } \over \bcancel{2} } } $
$ $ $ = 10 $(通り)
したがって、$2≦a≦4$ となる買い方は
$ $ $ 21 + 15 + 10 = 46$(通り)
「重複組み合わせの公式」のパターンにうまく持ち込むことでシンプルな解法になります。
重複組み合わせの応用問題【サイコロの目】
サイコロと「重複組み合わせ」が絡んだ 応用問題 です。
【例題2】$1$ つのさいころを $3$ 回投げて、出た目を順に $a_1, \ a_2, \ a_3$ とする。このとき、$a_1≦a_2≦a_3$ となる目の出方は何通りあるか。
この問題は、先に $a_1≦a_2≦a_3$ となるような $(a_1, \ a_2, \ a_3)$ の組を考えてしまうと、ちょっと大変です。
逆の発想をして、うまく重複組み合わせに持ち込みます。
- 【解答】を見る
-
【解答】
$1〜6$ の目から重複を許して $3$ 個 選んでから
$a_1≦a_2≦a_3$ となるように $a_1, \ a_2, \ a_3$ の数を決めればよいので
$ $ $ _6 H_3 = \, _{6+3-1} C_3 $
$ $ $ = \, _{8} C_3 $
$ $ $ \displaystyle{ = \require{cancel} { 8 \cdot 7 \cdot \bcancel{6} \over \bcancel{3 \cdot 2} } } $
$ $ $ = 56$(通り)
(注)例えば、$1〜6$ の目から「$3, \, 5, \, 1$」と選んだとして
$ $ $a_1≦a_2≦a_3$ となるように
$ $ $(a_1, \ a_2, \ a_3) = (1, \ 3, \ 5) $
$ $ と決める感じです。
重複組み合わせの応用問題【同じものを含む】
次は「同じものを含む 重複組み合わせ」の 応用問題 です。
【例題3】白玉 $5$ 個、赤玉 $3$ 個、黒玉 $2$ 個がある。次のような方法は何通りあるか。
(1) $10$ 個の玉を $6$ 人に分ける方法($1$ 個ももらわない人があってもよい)
(2) $10$ 個の玉を $2$ 組に分ける方法
(3) $10$ 個の玉を $1$ 列に並べる方法
(1) $10$ 個の玉を $6$ 人に分ける方法($1$ 個ももらわない人があってもよい)
一見、重複組み合わせには見えませんが、整理して考えてみると・・・
- 【解答】を見る
-
【解答】
白玉 $5$ 個の分け方は、異なる $6$ 人から 重複を許して $5$ 人選ぶ 組み合わせなので
$ $ $_6 H_{5} $(通り)・・・(注)
同様にして
$ $ 赤玉 $3$ 個の分け方は $_6 H_{3} $(通り)
$ $ 黒玉 $2$ 個の分け方は $_6 H_{2} $(通り)
よって、求める方法は
$ $ $_6 H_{5} × \, _6 H_{3} × \, _6 H_{2} $
$ = \, _{6+5-1} C_{5} × \, _{6+3-1} C_{3} × \, _{6+2-1} C_{2} $
$ = \, _{10} C_{5} × \, _{8} C_{3} × \, _{7} C_{2} $
$ = \displaystyle{ \require{cancel} { \cancel{10}^2 \cdot 9 \cdot \bcancel{8}^2 \cdot 7 \cdot \cancel{6} \over \cancel{5} \cdot \bcancel{4} \cdot \cancel{3 \cdot 2} } × {8 \cdot 7 \cdot \cancel{6} \over \cancel{3 \cdot 2} } × {7 \cdot \cancel{6}^3 \over \cancel{2}} } $
$ = 296352 $(通り)
(注)仮に、$6$ 人のもらう白玉の数をそれぞれ $x_1〜 \, x_6$ とすると
$ $ $ \begin{cases}
x_1+x_2+ \cdots +x_6=5 \\
\\
x_1, \ x_2, \cdots , \ x_6≧0 \\
\end{cases}$整数解 $(x_1, \ x_2, \cdots , \ x_6)$ の個数は
異なる $6$ 種類から 重複を許して $5$ コ選ぶ 組み合わせなので
$ $ $_6 H_{5} $(通り)
(2) $10$ 個の玉を $2$ 組に分ける方法
まずは $A, \ B $ の $2$ 組に分けるとして考えましょう。
- 【解答】を見る
-
【解答】
計 $10$ 個の玉を $A, \ B $ の $2$ 組に分けるとする。
白玉 $5$ 個の分け方は、異なる $2$ 組から 重複を許して $5$ 回選ぶ 組み合わせなので
$ $ $_2 H_{5} $(通り)・・・(注1)
同様にして
$ $ 赤玉 $3$ 個の分け方は $_2 H_{3} $(通り)
$ $ 黒玉 $2$ 個の分け方は $_2 H_{2} $(通り)
よって、計 $10$ 個の玉を $A, \ B $ の $2$ 組に分ける方法は
$ $ $_2 H_{5} × \, _2 H_{3} × \, _2 H_{2} $
$ = \, _{2+5-1} C_{5} × \, _{2+3-1} C_{3} × \, _{2+2-1} C_{2} $
$ = \, _{6} C_{5} × \, _{4} C_{3} × \, _{3} C_{2} $
$ = \, _{6} C_{1} × \, _{4} C_{1} × \, _{3} C_{1} $
$ = 6 × 4 × 3 $
$ = 72 $(通り)
このうち、$A$ 組だけ、$B$ 組だけに分ける $2$ 通りが含まれるので
$ $ $72−2=70$(通り)
さらに、$A, \ B$ 組の区別を無くして
$ $ $ \displaystyle{ {70 \over 2} = 35 } $(通り) ・・・(注2)
(注1)仮に、$A, \ B $ の $2$ 組に分ける白玉の数をそれぞれ $a, \ b$ とすると
$ $ $ \begin{cases}
a+b=5 \\
\\
a, \ b≧0 \\
\end{cases}$整数解 $(a, \ b)$ の個数は
異なる $2$ 種類から 重複を許して $5$ コ選ぶ 組み合わせなので
$ $ $_2 H_{5} $(通り)
(注2)分けずに一気に書くと
$ $ $ \displaystyle{ {_2 H_{5} × \, _2 H_{3} × \, _2 H_{2} − 2 \over 2} = 35 } $(通り)
(3) $10$ 個の玉を $1$ 列に並べる方法
この問題は「同じものを含む順列」です。
重複組み合わせの問題ではありませんが、比較のために解いておきましょう。
- 【解答】 を見る
-
【解答】
白玉 $5$ 個、赤玉 $3$ 個、黒玉 $2$ 個(計 $10$ 個)を $1$ 列に並べる方法は
$ $ $ \displaystyle{ {10! \over 5! \, 3! \, 2!} } $
$ \displaystyle{ = \require{cancel} {10 \cdot 9 \cdot \bcancel{8}^4 \cdot 7 \cdot \cancel{6} \cdot \bcancel{5!} \over \bcancel{5!} \, \cancel{3!} \, \bcancel{2!} } }$
$ = 2520 $(通り)
以上です。お疲れ様でした!
質問・要望があれば気軽にコメントください👍