【応用】指定した合計値になる整数の組合せ
ここでは、「指定した合計値になる整数の組合せがいくつあるか」を数える問題を考えます。例えば、「0以上の整数を3つ足して5になる組合せは？」という問題です。【応用】重複組合せで使った考え方を応用するので、見ていない人は事前に見ておきましょう。
指定した合計値になる整数の組合せ
例えば、 $x=5$ なら、 $y=z=0$ だけですね。 $x=4$ なら $y=1,z=0$ か、 $y=0, z=1$ の2通りです。同様に考えていくと、 $x=3$ のときは3通り、 $x=2$ のときは4通り、 $x=1$ のときは5通り、 $x=0$ のときは6通りです。以上から\[ 1+2+3+4+5+6=21 \]通りとなります。
この流れ、実は【応用】重複組合せ#カードが1種類増えるとどうなるかで見た内容とほぼ同じなんですね。そこでは、もっと簡単な方法を見ました。その方法をここでも適用してみましょう。
合計が5だと決まっているので、〇を5つ用意します。そこに区切り | を2つ入れ、区切りの左にある〇の数を x、真ん中にある〇の数を y 、右にある〇の数を z とすれば、「〇と| の並べ方」と「x, y, z の組」とが対応します。例えば、次のような対応になります。
「〇〇〇〇〇|| ⇔ $x=5$, $y=0$, $z=0$ 」
「〇〇〇|〇〇| ⇔ $x=3$, $y=2$, $z=0$ 」
「〇|〇|〇〇〇 ⇔ $x=1$, $y=1$, $z=3$ 」
「|〇〇|〇〇〇 ⇔ $x=0$, $y=2$, $z=3$ 」
「||〇〇〇〇〇 ⇔ $x=0$, $y=0$, $z=5$ 」
この対応には、モレやダブりがありません。「〇と| の並べ方」には必ず対応する「x, y, z の組」があり、逆もそうです。また、異なる「〇と| の並べ方」に対して、同じ「x, y, z の組」が対応することはありませんし、逆に、異なる「x, y, z の組」に対して、同じ「〇と| の並べ方」が対応することもありません。
よって、5つの〇と2つの|を並べる方法を数えれば答えになるので、\[ {}_7 \mathrm{ C }_2 =21 \]通りとなります。上と同じ答えですね。
このように、合計分の〇と、変数引く1の数だけ用意した区切り|とを並べる方法に対応させると、数えやすくなります。
指定した合計値になる自然数の組合せ
「0以上の整数」が「自然数」になりました。これにより、先ほどの例題1と違って、0を含む答えをのぞく必要が出てきます。
0を含むものを数えて引く方法も、もちろんあります。3つが0になることはないので、0になるとすれば2つか1つです。
2つが0になる場合、残りが5となるしかありません。どれが5になるかが3通りあります。
0になるのが1つの場合、残りの2つは0以外なので、「1,4」「2,3」「3,2」「4,1」となります。0になるものの選び方が3通り、それぞれに対して、残り2つの決め方が4通りあるので、12通りあります。
以上から、\[ 21-3-12=6 \]通り、と求めることができます。
しかし、実はもっと簡単に求めることができます。無理やり例題1の形に持っていくやり方です。
自然数を「1+(0以上の整数)」と考えるわけです。つまり、 $x'=x-1$, $y'=y-1$, $z'=z-1$ とすると、 $x',y',z'$ は0以上の整数です。また、
\begin{eqnarray}
x'+y'+z'
&=&
x-1+y-1+z-1 \\
&=&
5-3=2
\end{eqnarray}
となります。つまり、0以上の整数を3つ足して2となる組合せを考えればよくなるわけですね。
これなら、例題1と同じように数えることができます。 $x',y',z'$ の合計は2なので、〇を2つ、変数が3つなので、|を2つ、合わせて4つを並べる方法を考えればいいので\[ {}_4 \mathrm{ C }_2 =6 \]通りとなります。上の答えと合っていますね。
自然数の場合は、1引いて、0以上の整数として考えることがポイントです。
指定した合計値以下になる整数の組合せ
今後は合計値が5ではなく、5「以下」となったバージョンです。素直に考えれば、合計値が、0の場合、1の場合、…、5の場合を考えて、全部足すことになります。しかし、めんどくさいです。これも例題1の形に帰着させます。
合計が5でないからめんどうなんですよね。なので、無理やり5にすることを考えます。つまり、0以上の整数 a を足して5となるようにするわけです。
$a=5-(x+y+z)$ とすると、 a は0以上の整数になります。よって\[ x+y+z+a=5 \]となる、0以上の整数 x, y, z, a の組を考えればいいわけです。最後に a を取り除けば、欲しい x, y, z の組が得られます。 a を除いても、 x, y, z の組がダブることはありません。「和が違う」または「和が同じだがどれかの値が違う」のどちらかだからです。
合計が5で、変数の数が4なので、5つの〇と3つの|の8個を並べる方法を考えればよく、\[ {}_8 \mathrm{ C }_3 =56 \]通り、と求められます。
おわりに
ここでは、指定した合計値となる整数の組合せを考えました。〇と|の並び替えに帰着させると、簡単に計算できるようになりましたね。ただ、発想は少し難しいので、よく理解しましょう。
