「n元1次方程式 x1+x2+・・・xn=r (r≧n)の正整数解は何

質問

「n元1次方程式 x1+x2+・・・xn=r (r≧n)の正整数解は何組あるか」という問題です。
僕はx1～xnまで必ず最低1は入るので、残りの r-n の割り振りを考えればよいと考えました。
そこで、r-n を割り振る場合には nC1=n通り
また、　r-n-1,1 を割り振る場合には nC2*2通り
　　　　r-n-2,2 を割り振る場合には nC2*2通り
　　　　r-n-2,1,1 を割り振る場合には nC3*3通り
　　　　r-n-3,3 を割り振る場合には nC2*2通り
　　　　r-n-3,1,2 を割り振る場合には nC3*3通り
　　　　r-n-3,1,1,1 を割り振る場合には nC4*4通り
・・・
最後は　r-n-(r-n-1),1,1・・・　を割り振る場合には nCn*n=n通り
と考えていくと、
nC1+(r-n-1)nC2*2+(r-n-2)nC3*3+(r-n-3)nC4*4+・・・+2*nC[n-1]*(n-1)+1*nCn*n
=n+(r-n-1)nC2*2+(r-n-2)nC3*3+(r-n-3)nC4*4+・・・+2*nC1*(n-1)+n
としました。
このような考え方でよろしいのかアドバイスいただければと思います。
よろしくお願い致します。

回答No.1

nag0720 · ベストアンサー

これは重複組み合わせでよく出る問題で、答えは、
nH(r-n)=(r-1)C(r-n)
です。

例えば、n=4、r=7の場合は、
1114,1123,1132,1141,1213,1222,1231,1312,1321,1411,
2113,2122,2131,2212,2221,2311,3112,3121,3211,4111
の20通り。(4H3=6C3=20)

SATA_YUKIさんの式では、
4+2*4C2*2+1*4C3*3+4
なのか
4+2*4C2*2+4
なのかはわかりませんが、どちらにしても違っています。

考え方で間違っているのは、
「r-n-3,3 を割り振る場合には nC2*2通り」
などとしたときのnとrの条件を明確にしていない点でしょう。
（r-n-3≧3　に限定しないと他の場合と重複します）
あと、
r-n-4,2,2 を割り振る場合も考慮していますか？

お礼

nag0720様ありがとうございます。大変参考になりました。