今回は、重複組合せを利用して、方程式の整数解の総数を求める問題について解説します。
方程式の整数解の総数
方程式の整数解の総数は重複組合せを利用して求めることができます。重複組合せについては以下の記事で解説しています。
上の重複組合せの記事において、以下の問題を扱いました。
区別のない6個の玉をA，B，Cの3箱に分ける方法は何通りあるか。ただし、空箱があっても良いものとする。
この例題において、\(x=\)（箱Aの玉の個数）、\(y=\)（箱Bの玉の個数）、\(z=\)（箱Cの玉の個数）とおくと、
$$ x+y+z = 6，x \geq 0，y \geq 0，z \geq 0 $$
を満たす整数の組合せ \( (x，y，z) \)の総数を求めていることになります。このように、入試では、重複組合せを利用して、整数解の総数を求める問題を求めることができます。
仕切りを入れて考える
重複組合せは仕切りを入れて考えるのでした。次の例題を考えてみましょう。
\( x+y+z = 6，x \geq 0，y \geq 0，z \geq 0 \) を満たす整数 \(x\)，\(y\)，\(z\) の組は全部で何通りあるか。
前回と同様に重複組合せでは、◯（マル）と｜（仕切り）を使って考えます。今回は総数が6なので、◯の個数は6つです。登場する文字数は3種類なので、文字の変わり目は2つとなるため、｜は2つとなります。あとは◯と｜について、同じものを含む順列で考え、一番左が \(x\)、真ん中が \(y\)、一番左が \(z\)として割り当てて考えれば、\(x\)，\(y\)，\(z\) のに対応させて考えることができます。
たとえば、◯と｜を
◯◯◯｜◯◯｜◯
と配置した場合、 \( (x，y，z)=(3，2，1) \)と対応させて考えることができます。
同様に、
◯｜◯◯◯｜◯◯ ↔︎ \( (x，y，z)=(1，3，2) \)
◯◯｜｜◯◯◯◯ ↔︎ \( (x，y，z)=(2，0，4) \)
◯◯◯◯◯◯｜｜ ↔︎ \( (x，y，z)=(6，0，0) \)
と対応させて考えることができます。よって、\( (x，y，z) \) 組合せの総数は◯と｜の同じものを含む順列として考えることができるので、求める答えは
\( {}_8 \mathrm{C}_2 = 28 \) （通り）となります。
以上のように、重複組合せは図と対応させて考えます。
例題と演習
では、例題を見ていきます。
例題：重複組合せ
（1）\( x+y+z = 9，x \geq 0，y \geq 0，z \geq 0 \) を満たす整数 \(x\)，\(y\)，\(z\) の組は全部で何通りあるか。
（2）\( x+y+z = 9，x \geq 1，y \geq 1，z \geq 1 \) を満たす整数 \(x\)，\(y\)，\(z\) の組は全部で何通りあるか。
方針
（1）9個の◯と2個の｜による順列で考える。
（2）求めるものは、（1）の総数のうち、｜が両端に来ず、｜が隣り合わない順列の総数である。まず、9個の◯を並べる。次に、2個の｜をすき間に入れる。9個の◯は区別をすることができないので、9個の◯の並べ方は1通りしかありません。一方で、2個の｜のすき間の入れ方は\( {}_8 \mathrm{C}_2 \)（通り）になります。
（1）9個の◯と2個の｜による順列の総数に帰着されるので、
\( {}_11 \mathrm{C}_2 = 55 \)（通り）
（2）求めるものは、9個の◯と2個の｜の順列のうち、｜が両端に来ず、｜が隣り合わない順列の総数である。これは、まず、9個の◯を並べ、2個の｜をすき間に入れることを考えると、
\( {}_8 \mathrm{C}_2 = 28 \)（通り）
（2）には別解もあるので、以下の別解についても理解しましょう。
方針：（2）別解
（2）はじめに、 \(x\)，\(y\)，\(z\) に1を配っておき、次に、残りの6を \(x\)，\(y\)，\(z\) に分配すれば良い。よって、\(X=x-1\)、\(Y=y-1\)、\(Z=z-1\) とおくと、以下の条件を満たす整数の組の総数を求めればよい。
$$ X+Y+Z = 6，X \geq 0，Y \geq 0，Z \geq 0 $$
（2）\(X=x-1\)、\(Y=y-1\)、\(Z=z-1\) とおくと、以下の条件を満たす整数の組の総数を求めればよい。
$$ X+Y+Z = 6，X \geq 0，Y \geq 0，Z \geq 0 $$
6個の◯と2個の｜による順列の総数に帰着されるので、
\( {}_8 \mathrm{C}_2 = 28 \)（通り）
演習：重複組合せ
（1）\( a+b+c+d = 7，a \geq 0，b \geq 0，c \geq 0，d \geq 0 \) を満たす整数 \(a\)，\(b\)，\(c\)，\(d\) の組は全部で何通りあるか。
（2）\( a+b+c+d = 18，a \geq 8，b \geq 4，c \geq 2，d \geq 0 \) を満たす整数 \(a\)，\(b\)，\(c\)，\(d\) の組は全部で何通りあるか。
おわりに
以上が重複組合せの考え方になります。重複組合せの一番難しいところは、重複組合せの問題を重複組合せと気づくことです。このことについては次回の記事で扱います。
最後までお読みいただき、ありがとうございました。
