数学Ａ 順列、組み合わせ

質問

復習の範囲で問題を解いているのですが、次の問題の解き方で躓いたのでアドバイスお願いいたします。

■問１
区別ができないボール10個を区別が出来ない4個の箱に分ける方法は何通りあるか求めよ。
ただし空の箱があってもよいものとする。

ボールと箱の両方が区別されないので式が思いつきませんでした。
書き出せば答えは簡単に求められるのですが、うまく解く方法を教えていただきたいと思います。

回答No.14

taktta · ベストアンサー

記事■分割数の漸近挙動 　参考
http://www.geocities.jp/ikuro_kotaro/koramu/bunkatsu.htm

参考URL：

http://www.geocities.jp/ikuro_kotaro/koramu/bunkatsu.htm

お礼

そしてそして、更に参考ありがとうございます。
読ませていただいたのですが、知識不足なために途中から理解しかねる内容でした…。
自分なりに気の済むまで考えてみたいと思います。
05-06-30 16:50

回答No.13

taktta

何か法則を見つけられればと思います…ｗ
05-06-29 22:30

法則といえばＮＯ５の人のだしている回答が法則でこれで必要十分だと私にはおもわれますが。

お礼

その導出方法も気になりますが、他の法則も見つけられればと思いまして…。

回答No.12

graphaffine

quadsさん、今晩は。
お問合せの件、
p(n,4)＝｛（２ｎ＾３＋６ｎ＾２－９（１－（－１）＾ｎ）ｎ＋１４４）／２８８｝の出典は下記文献１です。但し、文献１では文献２から式を引用しているだけで
導出方法は文献２のほうにあるそうですが、私は見ていません。もし見ていたとしても差分方程式の高度な知識が必要みたいですから私にはとても歯が立ちません。

文献１　数え上げ組合せ論入門　日本評論者発行　成嶋弘著
文献２　数理科学　１９９１年９月号　離散数学とは何か　野崎昭弘著

それから、細かい話ですがNo7のお礼
＞自然数ｎを分割する方法の総数を算出する式は無いようですが、
無いということが示されたわけではありません。今現在は見つかっていないが、今後見つかるかもしれません。
（つい、字面どおりに解釈しましたが、もしかすると
意図としては合っていたかもしれませんね）

お礼

回答ありがとうございます。
恐らく、私の方が貴方様より知識が乏しいので、そのような仰られ方だと私には導出は不可能に近いようですね…；
しかしながら、文献の方も参考にさせていただきます。
でも、文献２の方は読む機会があるのだろうか…。

p(n,k)の式すら途轍もなく難しい感じなのにp(n)の導出は…というような。。
「式が存在しない」という解釈はしていませんでしたが、「式の導出は非常に困難」という感じで書き込みました。
今はNo.10さんの方を参考にプログラムを組んだりしています…。
といっても書き出しているだけですが…。

何か法則を見つけられればと思います…ｗ
05-06-29 22:30

回答No.11

taktta

下記ＮＯ　10でのＡＮＳＷＥＲ補足、同サイトのｐ（２０）まで計算した結果表
でこの表の１，５，８，９を足した２３が答えです。

１　２　３　　４　　５　６　７　８　９　１０
１
２
３
４
５
６
７
８
９
１０　p(n,r)　n,r
１１　４２、１０，１，５，８，９，７、―――

回答No.10

taktta

非常に関係あるところをみつけたのでお知らせします。
http://www.asahi-net.or.jp/~KC2H-MSM/excel/excel003.htm

参考URL：

http://www.asahi-net.or.jp/~KC2H-MSM/excel/excel003.htm

お礼

誠にありがとうございます。
提示していただいたサイトを参考に実際に組み込んで計算してみました。
もっと考察してみたいと思います。

05-06-29 19:50

※適当に締め切りたいと思います。

回答No.9

taktta

１０＋０＋０＋０
９＋１＋０＋０
８＋２＋０＋０
８＋１＋１＋０
７＋３＋０＋０
７＋２＋１＋０
７＋１＋１＋１
６＋４＋０＋０
６＋３＋１＋０
６＋２＋２＋０
６＋２＋１＋１
の続き
５５００
５４１０
５３２０
５３１１
５２２１
４４２０
４４１１
４３３０
４３２１
３３３１
３３２２

