- ベストアンサー
組み合わせの問題
↑ ○○○・・○ | ●●●・・● M △△△・・△ 種 ▲▲▲・・▲ 類 ◆◆◆・・◆ | □□□・・□ ↓ ■■■・・■ ←ーN個ー→ この中からX個を取り出したい。その時の組み合わせの数はいくつになるんでしょう?
- googlegoogle
- お礼率13% (5/36)
- 数学・算数
- 回答数7
- ありがとう数2
- みんなの回答 (7)
- 専門家の回答
質問者が選んだベストアンサー
汚名挽回のため、引き続き、考えてみました。 だいぶ煩雑になりますが、再帰処理を使ってプログラムで数値的に解く ことは可能のようです。C、H、GはANo.#4と同様にします。 また、取り出す対象を取りあえず「石」としておきます。 先ず、どの種類についても個数Xまで取り出すことが可能とする問題を 考えると G(M,X,X)=H(M,X) この場合の数のうち、1種類でもNを越える個数を取り出しているケース になる場合の数を F(M,N,X) とすると、求める場合の数は G(M,N,X)=H(M,X)-F(M,N,X) ここで、X>Nを想定して、 X=k・N1+x (N1=N+1、0<=x<N1、k>=1) とします。即ちkは取り出し個数がNを越えるような最大の種類数です。 このような設定でFを数え上げることを考えます。 F(M,N,X)の場合の数を取り出し個数がNを越える種類が何種類 あるかで分類すると i=1,2,...k (i=3なら「3種類ある」とする) のk通りで、このiの各々についてどの種類をi(個の)種類選択するか でC(M,i)通り考えられるます。 このC(M,i)通りの各々について、残りの石をどう配分して取り出す かを考えます。 取り出すべき石の残りの個数は y=X-i・N1=x+(k-i)・N1 このうちj個を選択されたi種のいずれかに追加配分し、更に その残り(y-j)個をそれ以外の種類(i種以外)にN個を越えない ように配分することにするとします。このような処理に対する場合の数は z=min(y,(X-N1)・i) として、j=1,2,....,zの各々に対して ・j個をi種に追加配分する場合の数がG(i,N-i,j)通り、 ・この各々に対して残りの石(y-j)個を選択されたi種以外に配分 する場合の数がG(M-i,N,y-j)通り となります。 以上をまとめて G(M,N,X)=H(M、X) i=k - Σ C(M,i)・D(i) i=1 j=z D(i)=Σ G(i,N-i,j)・G(M-i,N,y-j) j=1 但し、k、y、zはM、N、X、iに応じて計算された値 となります。 Gの小さくなったパラメータに対して再帰的に値を求める処理を繰り 返し、最終的にはH、Cで求められるようになります。 上の式で、細かい点についての配慮が欠けている部分があります。 例えば、 ・G(i,N-i,j)でN<=iとなる場合 ・残りの石(y-j)個を選択されたi種以外に全て配分が可能か 等です。プログラムする場合はこのほかにも注意すべき点が多々出て くると思いますので、注意が必要です。考え方にも問題があるかも 知れませんので、この解答例を参考に新たに考えてみてください。
その他の回答 (6)
- guowu-x
- ベストアンサー率41% (33/80)
結論から言うと答えはまだわかりません。去年までお世話になったZ会の問題を解いてるような気分です。 N>=X>0,M>0のときはいいですね。No3の人が書いている通りで重複順列です。 で、M>X>Nより、M種類全部は使えません。この場合が1通り。 M-N=0のとき M=Nで全部同じ種類をとる。これがM通り。 M-N=1のとき 同じのがN+1個になっちゃうのがあってこれもM通り。 M-N=2のとき N+1個が同じで残りはM種の内なんでもいい。よって、M・(CのMの1 これはCの右がM、左が1ということをあらわす。)=Mの2乗 という風にやって M-N=kのとき M・(CのM+k-2のM-1)=M(M+k-2)!/(k-1)!(M-1)!でΣというのも考えましたが計算がややこしいうえ、M-N=2k,3kとなったらどうするかという問題があり悩んでいます。別の方法も含めてもう少し考えてみます。2N>Mとかの条件でもあればもう少しはやりやすいかもしれませんが…。もっと一般的な方法があるかもしれないし…
お礼
プログラム作るさいの参考になりました。ありがとうございました。 もう少し煮詰めてみようと思います。
- tgb
- ベストアンサー率78% (32/41)
申し訳ありません。ANO#4のtgbですが、明らか な間違い(最初のN個の取り出しの場合の数)があり ますので撤回させていただきます。 ご迷惑をおかけしました。
- tgb
- ベストアンサー率78% (32/41)
漸化式を使って表現できそうですのでプログラムを作って数値的に 答えを求められるかと思います。 先ず、この答えをG(M,N,X)で表します。また、よく知られて いるM種からX個取り出す場合の数をH(M,X)、N個からX個取り 出す場合の数をC(N,X)とします。 そこで、場合分けをして、 1)X<=Nの場合 G(M,N,X)=H(M,X) と、Nに関係なく求まります。 2)X>Nの場合 この場合は工夫が必要で漸化式を使って求めます。 X>Nですから、手始めにN個のみ取り出すことを考えます。この 場合、M種の中から1種類まるまる取ることになるのでM通りとなり ます。残ったX-N個はM通りの各々に対して残りから取り出す場合 の数になります。これは M-1 <--- M X-N <--- X N <--- N のように置き換えて元の問題と同様になり、Gの式を使って表現 できます。 従って元の問題は次のように漸化式を使って表せます。 G(M,N,X)= H(M,X) (X<=N) = M*G(M-1,N,X-N) (X>N) また、 G(1,N,X)= C(N,X) 結局次のような形になります。 G(M,N,X) =M・(M-1)・....(I+1)・g(I,N,J) g(I,N,J)は H(I,J)、C(N,X)のいずれかであり、 g、IはM、N、Xにより決まりますので、M、Xを順次小さくして 行ってg、Iを決定してください。 概略の考え方は問題ないと思いますが、細部についてのチェックは お願いします。
- nyonta
- ベストアンサー率37% (6/16)
「M<X<N」の場合ですと、かなり沢山場合分けして求める方法しかおもいつきません。 実際、、X=14、M=34、N=4でも試みましたが、C(コンビネーション)の数が膨大(50個ぐらい)になり、とても計算出来るようなモノではありませんでした。(気分的に・・・) たぶん、スゴイ人が考えれば、画期的な計算方法があると思うので、もう少し、様子を見て下さい。 ちなみに、「M<X<N」ではなく「N≧X>0、M>0」であれば、簡単に出来ます。 (X+M-1)/{(M-1)!X!} により求められます。そう、Nの値に依存しないんですね。 って、間違ってたら、ごめんなさいデス。 もう少し、考えてみます。では、また。
- hiroshi0405
- ベストアンサー率20% (3/15)
直感的ですが、M、N、Xの大小関係は場合分けしないといけない気がします。 それさえ定まればなんとかなるんじゃないでしょうか。
補足
M>X>N の場合を考えてます。 もっとしぼるなら、X=14、M=34、N=4でどうでしょう?
- starflora
- ベストアンサー率61% (647/1050)
一応、補足要求として尋ねます。 これは、何かの式で、答えがあるのでしょうか? それとも簡単な式の答えはないのでしょうか? 何故こう問いかけるかと言いますと、組み合わせ問題には、理論的には解法がなく、実際に数えないとならないという問題が時にあるのです。例えば、組み合わせ問題ではありませんが、或る数以下の素数は幾つあるかというような問題は、一般解がありません。その数以下の素数を計算で出して、数えるしかないのです。 この問題も、わたしには、一般解のない、場合に応じて計算しなければならない問題のように思えます。M,N,Xを指定すると、その時の答えが、具体的な「場合分け」計算で出てくるような問題のように思えるということです。 そう思えるのですが、そうでないという人の回答があれば、わたしも参考にしたく思います。(なお、具体的な計算手順というのはありますが、場合分け計算であるので、一般には書くことができないのです)。
補足
M>X>N の場合を考えてます。 もっとしぼるなら、X=14、M=34、N=4でどうでしょう?
関連するQ&A
- 重複組み合わせの問題
重複組み合わせの問題で、問題集の回答を読んでも、理解できません。教科書には載っていないので、どう考えていいかも分かりません。解説していただけませんでしょうか? 問 x+y+z=12を満たす自然数の組はいくつあるか? 回答 x+1=X , y+1=Y , z+1=Z とおくと、 X+Y+Z=9 (ここまでは理解できます。) X,Y,Zは負ではない。(?) 例えば、X=3 , Y=2 , Z=4 とすると (X,X,X,Y,Y,Z,Z,Z)の3種から重複して 9個をとる重複組み合わせを考える。 _______________________ ?くらいから、分からなくなりました。 ちなみに、答えは55通りです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 組み合わせの問題です
組み合わせの問題です。正の整数nと整数K(0≦k≦n)に対してnCkは正の整数である事実を使って良い。 pを2以上の素数とする。このとき、任意の正の整数nに対し、(n+1)^p‐n^p ‐1はpで割り切れることを示せ です。 わからないのでどなかた教えてください。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 組み合わせの問題なんですが
16個の中から7個選ぶときの組み合わせの数なんですが、 (16*15*14*13*12*11*10) ÷ (7*6*5*4*3*2*1) = 11440 という計算であってますか? wikiの数式みてもよくわからなくて…すみませんがご教授願います。
- ベストアンサー
- 数学・算数
- 同じ物を含む順列、組み合わせについて
nPr や nCr という公式は 異なるn個の中からr個選んで並べる数 異なるn個の中からr個選ぶ組み合わせの数 ですが 異なる4個、同じ3個から2個選んで並べたり組み合わせるといった時は、この公式を使うことは出来ないのでしょうか? 選ばない順列の場合 AAABという単語の並び替えの個数はまず4!で計算してその後3!で割ることで 求めることが出来ますが 選ぶ場合はそのように公式でまず求めて、そこから何か操作することで真の数を求める方法は無いのでしょうか?
- ベストアンサー
- 数学・算数
- 組み合わせ記号の問題(第二種スターリング数)
Σ[k=0…n] (-1)^(n+k) * C[n+1, k+1] * (k+1)^m = Σ[k=0…n] (-1)^k * C[n, k] * (n-k)^m が示せなくて困っています。 これは、「m人が全n曲中1曲聞いてくるとき、全ての曲が少なくとも一回は聞かれている場合の数」の一般項を表しています。 エクセルで計算したところ二式は等しかったので、等しいことは確かです。 元々は、「m人のグループがn曲中l曲聞いてくる時、グループ全体でX曲聞きこぼしている場合の数」を求めるという問題を考察していたところ上記の数列の一般項を求める事に辿り着きました。 一般項は求まったのですが、ネットで実際の項で検索してみたところ、同じ数列が別の式で表されていました。 上の式が自分で出した式で下が載っていた式なのですが、そのサイトには説明は載っていませんでした。そこで上の式から下の式を出そうとしたのですが、それが上手くいきませんでした。 ちなみに同サイトに依ると第二種スターリング数S_2(n,m)を使って m!*S_2(n,m)とも表せるそうです。 分かる方いらっしゃいましたら、どうかよろしくお願いします!
- ベストアンサー
- 数学・算数
- 組み合わせの問題について
初歩的な質問で失礼します。 「コインを5枚投げた時、2枚が表になる場合の数」が10通りになるという計算の導き出し方として、5C2=10 となる理由がよく分かりません。 組み合わせの基本的な考え方として、5つの異なる色のボールから2つを取り出す組み合わせが上記の式で算出される理由は分かるのですが・・ なぜコインを5枚投げた時、2枚が表になる場合の数の出し方が5C2となるのか、教えて頂けないでしょうか。
- ベストアンサー
- 数学・算数
- 組み合わせの問題といえるのでしょうか?
赤い玉3個、白い玉2個の5個の中から、3個同時にとる場合、とり方は何通りあるかという問題は、「組み合わせ」の問題のようですが、5C3=10の10通りではなく、「赤、赤、赤」「赤、赤、白」「赤、白、白」の3通りだと思うのですが、組み合わせの問題とはいえないのでしょうか?この程度の数であれば、直感的にわかりますが、数が増えた場合にはどのように考えればよいのでしょうか?
- 締切済み
- 数学・算数
- 素数と組み合わせの問題
Z会の問題なのですが、わからないところがあるので質問します。 nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。 (1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。 (2)nと(2^n)-1は互いに素であることを示せ。 nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。
- ベストアンサー
- 数学・算数
お礼
プログラム作るさいの参考になりました。ありがとうございました。 もう少し煮詰めてみようと思います。