- ベストアンサー
組合せの総数がわかりません．
例えばa,b,c,dの四つの組み合わせ方を挙げます． 組み合わせるものを同じ数字であらわすとしまして， １１２３は，a,bを組み合わせてｂとｃは別々という意味です．ただし，２２１３も３３２１も３３１２も１１２３と同じ組合せになります． つまり総列挙すると １１２３(ab,c,d) １２１３(ac,b,d) １２３１(ad,c,b) ２１１３(a,bc,d) ２１３１(a,bd,c) ２３１１(a,b,cd) １１２２(ab,cd) １２１２(ac,bd) １２２１(ad,bc) １１１２(abc,d) １１２１(abd,c) １２１１(acd,b) ２１１１(a,bcd) １１１１(abcd) １２３４(a,b,c,d) の１５通りになるかと思います． 今，４つのアルファベットの組合せでしたが， これをnとすると，組合せの総数はどのようになりますでしょうか？ 定式化不可能なのでしょうか？不可能ならこの組合せ総数が指数関数的に増大することを示せればよいのですが．
- 数学・算数
- 回答数6
- ありがとう数4
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
#3です。あまりに乱雑なので手直ししてみました。 ちなみに#3のミスがありました… １,５,５,５,10,５,５,５,1,0,５,５,５,10,10,10,10,17ではなく １,５,５,５,10,５,５,５,10,５,５,５,10,10,10,10,17です… 他にも修正すべき所がありそうですが… #3は読ま無くて構いません。#4を読んでください。 なるべく解り易くまとめたのが#4ですので、 #3→#4と読んで戸惑う事はないかと思います… では、#4 Ｎ＝１の時 A の１通り Ｎ＝２の時 AB A B の２通り Ｎ＝３の時 ABC AB C AC B BC A A B C の５通り Ｎ＝４の時 質問にある15通り 以下延々と続くわけですが… ＮからＮ＋１を考えてみましょう Ｎ＝１→２ BはＮ＝１の時の組み合わせそれぞれに対して ・いずれかに混ざる ・単独となる の２通りが考えられるのだから… A→Aに付くor単独の２通り 合計２通り→Ｎ＝２の時の組み合わせは２通り Ｎ＝２→３ CはＮ＝２の時の組み合わせそれぞれに対して ・いずれかに混ざる ・単独となる の２通りが考えられるのだから… AB→ABに付くor単独の２通り A B→Aに付くor Bに付くor単独の３通り 合計５通り→Ｎ＝３の時の組み合わせは５通り これを簡単な式にするために組み合わせの図にある『固まりの数』について着目します。 ※質問にある１２１３等の最も大きい数と考えて下さい。 Ｎ＝１の時Aのみ…つまりＬ＝１ Ｎ＝２の時ABとAとBでＬ＝３ Ｎ＝３の時ABCとABとCとACとBとBCとAとAとBとCでＬ＝10 となります。 Ｎの時の組み合わせの数がＭ通り、固まりの数Ｌが解っていればＮ＋１の時の組み合わせは ・いずれかに混ざる事により新規組み合わせが合成される→Ｌ通り ・単独となる→Ｍ通り と言う事がいえますね。 つまり『Ｎ＋１の時の組み合わせは、Ｎの時のＭとＬの合計』と言う事になります。 ではＬを求める事が出来れば良いと言う事になりますが これは『組み合わせパターンがいくつになるのか』を考えるとＬを求められます。 ABC等くっついた固まりを○で表すと ○→○ or ○○ ○○→○○ or ○○○ ・いずれかに混ざる→組み合わせ一つに対しての固まりは吸収されるので変わらない ・単独となる→組み合わせ一つに対しての固まりは一つ増える また、 ・いずれかに混ざる→組み合わせはそのパターンの固まりの数 ・単独となる→組み合わせは１通り つまり、Ｎに対してＮ＋１になる時に新たに加わるものをoで表すと ○→◎ or ○ｏ ○○→◎○ or ○◎ or ○○ｏ ○○○→◎○○ or ○◎○ or ○○◎ or ○○○ｏ ○○○○→◎○○○ or ○◎○○ or ○○◎○ or ○○○◎ or ○○○○ｏ … という感じになるんです(これでイメージ沸きますかね…) つまり、固まりは １→３ ２→７ ３→１３ ４→２１ … と言う感じで増えます。 ここで、組み合わせに対する固まりの数の増え方を表してみます。 Ｎ＝１→２ １→３ Ｎ＝２の時の固まりの合計は３ Ｎ＝２→３ １→３ ２→７ Ｎ＝３の時の固まりの合計は3+7＝１０ Ｎ＝３→４ １→３ ２→７ ２→７ ２→７ ３→１３ Ｎ＝４の時の固まりの合計は3+7+7+7+13＝３７ となります。 固まりの数が増えるメカニズムを一般式にしてみましょう ------------------------------------------------------------------------- ・いずれかに混ざる→組み合わせ一つに対しての固まりは吸収されるので変わらない ・単独となる→組み合わせ一つに対しての固まりは一つ増える また、 ・いずれかに混ざる→組み合わせはそのパターンの固まりの数 ・単独となる→組み合わせは１通り つまり、Ｎに対してＮ＋１になる時に新たに加わるものをoで表すと ○→◎ or ○ｏ ○○→◎○ or ○◎ or ○○ｏ ○○○→◎○○ or ○◎○ or ○○◎ or ○○○ｏ ○○○○→◎○○○ or ○◎○○ or ○○◎○ or ○○○◎ or ○○○○ｏ ------------------------------------------------------------------------- これの考え方を使います。 Ｎに対してＮ＋１になった時… ・いずれかに混ざる→『組み合わせ１つに対して、固まりは吸収されるので変わらない』×『固まりの数ぶん増える』 ・単独となる→『組み合わせの固まりの数に対しての固まりが１つ増える』 これらの和が『固まりの数』となりますから [固まりの数]×[固まりの数]＋[固まりの数]＋１ まとめると [Ｎが１増えた時の固まりの数]＝[固まりの数]([固まりの数]＋１)＋１ となります。 １→３ ２→７ ３→１３ ４→２１ Ｘ→Ｙ…Ｙ＝Ｘ(Ｘ＋１)＋１となるわけですね。 では『固まりの数』に着目したら組み合わせのパターンはいくつになるのか？を考えます。 Ｎ＝１ １ Ｎ＝２ １ ２ Ｎ＝３ １ ２ ２ ２ ３ ここで言えるのはＮの時、全てが１つの固まりとなる１が１つあり、全てがバラバラとなるＮが１つあるのは確実ですよね？ その間には １＜ｘ＜Ｎとなるｘとなる組み合わせが存在しているのも確かでしょう。 この事からＮ＝４を考えると Ｎ＝４ １ ２ ｜ ｜ ２ ３ ｜ ｜ ３ ４ となるはずですね。(質問を見ればそうなるのは明白なんですが…) というわけでＮ＝４の時の２の場合と３の場合はそれぞれ何パターンあるかを考えてみます。 固まりが２となるものの組み合わせは １と３に分かれた場合 ２と２に分かれた場合 ですね １と３に分かれた場合は4Ｃ1で４通り ２と２に分かれた場合は4Ｃ2…ですが逆を含んでいるので２で割って３通り 固まりが３となるものの組み合わせは １と１と２に分かれた場合のみです ２に何が来るかが解ればいいのですから4Ｃ2の６通り Ｎ＝４ １：１通り ２：(4+3)通り ３：(6)通り ４：１通り 合計：１＋７＋６＋１＝15通りでよさそうです。 これをＮ＝３を踏まえて求めるとどうなるかを表します。 Ｎ＝３は以下の５通りですね １：ABC ２：AB C ２：AC B ２：BC A ３：A B C 固まりは1+2+2+2+3の１０です。 ５＋１０の15通りがＮ＝４の時の答えです。 引き続きＮ＝５を考えてみましょうか… １ ２ ｜ ｜ ２ ３ ｜ ｜ ３ ４ ｜ ｜ ４ ５ 固まりが２ ４１ ３２ 固まりが３ ３１１ ２２１ 固まりが４ ２１１１ それぞれの組み合わせは… となる所ですが、上の内容から、４の時の組み合わせの固まりの数を求めれば良いのですから Ｎ＝４の時固まりは… １：１通り ２：(4+3)通り ３：(6)通り ４：１通り ですから 固まり１が１つ→１×１＝１ 固まり２が７つ→２×７＝１４ 固まり３が６つ→３×６＝１８ 固まり４が１つ→４×１＝４ 1+14+18+4＝３７と言う事になります。 Ｎ＝５の時の組み合わせの数は [Ｎ＝４の時の組み合わせ数]＋[Ｎ＝４の時の固まりの数]＝１５＋３７で５２パターンとなります。 Ｎ＝６の時はと言うと Ｎ＝５の時の固まりを考えれば良いわけで、Ｎ＝４の時の固まりからＮ＝５の固まりを推測します。 ------------------------------------------------------------------------ ○→◎ or ○ｏ ○○→◎○ or ○◎ or ○○ｏ ○○○→◎○○ or ○◎○ or ○○◎ or ○○○ｏ ○○○○→◎○○○ or ○◎○○ or ○○◎○ or ○○○◎ or ○○○○ｏ ------------------------------------------------------------------------ これを使うわけですね。 Ｎ＝４→５ 固まり１が１つ→固まり１が１つ＋固まり２が１つ…これらが１つできる 固まり２が７つ→固まり２が２つ＋固まり３が１つ…これらが７つできる 固まり３が６つ→固まり３が３つ＋固まり４が１つ…これらが６つできる 固まり４が１つ→固まり４が４つ＋固まり５が１つ…これらが１つできる それぞれをまとめて 固まり１が１ 固まり２が1×1＋2×7＝15 固まり３が1×7＋3×6＝25 固まり４が1×6＋4×1＝10 固まり５が１ ５の時の固まりの合計は1×1+15×2+25×3＋10×4＋1×5＝１５１ つまり５２＋１５１＝２０３通りがＮ＝６の時の答えとなります。 Ｙ＝Ｘ(Ｘ＋１)＋１を使って固まりの計算をすると以下の通り ｛１(１＋１)＋１｝×１＋｛２(２＋１)＋１｝×７＋｛３(３＋１)＋１｝×６＋｛４(４＋１)＋１｝×１ ＝３×１＋７×７＋１３×６＋２１×１＝１５１ ５２＋１５１＝２０３通りとなるわけです。 多分これで合っているとは思いますが…どうなんですかね？今の私の頭ではこれ以上簡単には出来ませんでした。 固まりの数Ｌがもう少し簡単に求められるならばスッキリするんですけどね…
その他の回答 (5)
- jmh
- ベストアンサー率23% (71/304)
そんなときは、google とかで、 "1,2,5,15,52" math などと検索してみるとよいと思います。
- 参考URL：
- http://www.google.co.jp/
お礼
ありました。 Bellという数学者の考え方とこの問題は同値みたいでした。 Googleでこんな検索も出来るんですね！！ちょっとほんとにびっくりしました。
- kony0
- ベストアンサー率36% (175/474)
きわめて実験的推測ですが・・・ #4さんの考え方に基づいてn個の場合の組み合わせの総数I(n)を導出したところ、 I(n+1)/I(n)がどうやら単調増加するようです。 ということは、指数関数よりも発散の仕方が強いと言えるのではないでしょうか？ 誰か算式で解明してくれないかなぁ・・・（苦笑）
お礼
漸化式であらわすと a(i)=Σ(i-1)C(k-1)*a(i-k-1) となるみたいです。 1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,190899322,1382958545,10480142147,82864869804,682076806159,5832742205057,51724158235372,474869816156751, 4506715738447323 ベルというひとの考え方とこの問題は同値ですね。 みなさん本当にありがとうございました。
補足
n=30とn=50の組合せ総数っていくつぐらいですかね？ 最低でもこの２つが分かればとりあえず今のところは定式化や算式を明確に表現しなくてもいいのですが。。。
○ひとまずローカルルール アルファベッドＮ個の時Ｍ通りと解っているものとする。 また、１つの組み合わせをパターンと呼び パターンの中で質問の表記法で言う最大値をそのパターンのブロック数とでも呼ぶ そして、ブロック数の合計をＬで示すものとする。 ※補足、Ｌとは質問で言う数字の最大値→１２１３ならば３、１１１１ならば１、１２３４ならば４…の合計値 Ｎ＝２の時 AB／A B Ｎ・Ｍ・Ｌ＝２・２・３ Ｎ＝３の時 ABC／AB C／AC B／BC A／A B C Ｎ・Ｍ・Ｌ＝３・５・10 Ｎ＝４の時 ABCD／ABC D／ABD C／ACD B／BCD A／AB CD／AC BD／AD BC／AB C D／AC B D／AD B C／BC A D／BD A C／CD A B／A B C D Ｎ・Ｍ・Ｌ＝４・15・37 ○証明ではなく理論武装してみましょうか… ｎ＋１の時を考える 新たに追加されたアルファベッドは各ブロックのいずれかにくっ付くか単独と言う形となる ※１２１３ならば、１か２か３に加わるか４となるかである。と言う事。 つまり、組み合わせのリストではなくブロックで表すと… Ｎ＝２→３の時 １ブロック→２通り発生 ２ブロック→３通り発生 発生した合計５がＮ＋１つまり３つの時の組み合わせ Ｎ＝３→４の時 １ブロック→２通り発生 ２ブロック→３通り発生 ２ブロック→３通り発生 ２ブロック→３通り発生 ３ブロック→４通り発生 発生した合計１５がＮ＋１つまり４つの時の組み合わせ ちなみに Ｎ＝１の時は Aのみなので… Ｎ＝１→２の時 １ブロック→２通り発生 と言う事でＮ＝１からこれが使えそうですね。 次にＮ、Ｍ、Ｌを用いてＮ＋１の時を求めるように考えましょうか。 新たな１つはどうなる？ ・出来合いのブロックに付属する...(1) ・単独として存在する...(2) の２パターンですね。 (1)はＮの時のＬの数と解っているし、(2)はＭとなる。 つまりＮが１増えるとＭは一つ上のＭとＬの合計になるわけです。 Ｎ・Ｍ・Ｌ １・１・１ ２・２・３(１＋１＝２) ３・５・10(２＋３＝５) ４・15・37(５＋10＝15) つまり、この後のABCDEの５つの時は52通りとなるわけですね ではＬはどうやって求まるのかを考えれば良いわけです。 ブロック数はいくつ？ (1)で増えたものは前回のブロックと同じである (2)で増えたものは前回のブロック＋１である 各々いくつ増えるのか？ (1)は増える前のブロックと同じ数ぶん増える(ブロックが３ならブロック３が３つできるわけですね) (2)は１つだけ(これは１通りしかありません) Ｎ＝２→３の時 １ブロック→２通り発生→組み合わせのブロックは１と２ ２ブロック→３通り発生→組み合わせのブロックは２と２と３ 1+2+2+2+3＝１０ Ｎ＝３→４の時 １ブロック→２通り発生→それぞれのブロックは１と２ ２ブロック→３通り発生→それぞれのブロックは２と２と３ ２ブロック→３通り発生→それぞれのブロックは２と２と３ ２ブロック→３通り発生→それぞれのブロックは２と２と３ ３ブロック→４通り発生→それぞれのブロックは３と３と３と４ 1+2+2+2+3+2+2+3+2+2+3+3+3+3+4＝３７ これの一般式を作れば終わり...となるんですが、難しいですよね？ とりあえず『○と○と△』を『○と○と○と１』というように分けます 『□ブロック→□＋１通り発生→それぞれのブロックの和は□×(□＋１)＋１です。』 前回との差と考えると、前回の□を引くので『□×□＋１増える』と言えそうです。 この点について簡略化すると Ｎ＝２→３の時 １と２→(１×１＋１)＋(２×２＋１)→２＋５で７増える(３→10の説明) Ｎ＝３→４の時 １と２と２と２と３→(１×１＋１)＋(２×２＋１)＋(２×２＋１)＋(２×２＋１)＋(３×３＋１)→２＋５＋５＋５＋10で27増える(10→37の説明) アルゴリズム的にはＮの時の解を出すプログラムを作れますが 一般的な数式となるとものすごい事になりそうですね… Ｎ＝４→５の時 Ｎ＝３→４の時の『それぞれのブロックは』の数値のみを並べれば １,２,２,２,３,２,２,２,３,２,２,２,３,３,３,３,４です １～４はそれぞれ(１×１＋１)(２×２＋１)(３×３＋１)(４×４＋１)になるはずなので １,５,５,５,10,５,５,５,1,0,５,５,５,10,10,10,10,17 この合計がＮ＝５の時のＬでしょう… これを元にＮ＝６の時のＭは解りますよね？ 始めは面白そうだったのですが、とりあえずここまでで許してください… もう少し簡単かつ理論的に考え直してみます…
- hinebot
- ベストアンサー率37% (1123/2963)
とりあえず４つで考えると ・すべてバラバラ（１２３４）が1通り。 ・要素２つの組合せがあるもの ２つ組合せる組合せ方が 4C2 = 6通り それぞれの組合せ方に対し、残り２つの要素を組合せる場合と組合せない場合があるので（例えば、(ab,c,d)と(ab,cd)のこと） 4C2+4C2 = 12通り （敢えて足し算表記します） といいたいけど、残り２つの要素を組合せたものは 例えば(ab,c,d)からできるものと(a,b,cd)からできるものが（ab,cd)で重複するので半分になる よって、最終的には4C2+(4C2)/2 = 9通り ・要素３つの組合せがあるもの 4C3 = 4C1 = 4通り ・要素４つ全て組合せたもの 1通り 合計 1+9+4+1 = 15通り となる。 一般にnに拡張した場合も同様に考えれば、定式化できそうですが、かなりややこしそうですね。 数字の方も、ちょっと法則を見つけるのに骨折れそう。 役に立ってないですね。済みません。(^^;
補足
まさしくその通りです．私もそこまでたどり着いたのですが，n＝5,6でとたんに重複するものが増えて，どのようなｎに関する式または値で割ればいいのか分からなくて困っています．．．
- kenyamanasi
- ベストアンサー率23% (134/560)
４×３×２×１＝２４ではないですか？ 1111、1112、1113、1114、 1122、1123、1124 1222、1223、1224、 1233、1234、 2222、2223、2224、 2233、2234、 2333、2334、2344、 3333、3334、3344、3444,、4444
補足
1111と2222と3333と4444は同じです．（abcd） また1112と1113と1114も同じです．（abc,d） また，文字が連続しなければならない制約はありません．つまり，１２１３というようにaとcを組み合わせてbとｄは組み合わせないという（ac,b,d）もOKということです．
お礼
ううん・・・ どうしてもアルゴリズムが確立できません。。。 多分しっかり理解できてないんですね。。。 しっかりよく考えてプログラミングがんばってみます。。。
補足
非常に分かりやすい回答本当にありがとうございます！！！！ 最初、私は Σ(i=1～nまで){nCi×Σ{(j=1～n-jまで)n-jCj}} と定式化していましてかなりのダブルブッキングに気がつきませんでしたが、いざ総列挙し始めるとダメなことに気がつきました。 このように漸化式のようになるのですね。。。 急いでCでプログラミングしてみたいと思います。 本当にありがとうございます。