ここから本文です

区別のない玉と箱、規則性について

gun********さん

2010/6/2122:56:55

区別のない玉と箱、規則性について

とある日。友達から
「赤玉10個を、区別できない4個の箱に分ける方法は何通りあるか。同じ色の玉は区別できないものとし、空の箱があってもよいものとする」
という問題をどう解くのか訊かれました。区別なしの玉10個と箱4個、数え上げると23通りありました。

規則性は無いのか(計算で解けないものか)と思い、他の場合も数え上げてみたところ

(1:1)(2:2)(3:3)(4:5)(5:6)(6:9)(7:11)(8:15)(9:18)(10:23)
(11:27)(12:34)(13:39)(14:47)(15:54)(16:64)(17:72)(18:84)(19:94)(20:108)
(21:120)

でした。[(区別できない玉の個数:その場合の数(通り))となっています]
一応正確を期すために工夫したので、これらは正しいはずです。

規則性はないものでしょうか。

回答よろしくお願いします。

補足一応上記の場合の数は、Cでプログラム・コンパイルし、実行したものです。正確を期すために、正しいかどうか自ら1~10個までは数え確かめたので間違いありません。

あと、(9.1.0.0)~(5.5.0.0)は6通りじゃなくて5通りだと思うのですが……

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数:
229
回答数:
1
お礼:
250枚

違反報告

ベストアンサーに選ばれた回答

aki********さん

2010/6/2212:08:00

a(0)=1,a(1)=1,a(2)=2,
a(3)=3,a(4)=5,a(5)=6 とする。

a(n)=★+ a(n-6) で表せる。

ただし、★の部分は…
n÷4=AあまりB とし、

[B=0の時]
★=2A^2+2A+1

[B=1の時]
★=2A^2+3A+1

[B=2の時]
★=2A^2+4A+2

[B=3の時]
★=2A^2+5A+3

で出すものとする。

(追記)
★=b(n)とおくと、
b(0)=1,b(1)=1,b(2)=2,b(3)=3 とし、

b(n)=b(n-4)+n とも表せる。

(さらに、追記)
よって最終的には、
a(0)=1,a(1)=1,a(2)=2,a(3)=3,a(4)=5,
a(5)=6,a(6)=9,a(7)=11,a(8)=15,a(9)=18 とすると、

a(n)=a(n-6)+a(n-4)-a(n-10)+n と表せる。

この回答は投票によってベストアンサーに選ばれました!

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる