- ベストアンサー
組み合わせの問題
tgbの回答
- tgb
- ベストアンサー率78% (32/41)
漸化式を使って表現できそうですのでプログラムを作って数値的に 答えを求められるかと思います。 先ず、この答えをＧ（Ｍ，Ｎ，Ｘ）で表します。また、よく知られて いるＭ種からＸ個取り出す場合の数をＨ（Ｍ，Ｘ）、Ｎ個からＸ個取り 出す場合の数をＣ（Ｎ，Ｘ）とします。 そこで、場合分けをして、 １）Ｘ＜＝Ｎの場合 Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ，Ｘ） と、Ｎに関係なく求まります。 ２）Ｘ＞Ｎの場合 この場合は工夫が必要で漸化式を使って求めます。 Ｘ＞Ｎですから、手始めにＮ個のみ取り出すことを考えます。この 場合、Ｍ種の中から１種類まるまる取ることになるのでＭ通りとなり ます。残ったＸ－Ｎ個はＭ通りの各々に対して残りから取り出す場合 の数になります。これは Ｍ－１ ＜－－－ Ｍ Ｘ－Ｎ ＜－－－ Ｘ Ｎ ＜－－－ Ｎ のように置き換えて元の問題と同様になり、Ｇの式を使って表現 できます。 従って元の問題は次のように漸化式を使って表せます。 Ｇ（Ｍ，Ｎ，Ｘ）＝ Ｈ（Ｍ，Ｘ） （Ｘ＜＝Ｎ） ＝ Ｍ＊Ｇ（Ｍ－１，Ｎ，Ｘ－Ｎ） （Ｘ＞Ｎ） また、 Ｇ（１，Ｎ，Ｘ）＝ Ｃ（Ｎ，Ｘ） 結局次のような形になります。 Ｇ（Ｍ，Ｎ，Ｘ） ＝Ｍ・（Ｍ－１）・．．．．（Ｉ＋１）・ｇ（Ｉ，Ｎ，Ｊ） ｇ（Ｉ，Ｎ，Ｊ）は Ｈ（Ｉ，Ｊ）、Ｃ（Ｎ，Ｘ）のいずれかであり、 ｇ、ＩはＭ、Ｎ、Ｘにより決まりますので、Ｍ、Ｘを順次小さくして 行ってｇ、Ｉを決定してください。 概略の考え方は問題ないと思いますが、細部についてのチェックは お願いします。
関連する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)の３種から重複して ９個をとる重複組み合わせを考える。 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ ？くらいから、分からなくなりました。 ちなみに、答えは55通りです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 組み合わせの問題です
組み合わせの問題です。正の整数ｎと整数K(０≦ｋ≦ｎ)に対してnＣkは正の整数である事実を使って良い。 pを2以上の素数とする。このとき、任意の正の整数ｎに対し、(n＋１)^p‐n^p ‐１は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通りになるという計算の導き出し方として、5Ｃ2＝10 となる理由がよく分かりません。 組み合わせの基本的な考え方として、5つの異なる色のボールから2つを取り出す組み合わせが上記の式で算出される理由は分かるのですが・・ なぜコインを5枚投げた時、2枚が表になる場合の数の出し方が5Ｃ2となるのか、教えて頂けないでしょうか。
- ベストアンサー
- 数学・算数
- 組み合わせの問題といえるのでしょうか？
赤い玉3個、白い玉２個の５個の中から、3個同時にとる場合、とり方は何通りあるかという問題は、「組み合わせ」の問題のようですが、５Ｃ３＝１０の１０通りではなく、「赤、赤、赤」「赤、赤、白」「赤、白、白」の3通りだと思うのですが、組み合わせの問題とはいえないのでしょうか？この程度の数であれば、直感的にわかりますが、数が増えた場合にはどのように考えればよいのでしょうか？
- 締切済み
- 数学・算数
- 素数と組み合わせの問題
Z会の問題なのですが、わからないところがあるので質問します。 nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。 (1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。 (2)nと(2^n)-1は互いに素であることを示せ。 nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。
- ベストアンサー
- 数学・算数