組合せと数列 | 教えて数学理科

条件を満たす組の個数を数える例題です。

(例題)
(1)方程式 \(x+y+z=28\) をみたす負でない整数の組 (\(x,y,z\)) の個数を求めよ。また、その中で\(z\)が偶数である場合の個数を求めよ。

(2)いくつかの\(10\)円玉、\(50\)円玉、\(100\)円玉を用いて\(1400\)円をつくりたい。このつくり方の総数を求めよ。ただし用いる個数は\(0\)個でもよい。

(解答)
(1)

重複組合せ(仕切りと〇の並べ方)を考えても解けますが、せっかくなので数列の和を利用して解いていきます。\(x+y+z=28\) について、例えば \(z=5\) とすれば \(x+y=23\) となりますが、\(x\)のパターンとしては \(x=0,1,2,\cdots,23\) であり、この\(x\)の値それぞれに対して\(y\)は1通りに決定します。その他の\(z\)についても同様の議論になるので、\(z=k\) として進めていきます。\(k\)の範囲は\(x,y,z\)が負でない整数なので、\(0≦k≦28\) です。

(前半部分)
\(x+y+z=28\) において
\(z=k\)　(\(k=0,1,2,\cdots,28\)) とおくと

\(x+y=28-k\)

この方程式において\(x,y\)の組は
\((0,28-k),(1,27-k),(2,26-k),\cdots,(28-k,0)\)
であるから、全部で \((28-k+1)\) 通り。

\(k\)を固定した場合には、\(29-k\) 通りになります。実際には\(k\)は \(0≦k≦28\) の値をとるので、それぞれの\(k\)についての和が答えとなります。

よって組 (\(x,y,z\)) の個数は
\(\displaystyle\sum_{k=0}^{28}(29-k)\)

\(k=1\)スタートと分けて公式を使ってもよいですが、等差数列になっていることに着目して求めていきます。

\(=29+28+27+\cdots+1\)
\(=\displaystyle\frac{1}{2}\cdot29(29+1)\)
\(=435\)

(後半部分)

今度は\(z\)が偶数なので、\(z=2l\) とおいて処理していきます。\(l\)の範囲は \(0≦2l≦28\) より、\(0≦l≦14\) です。

\(x+y+z=28\) において
\(z=2l\)　(\(l=0,1,2,\cdots,14\)) とおくと

\(x+y=28-2l\)

この方程式において\(x,y\)の組は
\((0,28-2l),(1,27-2l),(2,26-2l),\cdots,(28-2l,0)\)
であるから、全部で \((28-2l+1)\) 通り。

よって組 (\(x,y,z\)) の個数は
\(\displaystyle\sum_{l=0}^{14}(29-2l)\)
\(=29+27+25+\cdots+1\)

(項数が\(15\)の等差数列だから)

\(=\displaystyle\frac{1}{2}\cdot15(1+29)\)

\(=225\)

(2)

\(10a+50b+100c=1400\) として、同じように進めていきます。両辺を\(10\)で割ると
\(a+5b+10c=140\) で固定する文字は係数が大きいものを選びます。何故かというと例えば \(a=1\) とすると、残りは全部\(5\)の倍数となっているために\(b,c\)が整数でとれなくなり面倒なことになるからです。それとこの問題だと\(c\)の係数が一番大きいですが、\(c\)の範囲が \(0≦c≦14\) と一番狭くなり処理が楽になるからです。
なお(1)を利用する別解もあります。

\(10\)円玉、\(50\)円玉、\(100\)円玉の選ぶ個数を\(a,b,c\)とすると

\(10a+50b+100c=1400\)
よって
\(a+5b+10c=140\)

\(c=m\)　(\(m=0,1,2,\cdots,14\)) とすると

\(a+5b=140-10m\)・・・①

今度は\(b\)を決定(固定)すると、\(a\)の係数が\(1\)なので必ず\(a\)は整数となります。具体例で挙げると、\(m=2\) のとき \(a+5b=120\) であり、\(b=3\) とすると、\(a=105\) です。\(m,b\)が整数である限り\(a\)は整数になるわけです。あとは\(0\)以上になることに気をつけます。

\(a=140-10m-5b\) より、\(m,b\)が整数ならば\(a\)も整数で、\(a,b\)は負でないから

\(b≧0\),　\(140-10m-5b≧0\)
より
\(0≦b≦28-2m\)

よって
\(a+5b=140-10m\)・・・①
を満たす\(a,b\)の組は
\((140-10m,0),(135-10m,1),(130-10m,2),\cdots,(0,28-2m)\)
だから、全部で \((28-2m+1)\) 個。

したがって\(a,b,c\)の組の個数は
\(\displaystyle\sum_{m=0}^{14}(29-2m)\) ((1)の後半部分と同じ)

\(=225\)　

(別解)

\(10a+50b+100c=1400\) で右辺が\(28\)になるように割ります。

\(10a+50b+100c=1400\) の両辺を\(50\)で割ると

\(\displaystyle\frac{a}{5}+b+2c=28\)・・・(i)

\(b\)は整数、\(2c\)は偶数になるので(1)の後半部分が利用できそうです。
\(a\)については分数になっていますが、\(b,c\)が整数だと \(\displaystyle\frac{a}{5}\) は整数でそれを\(n\)とおくと、\(\displaystyle\frac{a}{5}=n\) より \(a=5n\) だから\(a\)もちゃんと整数になります。

\(b,c\)が整数のとき、(i)より\(\displaystyle\frac{a}{5}\) も整数となるから

\(\displaystyle\frac{a}{5}=x\), \(b=y\),　\(2c=z\) とおくと

\(x+y+z=28\)

であり、負でない整数\(x,y\)をそれぞれ1つ定めると、負でない整数\(a,b\)が1つ定まり、負でない偶数\(z\)を1つ定めると、負でない整数\(c\)が1つ定まる。したがって

\(x+y+z=28\)　(ただし \(x,y\)は負でない整数、\(z\)は負でない偶数)

を満たす\(x,y,z\)の組の個数が求める個数だから(1)の後半部分から
\(225\)個

以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。
next→シグマとnCr　back→格子点の数