重複組合せの問題で

(問題文)
7を3つの自然数の和で表す方法は何通りあるか？
ただし、加える順序は問題にせず同じ自然数を
使ってもよい。

場合の数での問題なので、樹形図を書けば一発で
わかるのですが、式として表すことはできないもの
だろうかと悩んでます。
また、和の数や足す回数が変化した場合どうなるかも
知りたいのでその式を作る上での考え方も教えて
下さると嬉しいです。

No.6 ベストアンサー 回答者： taropoo 回答日時： 2001/07/21 22:38

n個の自然数 p_1, p_2, ... , p_n が次の条件を満たしているとします。

　　　　p_1 ≦ p_2 ≦ ... ≦ p_n
　　　　p_1 + p_2 + ... + p_n = S
このような (p_1, p_2, ... , p_n) の組が何通りあるかを N(S, n) で表す事にします。

さて、N(S, n) の中には p_1 が１のものとそうでないものがあります。これで場合分けしましょう。

i)p_1 = 1 のとき
p_1を取り除いた p_2, p_3, ... , p_n が次の条件を満たします。
　　　　p_2 ≦ p_3 ≦ ... ≦ p_n
　　　　p_2 + p_3 + ... + p_n = S - 1
よってこのような (p_2, p_3, ... , p_n) の組の総数は、(n - 1) 個の自然数の総和が (S - 1) になる場合の数なので
　　　　N(S - 1, n - 1) 通り
となります。

ii)p_1 > 1 の時
p'_1 = p_1 - 1, p'_2 = p_2 - 1, ... , p'_n = p_n - 1 とおくと
n個の自然数 p'_1, p'_2, ... , p'_n
　　　　p'_1 ≦ p'_2 ≦ ... ≦ p'_n
　　　　p'_1 + p'_2 + ... + p'_n = (p_1 - 1) + (p_2 - 1) + ... + (p_n - 1)
　　　　　　　　= p_1 + p_2 + ... + p_n - n = S - n
よってこのような(p'_1, p'_2, ... , p'_n)の組の総数は
　　　　N(S - n, n) 通り
となります。

以上より、N(S, n) に関する漸化式
　　　　N(S, n) = N(S - 1, n - 1) + N(S - n, n)　　　　(*)
が得られます。

これに初期条件、境界条件
　　　　N(S, 1) = 1
　　　　N(n, n) = 1
　　　　N(n, m) = 0　　(n < m)
を加味してやれば任意の S, n について N(S, n) が求まります。

ここまでは分かったのですが、漸化式 (*) の解き方までは分かりませんでした。
どなたか解いて頂ければ良いのですが。

この回答へのお礼

漸化式を利用して解くとは思いつきませんでした。
ただ、私自身まだ漸化式について勉強が不十分のため
また漸化式を勉強しなおしてからゆっくり考えたいと
思います。
どうもありがとうございました。

お礼日時：2001/07/23 11:31

No.5 回答者： Ni-MH 回答日時： 2001/07/21 13:33

足す回数と足した合計の関係の式は、こうなるんじゃないでしょうか？

a:足した合計
b:足す回数

(a-1)C(b-1)-{(b-2)+(a-2)C(b-1)}

No.4 回答者： Ni-MH 回答日時： 2001/07/21 12:16

そうですかぁー。

「加える順序は問題にせず」って言うのは、重複無し
ってことなんですね。国語力も不足しています（^^;）

また式だけですが、式だけはわかりましたので・・・たぶん

あの式だったらCを使ったほうがいいですね。
a:合計の数

(a-1)Ｃ2-{1+(a-2)Ｃ2}＝重複無しの通りの数

だと思います（笑）

この式の（－)以降は、重複を消す値ですので、
これから本来の意味を発見するのはどうでしょうか？

No.3 回答者： Ni-MH 回答日時： 2001/07/21 03:44

下で、アドバイスを書いたNi-MHです。

足す回数が変化したときの式ですが、、、

