FC2ブログ

Welcome to my blog

[答94] 自然数解の組数

ヤドカリ

ヤドカリ


'


[答94] 自然数解の組数


 a+b+c+d=29, a<b<c<d を満たす自然数の組(a,b,c,d)は何組?



[解答1]

 a<b<c<d の条件を除くと、283=3276 組。

 2数が同じものは順序を無視すれば、

   1が2個含まれる場合、他の2数の和は 27 だから 13 組、

   2が2個含まれる場合、他の2数の和は 25 だから 12 組、

            ………

   13が2個含まれる場合、他の2数の和は 3 だから 1 組、

 よって、13+12+……+1=91 組。

 3数が同じものは順序を無視すれば、

   1が3個含まれる場合, 2が3個含まれる場合,……, 9が3個含まれる場合 の9組、

   順序を考えると、9×4=36 組。

 2数だけが同じものは順序を無視すれば、91-9=82 組、

   順序を考えると、82×(4!/2!)=984 組。

 よって、a,b,c,dが異なるものは、3276-984-36=2256 組、

 a<b<c<d の条件をつければ、2256/4!=94 組。


[解答2]

 (b-a)+(c-a)+(d-a)=29-4a だから、b-a=p, c-a=q, d-a=r とおくと、

 p+q+r=29-4a, p<q<r を満たす自然数の組を求めることになります。

 (q-p)+(r-p)=29-4a-3p だから、q-p=x, r-p=y とおくと、

 x+y=29-4a-3p, x<y を満たす自然数の組を求めることになります。

 ここで、x+y=n, x<y を満たす自然数の組は、n≧3 で解が存在し、

 nが偶数のとき n/2-1 組, nが奇数のとき n/2-1/2 組 あります。

 29-4a-3p の値は、
   a=1 のとき、22, 19, 16, 13, 10, 7, 4
   a=2 のとき、18, 15, 12, 9, 6, 3
   a=3 のとき、14, 11, 8, 5
   a=4 のとき、10, 7, 4
   a=5 のとき、6, 3

 これらのすべての和が 222 で、偶数が 12 個、奇数が 10 個だから、222/2-12-10/2=94 組。


[参考]

 uch*n*anさんが、解答1の方法で、a+b+c+d=n の一般化をしてくれましたので、結果を示します。

・nが奇数の場合
 ((n-1)(n-2)(n-3)/6-(6((n-3)(n-5)/4+(n-2[(n+2)/3]-1))+4[(n-1)/3]))/24
・nが4で割って2余る場合
 ((n-1)(n-2)(n-3)/6-(6((n-4)(n-6)/4+(n-2[(n+2)/3]-2))+3(n-2)/2+4[(n-1)/3]))/24
・nが4の倍数の場合
 ((n-1)(n-2)(n-3)/6-(6((n-4)(n-6)/4+2+(n-2[(n+2)/3]-2))+3((n-2)/2-1)+4([(n-1)/3]-1)+1))/24

 もちろん、計算すれば式はもう少し簡単になりますが、計算がわかる状態を残してくれました。


 ちなみに私は、解答2の方法で、次の式を得ましたが、途中が非常に煩雑ですので、結果だけ示します。

・nが偶数の場合 [(n3-15n2+72n-76)/144] 個、
・nが奇数の場合 [(n3-15n2+63n-49)/144] 個です。

 プログラミングして両者が n=1000000 まで等しいことを確認しましたので間違いないものと思います。

.

スポンサーサイト



Comments 7

There are no comments yet.
ヤドカリ  
No title

数え上げる方法が一番確実で、そのように解かれた方が多いです。
右辺が29だから数え上げ、29万ならプログラム、29億なら一般化でしょうか?

いっちゃん  
No title

一番に伺ったら画像が行方不明でした。捜索願い出そうかなと
思ってたら、無事発見。。笑

我が家のポインセチアは枯れてしまいましたが、きれいに咲かせて
ありますね^^ポチ

アキチャン  
No title

おはようございます。
今の時期のポインセチア・・・珍しいですね (o^-^o)

uch*n*an  
No title

やどかりさん,チェックをありがとうございます。
私の一般式,n が 4 の倍数の場合の分子の引いている括弧内をちょっと補足しておくと,
6 倍している第 1 項:a = b,他は等しくない,二つだけが等しい場合
3 倍している第 2 項:a = b, c = d,他は等しくない,二つずつだけが等しい場合
4 倍している第 3 項:a = b = c,他は等しくない,三つだけが等しい場合
+ 1 となっている第 4 項:a = b = c = d,四つが等しい場合
他のは,これらと比較してご覧ください。
いきなり一般の場合を考えるのは大変なので,
n = 9, 10, 11, 12 などで試してみて,感じをつかむのがいいと思います。
なお,[解答2]の方法は,a + b + c + d + e = n のように,どんどん拡張でき,
具体的な計算ならば漸化式風にできる点,優れているのですが,
一般式の導出は,計算を頑張るしかないんでしょうかねぇ...

ヤドカリ  
No title

いっちゃん、コメントとポチを有難う御座います。
このポインセチアは1ヶ月以上前に長居植物園で撮ったものです。
今、どうなっているのかは分かりません。

ヤドカリ  
No title

アキチャンさん、コメントを有難う御座います。
上記のように、1ヶ月以上前に撮ったものです。
忘れていたので今頃になって載せました。
誤解されるようなことで、申し訳ありません。

ヤドカリ  
No title

uch*n*anさん、詳しい補足とコメントを有難う御座います。
> 一般式の導出は,計算を頑張るしかないんでしょうかねぇ...
は、その通りだと思います。
5元の場合、[解答1]の方法だと、
1ペア・2ペア・3カード・フルハウス・4カード・5カード
とポーカー役が沢山で手に負えません。
何か良い方法がないかと思います。