本項では以下の内容を解説しています。
重複組み合わせとは、異なる種類のものから同じものを何回でも選ぶことを許して取る組み合わせのことです。
重複組み合わせの例として \(\large{\rm{\hspace{1pt}A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{1pt}}}\) の\(\large{\hspace{1pt}3\hspace{1pt}}\)つの文字から重複を許して選ぶ組み合わせの数を求める問題について考えます。
例題のように\(\large{\hspace{1pt}3\hspace{2pt}}\)種類のものから\(\large{\hspace{1pt}5\hspace{2pt}}\)個を重複を許して選ぶ組み合わせを求めるとき、取り出した文字を左から順に\(\large{\rm{\hspace{1pt}A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{1pt}}}\)の順に並べるとします。 \begin{eqnarray} &&\large \rm{A\hspace{2pt}B\hspace{2pt}B\hspace{2pt}B\hspace{2pt}C} \\[0.7em] &&\large \rm{A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}B\hspace{2pt}C} \\[0.7em] &&\large \rm{A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}A} \\[0.7em] &&\large \cdots \hspace{3pt}\cdots\hspace{3pt}\cdots\\[0.7em] \end{eqnarray}
このとき、上記の文字の並びを\(\large{\hspace{1pt}5\hspace{1pt}}\)つの『\(\large{\hspace{1pt}〇\hspace{1pt}}\)』と\(\large{\hspace{1pt}2\hspace{1pt}}\)つの仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を使用して、\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切りに区切られた左側を\(\large{\hspace{1pt}A\hspace{1pt}}\)、真ん中を\(\large{\hspace{1pt}B\hspace{1pt}}\)、右側を\(\large{\hspace{1pt}C\hspace{1pt}}\)と対応させます。 \begin{eqnarray} \large \rm{A\hspace{2pt}B\hspace{2pt}B\hspace{2pt}B\hspace{2pt}C}& \large \rightarrow & \large 〇\hspace{1pt}|\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}|\hspace{1pt}〇\\[0.7em] \large \rm{A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}B\hspace{2pt}C}& \large \rightarrow & \large 〇\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}|\hspace{1pt}〇\hspace{1pt}|\hspace{1pt}〇\\[0.7em] \large \rm{A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}A\hspace{2pt}A} & \large \rightarrow & \large 〇\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}〇\hspace{1pt}|\hspace{1pt}| \\[0.7em] \end{eqnarray}
このように対応させることで、\(\large{\hspace{1pt}3\hspace{2pt}}\)種類のものから重複を許して\(\large{\hspace{1pt}5\hspace{2pt}}\)個選ぶ組み合わせを、\(\large{\hspace{1pt}5\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の『\(\large{\hspace{1pt}|\hspace{2pt}}\)』の同じものを含む順列に変換して計算できます。
同じものを含む順列の公式から、\(\large{\hspace{1pt}5\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の『\(\large{\hspace{1pt}|\hspace{2pt}}\)』の順列の数は $$\large{\frac{7\hspace{1pt}!}{5\hspace{1pt}!\hspace{1pt}2\hspace{1pt}!} = 21}$$ したがって、\(\large{\hspace{1pt}21\hspace{1pt}}\)通りとなります。
もしくは、\(\large{\hspace{1pt}7\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}5\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}2\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_7 C_5 \times {}_2 C_2 & \large = & \large \frac{ {}_7 P_5}{5\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 21\\[0.7em] \end{eqnarray} したがって、\(\large{\hspace{1pt}21\hspace{1pt}}\)通りと求めることもできます。
一般的には、異なる\(\large{\hspace{1pt}n\hspace{2pt}}\)個のものから重複を許して\(\large{\hspace{1pt}r\hspace{2pt}}\)個を取り出す組み合わせの総数は以下の公式で表されます。
もしくは組み合わせの記号\(\large{\hspace{1pt}C\hspace{2pt}}\)を用いると以下のように書き表されます。
本章では、同じものを含む順列に関連する問題と解き方について解説します。
解答と解説 : 問題1
解答と解説 : 問題2
解答と解説 : 問題3
解答と解説 : 問題4
解答と解説 : 問題5
\(\large{\hspace{1pt}4\hspace{1pt}}\)つの種類の重複組み合わせを求める場合は、\(\large{\hspace{1pt}6\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}3\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を並べ、\(\large{\hspace{1pt}3\hspace{2pt}}\)個の仕切りに対して左側から\(\large{\hspace{1pt}\rm{A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{1pt},\hspace{1pt}D\hspace{2pt}}\hspace{1pt}}\)と割り振ると考えます。
つまり、\(\large{\hspace{1pt}6\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}3\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』の順列の総数は $$\large{\frac{9\hspace{1pt}!}{6\hspace{1pt}!\hspace{1pt}3\hspace{1pt}!} = 84}$$ したがって、\(\large{\hspace{1pt}84\hspace{1pt}}\)通りとなります。
もしくは、\(\large{\hspace{1pt}9\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}6\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}3\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_9 C_6 \times {}_3 C_3 & \large = & \large \frac{ {}_9 P_6}{6\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 84\\[0.7em] \end{eqnarray} したがって、\(\large{\hspace{1pt}84\hspace{1pt}}\)通りとも求められます。
まず、\(\large{\hspace{1pt}\rm{A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{2pt}}}\)の文字を\(\large{\hspace{1pt}1\hspace{1pt}}\)つずつ選んだとします。
残りの\(\large{\hspace{1pt}3\hspace{1pt}}\)個の選び方は、\(\large{\hspace{1pt}3\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』の順列の数を求めればよいため $$\large{\frac{5\hspace{1pt}!}{3\hspace{1pt}!\hspace{1pt}2\hspace{1pt}!} = 10}$$ したがって、\(\large{\hspace{1pt}10\hspace{1pt}}\)通りとなります。
もしくは、\(\large{\hspace{1pt}5\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}3\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}2\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_5 C_3 \times {}_2 C_2 & \large = & \large \frac{ {}_5 P_3}{3\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 10\\[0.7em] \end{eqnarray} したがって、\(\large{\hspace{1pt}10\hspace{1pt}}\)通りとも求められます。
ボールを渡す\(\large{\hspace{1pt}3\hspace{1pt}}\)人にそれぞれ\(\large{\hspace{1pt}A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{2pt}}\)と名前を付けます。
まず、\(\large{1\hspace{1pt}}\)人につき少なくとも\(\large{\hspace{1pt}1\hspace{1pt}}\)個のボールは渡すという条件から、\(\large{\hspace{1pt}A\hspace{1pt},\hspace{1pt}B\hspace{1pt},\hspace{1pt}C\hspace{2pt}}\)それぞれに先にボールが\(\large{\hspace{1pt}1\hspace{1pt}}\)個ずつ渡されているとします。
残りのボールの渡し方は、\(\large{\hspace{1pt}6\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を考えて、\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切りの左側を\(\large{\hspace{1pt}A\hspace{1pt}}\)、真ん中を\(\large{\hspace{1pt}B\hspace{1pt}}\)、右側を\(\large{\hspace{1pt}C\hspace{2pt}}\)に渡す数とします。
つまり、\(\large{\hspace{1pt}6\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を順列の数を求めることでボールの渡し方を求めます。
重複組み合わせの公式から $$\large{\frac{8\hspace{1pt}!}{6\hspace{1pt}!\hspace{1pt}2\hspace{1pt}!} = 28}$$ したがって、ボールの渡し方は\(\large{\hspace{1pt}28\hspace{1pt}}\)通りとなります。
もしくは、\(\large{\hspace{1pt}8\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}6\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}2\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_8 C_6 \times {}_2 C_2 & \large = & \large \frac{ {}_8 P_6}{6\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 28\\[0.7em] \end{eqnarray} したがって、\(\large{\hspace{1pt}28\hspace{1pt}}\)通りとも求められます。
問題のような整数の組を求める問題は、重複組み合わせの考え方で解くことができます。
\(\large{\hspace{1pt}8\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』に対して、左側から順番に\(\large{\hspace{1pt}x\hspace{1pt},\hspace{1pt}y\hspace{1pt},\hspace{1pt}z\hspace{2pt}}\)として割り振り、順列の数を求めることで整数の組の数を求められます。 $$\large{\frac{10\hspace{1pt}!}{8\hspace{1pt}!\hspace{1pt}2\hspace{1pt}!} = 45}$$ したがって、整数の組は\(\large{\hspace{1pt}45\hspace{1pt}}\)個となります。
もしくは、\(\large{\hspace{1pt}10\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}8\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}2\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_{10} C_8 \times {}_2 C_2 & \large = & \large \frac{ {}_{10} P_8}{8\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 45\\[0.7em] \end{eqnarray} したがって、整数の組は\(\large{\hspace{1pt}45\hspace{1pt}}\)個とも求められます。
問題\(\large{\hspace{1pt}4\hspace{2pt}}\)と同様に、重複組み合わせの考え方で解くことができます。
\(\large{\hspace{1pt}x\geqq 1\hspace{1pt},\hspace{2pt}y\geqq 1\hspace{1pt},\hspace{2pt}z\geqq 1\hspace{1pt}}\)という条件から、問題\(\large{\hspace{1pt}4\hspace{2pt}}\)の\(\large{\hspace{1pt}8\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』のうち、\(\large{\hspace{1pt}3\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』がすでに\(\large{\hspace{1pt}x\hspace{1pt},\hspace{1pt}y\hspace{1pt},\hspace{1pt}z\hspace{2pt}}\)に\(\large{\hspace{1pt}1\hspace{1pt}}\)つずつ割り振られていると考えます。
つまり、問題\(\large{\hspace{1pt}5\hspace{2pt}}\)は\(\large{\hspace{1pt}5\hspace{2pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』と\(\large{\hspace{1pt}2\hspace{2pt}}\)個の仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を一列に並べる順列の数を求めればよいことになります。
順列の数は $$\large{\frac{7\hspace{1pt}!}{5\hspace{1pt}!\hspace{1pt}2\hspace{1pt}!} = 21}$$ と求められます。したがって、整数の組は\(\large{\hspace{1pt}21\hspace{1pt}}\)個となります。
もしくは、\(\large{\hspace{1pt}7\hspace{1pt}}\)個の場所から\(\large{\hspace{1pt}5\hspace{1pt}}\)個の『\(\large{\hspace{1pt}〇\hspace{2pt}}\)』の場所を選び、残りの\(\large{\hspace{1pt}2\hspace{1pt}}\)箇所に仕切り『\(\large{\hspace{1pt}|\hspace{2pt}}\)』を入れると考えると \begin{eqnarray} \large {}_7 C_5 \times {}_2 C_2 & \large = & \large \frac{ {}_7 P_5}{5\hspace{1pt}! }\times 1 \\[0.7em] \large & \large = & \large 21\\[0.7em] \end{eqnarray} したがって、整数の組は\(\large{\hspace{1pt}21\hspace{1pt}}\)個とも求められます。