格子点

質問

x/2+y/3+z/6≦10を満たす0以上の整数x, y, zの組(x, y, z)の個数を求めよ。

という問題で、答えではxを固定して、あとはシグマ計算をしているのですが、
なんとか工夫して重複組合せを使えないでしょうか？（余事象など・・・）

つまり一般化すると、
ax+by+cz=n (a, b, c, nは自然数、x, y, zは0以上の整数)
を満たす(x, y, z)の個数を重複組合せを利用して求めよ。

ということです。
（ただしa=b=c=1のときはそのままなので、それ以外の場合です。)

回答No.5

stomachman · ベストアンサー

えーと、ANo.4がどうも伝わらないようなんで、もちっと詳しくご説明いたしましょう。

[1] まずは、
　「"S"と書いたカード2枚と、"T"と書いたカード2枚がある。で、好きなようにカードを取りなさい。」
という話が、
　　(1+s+s^2)(1+t+t^2)
という式に対応付けられる、ということをご理解戴きましょう。この式を多項式に展開してみると
　　(1+s+s^2)(1+t+t^2) = 1 + s + s^2 + t + st + (s^2)t + (t^2) + s(t^2) + (s^2)(t^2)
となりますね。
　項の数が9個あるのは、「好きなようにカードを取」るやり方が9通りあることを意味している。そして、たとえば(s^2)tの項は「Sのカード2枚とTのカード1枚を取る」という取り方を表している。右辺第1項の1(=(s^0)(t^0))は「Sのカードを0枚とTのカードを0枚取る」という取り方を表している。
　なぜそうなるかというと、展開の時に二つあるカッコの中からそれぞれひとつの項を選んで、それらを掛け算して項を作りますよね。この作業こそが、9通りの「取り方」を実際にひとつずつやっていることに他ならないからです。

[2] 「"S"と書いたカード2枚と、"T"と書いたカード2枚がある。3枚カードを取る方法は何通りあるか」
という問いではどうか。カードの枚数はSとTのカードを区別しないで数えるのだから、上記のs,tの両方にpを代入して区別を無くしてしまえば良い。すると、
　　(1+p+p^2)(1+p+p^2) = 1 + 2p + 3(p^2) + 2(p^3) + p^4
だから、3枚のカードを取る方法は、p^3の項の係数を見れば2通りだと分かる。実際、S,Tのカードを区別して数えた[1]の多項式展開における(s^2)tとs(t^2)が、p=s=tによって合算されて2(p^3)の項が出来ている訳です。
　全く同様に
　「"S"と書いたカード6枚と、"T"と書いたカード5枚と、"U"と書いたカード100枚とがある。3枚カードを取る方法は何通りあるか」
ならば、
　　(1+s+s^2+…+s^6)(1+t+t^2+…+t^5)(1+u+u^2…+u^100)
において、p=s=t=uとすれば良い。カードの枚数や種類が増えたって話は同じです。

[3] ここで改めて
　「"S"と書いたカード6枚がある」
を考えてみれば、
　　1+s+s^2+…+s^6
という式がどうして「好きなようにカードを取りなさい」と対応付けられるのか、もう納得が行ったんじゃないでしょうか。

[4] 次に、ちょっと条件が付いて
　「"S"と書いたカード6枚と、"T"と書いたカード5枚と、"U"と書いたカード100枚とがある。ただし、Sのカードは2の倍数枚ずつ取らねばならない。n枚カードを取る方法は何通りあるか」
を考えます。すると、
　　(1+s^2+s^4+s^6)(1+t+t^2+…+t^5)(1+u+u^2…+u^100)
とすれば良い。s, s^3, s^5 という取り方は禁止されているから、これらの項の係数は0にしなきゃならん、という所だけが違います。あとは同じで、p=s=t=uを代入して多項式に展開し、p^nの項の係数を調べる。

