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

スポンサーリンク
の式を満たす整数解の組は何通りあるか. $ (1)\ \ x+y+z=8 (x≧0,\ \ y≧0,\ \ z≧0)$ $ (2)\ \ x+y+z=8 (x≧1,\ \ y≧1,\ \ z≧1)$ $ (3)\ \ x+y+z≦8 (x≧0,\ \ y≧0,\ \ z≧0)$ \\ x+y+z=n}$を満たす整数解の組数 \\  (1)\ \ $異なる3種類のものから,\ 重複を許して8個取る組合せの総数}に等しい. x,\ y,\ zは整数なので,\ 8個のものをx,\ y,\ zにそれぞれ何個ずつ分配するか}を考えることに等しい. これは以下のように○と|の並びとみなせるから,\ 結局は前項で学習した重複組合せ}に他ならない. 8個の○と2本の|の並べ方に帰着するから 10!}{8!2!}=45\ (通り) (同じものを含む順列}) もちろんこれで答えても何ら問題ないが,\ 重複組合せの公式を用いた解答を示した. n種類のものから重複を許してr個選ぶ組合せの総数は \Kumiawase nr=C{r+n-1}{r 本問が初見であっても,\ 以下のようにしらみつぶし}する気概をもってほしい. 後に示す応用問題のように条件が複雑になるほどその姿勢は重要になる. 数 B:数列を学習済みならば,\ この過程を別解のように多少スマートに記述できる. 異なる3種類のものから,\ 重複を許して5個取る組合せの総数}に等しい. {8個の○の間の7ヶ所から2ヶ所選んでに2本の|を入れる場合の数}に等しい.$先にx,\ y,\ zに1ずつ配分すると,\ 後は残りの5の配分である.}$ 異なる3種類のものから,\ 重複を許して5個取る組合せの総数}に等しい.$ x,\ y,\ zが0以上の整数}のとき,\ x+y+z=nを満たす整数解の組数は重複組合せとなる. x,\ y,\ zが0以上でない場合,\ 0以上になるように変数変換する}ことが有効である. 簡潔さは別解が上だが,\ 応用性が高く機械的な処理が可能になるので,\ 本解の方法も習得してほしい. x≧1\ ⇔\ x-1≧0\ より,\ x-1=X\ とすれば,\ X≧0\ となる. y,\ zも同様の変換を行い,\ X,\ Y,\ Zのみの条件にすると,\ (1)と同様に重複組合せに帰着する. (x,\ y,\ z)と(X,\ Y,\ Z)は1対1で対応する}から,\ (X,\ Y,\ Z)の組数を求めればよいわけである. 実は,\ ○と|に置き換えて考えるとあっさりと解決する(別解1). 各文字が1以上は,\ 2本の|が連続していたり端にあったりしてはいけない}ことを意味する. よって,\ ○\land○\land○\land○\land○\land○\land○\land○\ の\land に2本の|を入れる}だけでよい. 別解2は,\ あらかじめ8個の○から3個を取り,\ x,\ y,\ zに1個ずつ配分しておく}ものである. すると,\ 残りの5個の○の配分の仕方が何通りあるか}に帰着する. このとき,\ ○○|○|○○\ は,\ x=3,\ y=2,\ z=3\ を意味することになる. 本質的には本解と同じであり,\ 数式で考えるか○と|で考えるかの違いでしかない. 異なる4種類のものから,\ 重複を許して8個取る組合せの総数}に等しい.$ 本解の方法を知らなければ,\ 右辺の値で場合分け}することになるだろう. つまり,\ x+y+z=0,\ x+y+z=1,\ ・・・,\ x+y+z=8\ の解の組数をそれぞれ求めて足す. 本問には,\ 極めてうまい解法が存在する.\ 応用性も高いので,\ 是非とも習得しておいてほしい. x+y+zと8の差を文字でおくと,\ 不等式を等式に変換できる.} 下の左の9つの方程式の整数解と,\ 右の方程式(すべて同じ式)の整数解は1対1で対応する.  x+y+z=0\ ⇔\ x+y+z+w=8\ \ (w=8)  x+y+z=1\ ⇔\ x+y+z+w=8\ \ (w=7)  x+y+z=8\ ⇔\ x+y+z+w=8\ \ (w=0) 例えば,\ x+y+z=4の整数解(3,\ 1,\ 0)は,\ x+y+z+w=8の整数解(3,\ 1,\ 0,\ 4)と対応する. 結局,\ x+y+z≦8の整数解の組数は,\ x+y+z+w=8の整数解の組数と一致する.} 次の式を満たす整数解の組は何通りあるか. $ (4)\ \ 3x+y+z=8 (x≧0,\ \ y≧0,\ \ z≧0)$ $ (5)\ \ x+y+z=8 (0≦ x≦4,\ \ 0≦ y≦4,\ \ 0≦ z≦4)$ $ (6)\ \ x+y+z=8 (x≧0,\ \ y≧0,\ \ z≧0,\ \ x,\ y,\ zに奇数が含まれる)$ $ (7)\ \ xyz=400 (x≧1,\ \ y≧1,\ \ z≧1)$ \\ 各文字の係数が異なる場合,\ 計算で簡潔に求めることは難しいのでしらみつぶし}する. 係数が大きい文字に着目する}と,\ 整数解の組数は一気に絞られる. 本問の場合,\ 3xに着目すると,\ y≧0,\ z≧0よりx≧3はありえないことがわかる. 整数解の組に5以上の値が含まれるとすれば,\ $x,\ y,\ z$のうちの1つだけ}である. x≧5,\ y≧0,\ z≧0}$のときの$x+y+z=8$の整数解の組数を求める. ]\,は排反}なので,\ 5以上の値を含む整数解の組数は\ \ $10+10+10=30\ (通り 求める整数解の組数は 45-30=15\ (通り)}$} 上限がある場合,\ 総数から上限を超える値を含む整数解の組数を除く方針}が有効である. よって,\ 本来は次の個数定理を用いて求める必要が生じる.\ 重複を考慮する必要があるわけである.  n(A∪ B∪ C)=n(A)+n(B)+n(C)-n(A∩ B)-n(B∩ C)-n(C∩ A)+n(A∩ B∩ C) しかし,\ 本問の場合,\ 合計でも8なので2つ以上の文字が同時に5以上になることはない. この場合,\ x≧5,\ 0≦ y≦4,\ 0≦ z≦4を満たす解とx≧5,\ y≧0,\ z≧0を満たす解は同じである. 結局,\ (2)と同様に変数変換}することが有効なタイプに帰着する. 最後,\ (1)で求めた総数から引く. 求める整数解の組数は 45-15=30\ (通り)}$}  条件を満たすのは,\ $x,\ y,\ z$のうちちょうど2つが奇数}の場合だけである. \\ 同様に, $yとz$が奇数のときおよび$zとx$が奇数のときも10通りずつある. 「少なくとも1つが奇数」なので,\ 総数の45通りから「すべてが偶数」を除く}と簡潔に済む. 偶数条件を数式で表す(変数変換する})と,\ (1)に帰着する. (x,\ y,\ z)と(x’,\ y’,\ z’)は1対1で対応する}から,\ (x’,\ y’,\ z’)の組数を求めればよいのである. 別解は奇数を含む解を直接的に求めるものである. x+y+zが偶数なので,\ 実は(x,\ y,\ z)=(奇,\ 奇,\ 偶),\ (奇,\ 偶,\ 奇),\ (偶,\ 奇,\ 奇)の場合しかない. 変数変換}により(1)に帰着するが,\ そのためにはx=2x’-1と設定してはならない. x≧0よりx=1,\ 3,\ 5,\ ・・・\ であり,\ x=2x’-1とするとx’≧1となってしまうからである. 4個の素因数2と2個の素因数5をx,\ y,\ zに配分する方法が何通りあるか}を求めればよい. 条件を数式で表現してみると,\ 結局は(1)と同様の問題であることに気付く. (a,\ b,\ c)と(p,\ q,\ r)は互いに影響しないから,\ それぞれの整数解の組数を求めて掛ければよい. なお,\ 2^0=3^0=5^0=1である(詳しくは数II}で学習).