まず3回のとき下のとおり　S=(A-2)*(A-1)/2　です。
4回のときは　　　　S=(A-3)*(A-2)*(A-1)/6　です。（たぶん（笑））
5回なら　　　S=(A-4)*(A-3)*(A-2)*(A-1)/24　です。（たぶん）

こういう風に、規則的になるのではないでしょうか？

No.2 回答者： Ni-MH 回答日時： 2001/07/21 03:19

まず始めに…この文章は間違っているかもしれません（＾＿＾;）

なにせ数学が苦手ですから。

まずは　X+Y+Z=7　として、Y+Zが最小値のとき（Y=1,Z=1）
X　の最大値を調べます。

X=7-Y-Z=5 で、　1≦X≦5　になります。
そして、必ず 1≦Z にするためには下のようになります

X=5　のときは　Y=Z=1 　だから　X=5　のときは　1通り
X=4　のときは　Y≦2　　だから　X=4　のときは　2通り
X=3　のときは　Y≦3　　だから　X=3　のときは　3通り
　　　　　　　　　　　　・
　　　　　　　　　　　　・
これは、Y　の値が決まれば　Z　を考える必要がないからです。
Y　の値は、そのまま”通り”の数になります。

こう考えると、1,2,3,4,5 通りなので

1+2+3+4+5=15通りです。

そしてこれを、一般的な式にすると・・
（これは3個の数字の足し算に関してのみいえます。）

足し算の合計の数をAとすると（今回の問題で言えば7）
n=A-2
S(通りの合計)=n*(n+1)/2　で出ます。（S=(A-2)*(A-1)/2）

これでは、足す回数が4とかだったら無理ですね。
でも、、
１＋○＋○＋○
２＋○＋○＋○
３＋○＋○＋○　で考えて、○の部分３つを上の考え方で補えば、
何とかできるかも・・・ちょっと無理か（笑）

ここんところは、頭のいい方に任せましょう（＾＾；）

ところで、この問題は高校レベルですか？中学レベルですか？
教えてください（笑）

この回答への補足

まず、初めにこんなややこしい問題にお答え下さってありがとうございます！
ただ『加える順序は問題にせず』とあるように『124』『142』『214』『241』『412』『421』と
これらはすべて同じことになるのでNi-MHさんの教えてくださった考え方ではちょっと解けないみたいなんです。
(ちなみに『加える順序』も考えて求めるとこの問題は6C2=6*5/2*1=15という式になります)
あと、この問題は一応高校レベルですが、なにぶん樹形図ではなく妙な風に考えているので、ちゃんとした難易度はわかりません(苦笑)

補足日時：2001/07/21 09:26

No.1 回答者： taropoo 回答日時： 2001/07/21 01:39

xyz-空間を考えます。

x + y + z = 7
x ≧ 0, y ≧ 0, z ≧ 0
とすると、これはＡ(7,0,0),Ｂ(0,7,0),Ｃ(0,0,7)を頂点とする正三角形になります。
この正三角形をＡＢに平行に７等分、ＢＣに平行に７等分、ＣＡに平行に７等分に線を引くと
その線の交点達が格子点、すなわちx,y,z座標が整数の点になります。
まずこの図を書いてください。

次に「自然数の和」および「加える順序は問題にせず同じ自然数を使ってもよい」をx,y,zで表すと
1 ≦ x ≦ y ≦ z
となります。そこで上の図に３本の線を付け加えます。すなわち
x = 1
x = y
y = z
この３本の線の作る三角形の辺上および内部にある格子点が求める「自然数の和」に対応します。
この場合ですと４点が該当します。即ち
(1,1,5), (1,2,4), (1,3,3), (2,2,3)
です。よって４通りとなります。

あまり関数などのきれいな形では表せてませんが、樹形図よりは幾何学的でしょ？
但し、和の数の変化には対応できますが足す回数が増えると次元が４次元とか５次元とか
イメージしづらいものになっちゃうので足す回数の増加にはこの考えでは対応できません。

この回答への補足

すみません。３次元における関数についてはまだ習っていないんです。でも、考え方としてはなんとなくですがわかったような気がします。

補足日時：2001/07/21 09:34