方程式x+y+z=nの整数解の組数

スポンサーリンク
次の式を満たす整数解の組は何通りあるか. $ x+y+z=8 (x0,y0,z0)$ $ x+y+z=8 (x1,y1,z1)$ $ x+y+z8 (x0,y0,z0)$  $異なる3個のものから,\ 重複を許して8個取る重複組合せ}であるx-1=X,y-1=Y,z-1=Z}\ とおく.$ { }$このとき x=X+1,y=Y+1,z=Z+1$ { }$よって  X+Y+Z=5 (X0,Y0,Z0)}$ { }$異なる3個のものから,\ 重複を許して5個取る重複組合せ}である.8個の○の間の7箇所に2本の|を入れる方法を考える.}$ 先にx,\ y,\ zに1ずつ配分しておき,\ 後で残りの5を配分する.}$ { }$異なる3個のものから,\ 重複を許して5個取る重複組合せ}である.$ $ C72}={21\ (通り)}$}よって x+y+z+w=8  異なる4個のものから,\ 重複を許して8個取る重複組合せ}である. 整数解の組数は,\ 実質重複組合せである. そして,\ 重複組合せは,\ 同じものを含む順列に帰着するのであった. 極めて応用性が高いので,\ 必ず以下の考え方を習得しておこう. x,\ y,\ zの値は,\ 次のようにして○8個と|\ 2本の順列と対応する. ○○○|○○|○○○ → x=3,y=2,z=3 ||○○○○○○○○ → x=0,y=0,z=8 結局,\ 重複組合せと同じく,\ ○と|の並びの総数を求めることに帰着する. 重複組合せとしてと同様に考えるには,\ 0以上である必要がある. 1以上の場合,\ |\ 2本が連続することが許されない. そこで,\ {0以上となるように変数変換を行う.} y,\ zも同様に変換し,\ X,\ Y,\ Zのみの式にすると,\ と同じ問題に帰着する. {x,\ y,\ zとX,\ Y,\ Zは1対1に対応する}から,\ X,\ Y,\ Zの組数を求める. 実質同じだが,\ わかりやすさでは別解のほうが有利である. 別解1は,\ {「○\land○\land○\land○\land○\land○\land○\land○」の\land に2本の|を入れる.} 別解2は,\ {○8個のうちの3個を1個ずつx,\ y,\ zに配分すると決めておく.} 結局,\ 残りの○5個の配分の仕方が何通りあるかに帰着する. このとき,\ ○○|○|○○\ は,\ x=3,\ y=2,\ z=3\ を意味することになる. 応用性を考えると本解のほうが有利なので,\ これらは別解とした. 本問を普通に解く場合,\ {右辺の値で場合分け}することになる. つまり,\ x+y+z=0,\ ,\ x+y+z=8\ のそれぞれの解の組数を求める. すると,\ C22+C32++C10}{2}=165\ となるが,\ かなり面倒である. 本問には,\ 恐ろしく巧妙な解法が存在する.\ 応用性も高く,\ 推奨される. {x+y+z\ と8の差を文字でおいて,\ 不等式を等式に変換する}のである. 存在しないwを導入することで,\ 9つの場合が右のように対等になる.  x+y+z=0x+y+z+w=8\ (w=8)  x+y+z=1x+y+z+w=8\ (w=7)           x+y+z=8x+y+z+w=8\ (w=0) 結局,\ {x+y+z8\ の組数は,\ x+y+z+w=8\ の組数と一致する.} 8個の苺をA,\ B,\ Cの3人に分ける方法は何通りあるか. ただし,\ 1個ももらえない人がいてもよいとする.  A,\ B,\ Cの3人がもらう個数をそれぞれ$x,\ y,\ z$とすると  求める場合の数は,\ を満たす整数$(x,\ y,\ z)$の組数に等しい.  これは,\ 異なる3個のものから重複を許して8個取る重複組合せ}である. 整数解の組数の求め方が真に役立つのは,\ むしろ通常の重複組合せの問題である. 本問は\ {8個の苺に重複を許してA,\ B,\ Cを対応させる}と重複組合せの扱いになる. つまり,\ {A,\ B,\ Cから重複を許して8個を選ぶ}と考えるわけである. このような対応は自然とは言えず,\ 重複組合せとみることが難しいかもしれない. そこで,\ とりあえず{条件を数式で表現してみる}と,\ 整数解の組数の問題になる. 重複組合せの問題は,\ {逆に整数解の組数の問題としてとらえると楽なことが多い.} 変に対応を考えることもなく,\ 半ば機械的に処理できるようになる. 以上から,\ {整数解の組数の求め方の応用性は極めて高い}といえるのである.
タイトルとURLをコピーしました