[5] というわけで、ご質問の
　「ax + by + cz = k (ただしk≦n) となる非負のx,y,zは何通りあるか」
を
　「Xと書いたカードがn/a枚以上、Yと書いたカードがn/b枚以上、Zと書いたカードがn/c枚以上ある。Xのカードはaの倍数枚ずつ、Yのカードはbの倍数枚ずつ、Zのカードはcの倍数枚ずつ取らねばならない。k枚カードを取る方法は何通りあるか」
という問題に書き換えれば、nがa,b,cのどれでも割り切れる場合なら
　　X(p) = 1+p^a+p^(2a)+…+p^n
　　Y(p) = 1+p^b+p^(2b)+…+p^n
　　Z(p) = 1+p^c+p^(2c)+…+p^n
を考えて、（ただしnがa,b,cのどれでも割り切れる場合以外は、X, Y, Zの右辺の最後の項がちょっと異なる。）それらの積
　　f(p) = X(p)Y(p)Z(p)
を多項式に展開してp^kの項の係数を調べれば、それが答である。

　a=3, b=2, z=1, n=60の場合ならば、
　　X(p) = 1+p^3+p^6+…+p^60
　　Y(p) = 1+p^2+p^4+…+p^60
　　Z(p) = 1+p+p^2+…+p^60
　これを、等比級数の公式を使って
　　X(p) = (1-p^63)/(1-p^3)
　　Y(p) = (1-p^62)/(1-p^2)
　　Z(p) = (1-p^61)/(1-p)
　　f(p) = X(p)Y(p)Z(p)
と整理しました。（ここんとこまでをANo.4に書いたんです。）