回答No.8

taktta

g(10,4）空箱なしで１０を４つの箱に分けるの場合数
f(10,4）空箱ありで１０を４つの箱に分けるの場合数
f(10,4）＝ｇ(10,4）+ｇ(10,3）+ｇ(10,2）+g(10,1）
g(n,1）=1

ｇ(10,4）1=箱の数４で一番最小の箱の数が１ の場合数
ｇ(10,4）２=同上で一番最小の箱の数が２ の場合数
ｇ(10,4）３=同上で一番最小の箱の数が３の場合数 ：ありえない
ｇ(10,3）1=箱の数3で一番最小の箱の数が1の場合数
ｇ(10,3）2=箱の数3で一番最小の箱の数が2の場合数

以下同様定義

すると
ｇ(10,4）＝ｇ(10,4）1+ｇ(10,4）２
ｇ(10,3）＝ｇ(10,3）1+ｇ(10,3）２+ｇ(10,3）３
ｇ(10,2）＝ｇ(10,２）1+ｇ(10,2）２+ｇ(10,2）３+ｇ(10,2）４+ｇ(10,2）５
ｇ(10,１）＝１
ｇ(ｎ,１）＝１

関係式
ｇ(10,ｎ）m＝ｆ（１０－nm、n-1）の関係が成立します。これはｎｏ１の人の考えを理解すればわかる。
後はエクセルなどでｆ、ｇの表を作っていけ一般的な場合もいくはづですが。

お礼

No.10でまとめて書かせていただきます。

回答No.7

graphaffine

たびたびの訂正で申し訳ない。

先程の投稿の最終行を下記のように、訂正。

従って、求める答えはq(10,4)=p(10,4)+p(10,3)+p(10,2)+p(10,1)=9+8+5+1=23となる。

お礼

過去ログに同じ内容がありましたね…。失礼しました。
http://oshiete1.goo.ne.jp/kotaeru.php3?q=998567

自然数ｎを分割する方法の総数を算出する式は無いようですが、拡張させたりして考えてみたいと思います。

回答No.6

graphaffine

先程回答したものですが、問題を間違えましたので、再投稿です。
細かい部分は適当に省略しますが、意欲があれば自分でギャップを埋めてください。

自然数ｎ、ｋに対し関数ｐ、ｑを次のように定める。
p(n,k):自然数ｎのちょうどｋ個の自然数への分割の個数
q(n,k):自然数ｎのｋ個以下の自然数への分割の個数

このとき、定義から明らかに下記２式が成り立つ。
q(n,k)=p(n,1)+・・・+p(n,k)---(a)
p(n,k)=q(n-k,k)---(b)

従って、求める答えはp(10,4)=p(10,4)+p(10,3)+p(10,2)+p(10,1)=9+8+5+1=23となる。

回答No.5

graphaffine

自然数分割問題であることを
理解されているようなので、話は早いです。
一般に自然数ｎの４個の整数への分割の個数p(n,4)は
p(n,4)＝｛（２ｎ＾３＋６ｎ＾２－９（１－（－１）＾ｎ）ｎ＋１４４）／２８８｝で与えられます。
なお、｛　｝は小数部切捨てとします。
従って、ご質問の答えは、ｐ（１０，４）＝９となります。

お礼

回答ありがとうございます。
この場合の式はどのように導出されたのでしょうか…。
恐れ入ります。

05-06-29 18:55

回答No.4

sunasearch

#1です。いろいろとまちがってすみません。。。
ご指摘の通りです。

計算式の予想は、１０個を４つの箱という問題を、
７個を３つの箱
６個を３つの箱
・・・
１個を３つの箱
０個を３つの箱
という小さな部分問題に分解してその和を考える。

そして同様の操作を、再帰的に繰り返す形になると思うのですが、うまく定式化できるか不明です。

お礼

お礼で少し示しましたが、自然数ｎを自然数の和で表す場合の数について、ｎと項数の関係式に法則が分かれば代入するだけなのですが。

自然数を自然数の和の形にする方法が何通りあるか。というような問題を、過去に、ある数学掲示板にて考えた記憶があるのですが忘れてしまいました…。

もう少し自力で考えてみます…。
ご存知の方は回答お願いいたします。