\(\displaystyle a+b+c=9\)
を満たす自然数
\(\displaystyle a,b,c\)
を全て求めよ。
これは、自然数9を複数の自然数の和に分割する方法をすべて求める問題です。
自然数の分割問題
素因数分解は自然数を積の形に分解します。
積で分解する方法は順番を無視すると一意に定まります。これが素因数分解の一意性と呼ばれる性質です。
それに対して、一般に自然数を自然数の和で分割する方法は幾通りもあります。
分割の方法は一意ではありませんが、しかし無限に分割する方法があるわけではありません。
そこで、何通りの分割の方法があるのか数えてみようというのがここでの分割問題です。
単に分割するといっても、いろいろな分割の方法がありますが、ここではある自然数を三つの自然数の和に分割する問題を考えます。
なお、一般に分割の問題では、分割の順番を考えませんが、ここでは順序も考えて分割の個数を数えます。
つまりここでは、９＝２＋３＋４という分割と、９＝３＋４＋２という分割ば別の分割であると考えて分割の個数を数えることになります。
この考え方で分割を考えると、
例えば、自然数9を3つの自然数に分割する方法は、
\(\displaystyle a+b+c=9\)
を満たす自然数 \(\displaystyle a,b,c\) の解の個数と同じになります。
9を三つの自然数に分割する方法は28通り
最初に、答えを書いておきます。
９を三つの自然数に分割する方法は、次の式で計算できます。
\(\displaystyle \frac{8*7}{2*1}=28\)
と計算できて、答えの28通りが得られます。
実際、解を(a,b,c)の形で列挙すると
(7,1,1)
(6,2,1)
(6,1,2)
(5,3,1)
(5,2,2)
(5,1,3)
(4,4,1)
(4,3,2)
(4,2,3)
(4,1,4)
(3,5,1)
(3,4,2)
(3,3,3)
(3,2,4)
(3,1,5)
(2,6,1)
(2,5,2)
(2,4,3)
(2,3,4)
(2,2,5)
(2,1,6)
(1,7,1)
(1,6,2)
(1,5,3)
(1,4,4)
(1,3,5)
(1,2,6)
(1,1,7)
と実際に28組の解があることが確認できます。
上記の解はある規則に並べて表示していますので、この規則からも解の個数を数えることができます。
\(a\)の値でグルーピングすると、\(a=7\)の場合は1組、\(a=6\)の場合は2組、・・・、\(a=1\)の場合は7組の解がありますから、全ての解の個数は、
\(1+2+3+4+5+6+7\)で計算できることがわかります。
この規則をもとに、もっと一般に自然数\(n\)を３つの自然数に分割する個数も以下のように計算できます。
\(n=9\)の例で考察した考えを一般化すると、
\(1+2+3+\cdots +(n-2)\)の計算結果が個数となります。
これは、数列の和の公式が適用でき、
\(\displaystyle \frac{(n-1)(n-2)}{2}\)
といった計算式になります。
組合せの考えから整数解の個数を数える
3つの自然数に分割する方法の個数の計算式は解をうまくグルーピングすることで得られましたが、一歩発展させて、4つの自然数に分割する方法の個数を考えると、ちょっと複雑な計算式になります。
問題は再帰的な構造を持っていますので、計算できなくはありません。
しかし、組合せの考え方でアプローチすると、この問題をもっと簡単に解くことができます。
そのために、問題をすこし変形します。
まず、ゼロは自然数としては扱っていませんが、解にゼロも許すことで問題が考えやすくなるため、ゼロ以上の整数で解を求めます。
先ほどの例で考えると、
\(\displaystyle a+b+c=9\)を満たす0以上の整数の解の個数を求めることを考えます。
0も含むため、
(a,b,c)=(9,0,0)等も
解として含めて数えることになります。
組合せの問題にする
どういった組合せの問題にするのかというと、９個の○と３個の箱があったとし、まるを３個の箱に分割する方法です。
不定方程式a+b+c=9を満たすゼロ以上の整数解a,b,cは、
9個の○を３個の箱に入れる方法に対応する。
3個の箱をここではA,B,Cと名付けます。
解にゼロも許すというのは、空箱も許すということです。
空箱を許すことで数えやすくなります。
箱に入れた状態を次の記号で表すことにします。
例えば、
○○|○|○○○○○○
のように○の間に仕切り|を２つ挿入して表します。
仕切りで区切られた○の数を数えると
2,1,6となりますが、これはAの箱に２個、Bの箱に１個、Cの箱に６個○を入れたことを表しています。
この表し方と箱に○を入れる方法がうまく対応つきます。
この対応つけこそが組合せで考えるときのポイントです。
なにか、別の数えやすいものにうまく対応つけていくことで、数えにくかったものが数えやすくなるのです。
この対応を考えると、○を箱に入れる方法は、すべて９個の○と２個の仕切り|の組合せでできる文字列と一対一に対応します。
さらに、９個の○と２個の|を並べる方法が組み合わ論で求めることができます。
すなわち、○を箱に入れる方法は組合せ論で求められるというわけです。
組合せ問題の表現方法
９個の○と２個の|からなる文字列は、11文字の長さの文字列です。
これらば、11文字のどこの位置に|をいれるかで区別されます。
例えば、
○○|○|○○○○○○
は、3文字目と5文字目に|を挿入し、残りを○にした文字列と考えることができます。
ということは、11のポジジョンの中から二つのポジションを選ぶ方法で文字列を表すことができます。
これは、１１個から２個を選ぶ組合せとなります。
組合せ論でこれは、\(\displaystyle {}_{11}C_{2} \)となります。
３個の箱に○を入れる場合は、２個の仕切りを考えることに置き換わりました。
なお、||○○○○○○○○○
のような文字列は、Aの箱とBの箱は空の状態に対応します。
このような文字列も含めて考えたいので空箱も許しています。
すなわちゼロも解として含めて考えています。
まとめますと、
９個の○と２個の|からなる文字列は、空箱もゆるした３つの箱に９個の○を入れる方法と対応つきます。
そして、その箱の○の数をそれぞれ\(a,b,c\)個とすると
\(a+b+c=9\)を満たす不定方程式のゼロ以上の整数解に対応します。
これは逆にみると、\(a+b+c=9\)を満たす解(a,b,c)は、○を箱に入れる方法で表すことができるということです。
4個の分割に発展させる
この考え方を少し発展させると、４個の箱に○を入れる場合は、3個の仕切りで考えればよいことがわかります。
この場合、９個の○を４個の箱に分割する方法は、９個の○と３個の|の文字列に対応します。
ですから、その分割の個数は\(\displaystyle {}_{12}C_{3}\)で計算できます。
なお、|の個数が増えることであえ、全体の文字列が12文字に伸びていることを注意してください。
\(a+b+c+d=9\)を満たす解(a,b,c,d)の個数は、\(\displaystyle {}_{12}C_{3}\)個というわけです。
この考え方でいくと、５個に分割する方法、６個に分割する方法も組み合わせ式で表すことができます。
\(\displaystyle {}_{12}C_{3}=220\)ですので、９を４個のゼロ以上の整数に分割する方法は、220通りとなります。
ゼロも許しているせいもあり、分割する方法が220通りと多く、ちょっと列挙しきれません。
||○○○○○○○○○
|○|○○○○○○○○
|○○|○○○○○○○
…
と並べていけば人力でも列挙できないわけではないですが、かなり長くまた退屈です。
さて、今はゼロ（空箱）も許容して○の入れ方を考えましたが、次のようにするとそれぞれの箱に１個以上いれる制約をつけても問題はそう変わりません。
それは、９個の○のうち３個をそれぞれのA,B,Cの箱に１個ずついれておくのです。
これでA,B,Cは少なくとも１個の○がはいった状態になります。
すでにそれぞれの箱に１個の○が入っていますが、いったんその１個の○を覆い隠して、A,B,Cは空箱とみなします。
この状態で残りの６個の○を箱A,B,Cに入れる方法を考えますと、６個の○を３個の箱にみなし空箱も許して入れる方法ですから、分割の公式が使えます。
6個の○と2個の|の並べ方は、
\(\displaystyle {}_8C_{2}=28\)
です。
すなわち、
\(a+b+c=9\)を満たす自然数解(a,b,c)は28通りあることになります。
ちなみに、9を４個の自然数に分割の個数は、
\(a+b+c+d=9\)を満たす自然数解(a,b,c,d)に対応し、
\(\displaystyle {}_9C_{3}=84\)個
あることになります。
公式
上記をまとめて公式として記すと
ある自然数nをm個の自然数に分割する方法は、
\(\displaystyle {}_nC_{m-1} = \frac {n!} {m!(n-m)!} \)\(\displaystyle = \frac {n(n-1)(n-2)\cdots (n-m+1)} {m(m-1) \cdots 1}\)
通りある。