[6] f(p)の分子と分母を分けて、
　　g(p) = (1-p^61)(1-p^62)(1-p^63)
　　h(p) = 1/((1-p)(1-p^2)(1-p^3))
とすると
　　f(p) = g(p)h(p)
であり、h(p)のマクローリン展開を
　　h(p) = Σ{n=0～∞} H[n](p^n)
とすれば、f(p)は
　　f(p) = g(p) Σ{n=0～∞} H[n](p^n)
である。
　さて、分子g(p)を展開して
　　g(p) = 1 - p^61 - p^62 - …(略
としてみれば分かる通り、g(p)の各項のうちで、f(p)を多項式で表した時にp^k (k≦60)の項の係数に関わるのは最初の1だけ。他の項は全部指数が60を越えているから、p^kの項とは関係がないんです。
なので、h(p)のp^k (k≦60)の項の係数、すなわちH[k]がコタエである。

　言い換えれば、なにも
　　X(p) = 1+p+p^2+…+p^60
なんて上限を切らなくたって、無限級数
　　X(p) = 1+p+p^2+… = 1/(1-p)
でも同じ事ですね。
　　X(p) = 1/(1-p)
　　Y(p) = 1/(1-p^2)
　　Z(p) = 1/(1-p^3)
　　f(p) = X(p)Y(p)Z(p)
としておけば、最初からg(p)なんて詰まらんものは出て来ないで済む訳です。

[7] まとめますと、
「ax + by + cz = k となる非負のx,y,zは何通りあるか」の答は
　　f(p) = 1/((1-p^a)(1-p^b)(1-p^c))
のマクローリン展開
　　f(p) = Σ{n=0～∞} H[n](p^n)
におけるH[k]に他ならない。（もちろん、問題の左辺がx,y,zの3項だけじゃなく、もっと沢山あっても同じことです。）
　かくて、（ご要望通りに重複組み合わせを使うという訳ではないけれども）組み合わせ論と多項式との関係を利用して、ご要望の一般化ができた。（ということになりませんかね？）

[8] 実は、g(p)の有り難みは、x,y,zのそれぞれに勝手な上限が付いている、という時に発揮されるんです。すなわち
　ax + by + cz = n ただし 0≦x≦S, 0≦y≦T, 0≦z≦U
という問題の時には、
　　X(p) = 1+p^a+p^(2a)+…+p^(Sa) = (1-p^((S+1)a))/(1-p^a)
　　Y(p) = 1+p^b+p^(2b)+…+p^(Tb) = (1-p^((T+1)b))/(1-p^b)
　　Z(p) = 1+p^c+p^(2c)+…+p^(Uc) = (1-p^((U+1)c))/(1-p^c)
　　f(p) = X(p)Y(p)Z(p)
とすればいいというわけ。

お礼

とてもよく分かりました！すごく納得です。
冪級数の積からマクローリン展開を使うのは、目からうろこでした。その発想はまったくなかったです。（約数の数や和を求めるときの考えと途中まで同じですね）
本当に助かりました。ありがとうございました。

回答No.4

stomachman

一般化ですか。
えーと、重複組み合わせという訳にはいかないけれども、ナントナク似てる風の話に持って行くことならできるかも。すなわち、多項式
　　X(p) = (1+p^3+p^6+…+p^60)
　　Y(p) = (1+p^2+p^4+…+p^60)
　　Z(p) = (1+p+p^2+…+p^60)
　　f(p) = X(p)Y(p)Z(p)
を考えると、f(p)を展開した多項式において、p^kの項の係数が、3x+2y+z=kとなる(x,y,z)の組み合わせの数ですね。なので等比級数の公式
　　X(p)= (1-p^63)/(1-p^3)
　　Y(p)= (1-p^62)/(1-p^2)
　　Z(p) = (1-p^61)/(1-p)
を使って
　　f(p) = (1-p^63)(1-p^62)(1-p^61)/((1-p^3)(1-p^2)(1-p))
のマクローリン展開
　　f(p) = f(0) + f'(0)p/1! + f''(0)(p^2)/2! + f'''(0)(p^3)/3! + …
でp^kの項の係数を考えればいい。
　一般のa,b,cの場合には、X(p),Y(p),Z(p)の最後の項のベキが幾らになるかが(nがa,b,cでそれぞれ割り切れるかどうかによって)違って来るだけです。

お礼

なるほど、ありがとうございます。

回答No.3

masa072

整数問題と考えたほうが自然です。
両辺を6倍して3x+2y+z≦60を満たす組み合わせを絞り出します。
移項して2y+z≦3(20-x)、20-x=kとおけば2y+z≦3k(0≦k≦20)
このときの(y,z)の組を出すときに格子点的な発想が使えますが、kの範囲が小さいので数え上げてもいいですね。
（きっとわかっていると思いますが念のため）

重複組み合わせは使えないですね。
x+y+z=nのときに使えるのは、xもyもzも等価だからです。等価なので○をn個、|を2個として左から順にx,y,zと考えられますが、係数が異なれば|を置くところに制約が出てしまいます。そこまでは考えられません。

お礼

確かに等価でないと条件が出てきて、重複組合せでは考えられなくなりますね。
ありがとうございます。

回答No.2

naniwacchi

こんにちわ．
なかなか難しいお話ですね．

x+ y+ z≦ nという「不等式」を満たす (x, y, z)の組については，以下のようにして求められます．

問題を以下のように言い換えます．
「x+ y+ z+ k＝ nを満たす (x, y, z, k)の組は何組あるか？」
さらに，
「n個のりんごを x, y, z, kの 4つに分ける分け方は，いくつあるか？（0個の場合も可）」
と言い換えることで，(n+3)Ｃ3とおりと求められます．

いま書かれている問題（ax+ by+ cz＝ n）は，
「100円玉 x枚，50円玉 y枚，10円玉 z枚で，500円を作る組合せは何とおりあるか？」と同様ですね．
結局，100円玉が 5枚のとき，4枚のとき，・・・と場合分けしていくことになるかと．
これは，xを固定することと同等です．

お礼

ありがとうございます。正攻法ですね。

回答No.1

noname2727

このケースでは、重複組み合わせの考えを使うことはできないと思います。

お礼

わかりました。ありがとうございました。