- ベストアンサー
組み合わせの問題
tgbの回答
汚名挽回のため、引き続き、考えてみました。 だいぶ煩雑になりますが、再帰処理を使ってプログラムで数値的に解く ことは可能のようです。Ｃ、Ｈ、ＧはＡＮｏ．＃４と同様にします。 また、取り出す対象を取りあえず「石」としておきます。 先ず、どの種類についても個数Ｘまで取り出すことが可能とする問題を 考えると Ｇ（Ｍ，Ｘ，Ｘ）＝Ｈ（Ｍ，Ｘ） この場合の数のうち、１種類でもＮを越える個数を取り出しているケース になる場合の数を Ｆ（Ｍ，Ｎ，Ｘ） とすると、求める場合の数は Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ，Ｘ）－Ｆ（Ｍ，Ｎ，Ｘ） ここで、Ｘ＞Ｎを想定して、 Ｘ＝ｋ・Ｎ１＋ｘ （Ｎ１＝Ｎ＋１、０＜＝ｘ＜Ｎ１、ｋ＞＝１） とします。即ちｋは取り出し個数がＮを越えるような最大の種類数です。 このような設定でＦを数え上げることを考えます。 Ｆ（Ｍ，Ｎ，Ｘ）の場合の数を取り出し個数がＮを越える種類が何種類 あるかで分類すると ｉ＝１，２，．．．ｋ （ｉ＝３なら「３種類ある」とする） のｋ通りで、このｉの各々についてどの種類をｉ（個の）種類選択するか でＣ（Ｍ，ｉ）通り考えられるます。 このＣ（Ｍ，ｉ）通りの各々について、残りの石をどう配分して取り出す かを考えます。 取り出すべき石の残りの個数は ｙ＝Ｘ－ｉ・Ｎ１＝ｘ＋（ｋ－ｉ）・Ｎ１ このうちｊ個を選択されたｉ種のいずれかに追加配分し、更に その残り（ｙ－ｊ）個をそれ以外の種類（ｉ種以外）にＮ個を越えない ように配分することにするとします。このような処理に対する場合の数は ｚ＝ｍｉｎ（ｙ，（Ｘ－Ｎ１）・ｉ） として、ｊ＝１，２，．．．．，ｚの各々に対して ・ｊ個をｉ種に追加配分する場合の数がＧ（ｉ，Ｎ－ｉ，ｊ）通り、 ・この各々に対して残りの石（ｙ－ｊ）個を選択されたｉ種以外に配分 する場合の数がＧ（Ｍ－ｉ，Ｎ，ｙ－ｊ）通り となります。 以上をまとめて Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ、Ｘ） ｉ＝ｋ － Σ Ｃ（Ｍ，ｉ）・Ｄ（ｉ） ｉ＝１ ｊ＝ｚ Ｄ（ｉ）＝Σ Ｇ（ｉ，Ｎ－ｉ，ｊ）・Ｇ（Ｍ－ｉ，Ｎ，ｙ－ｊ） ｊ＝１ 但し、ｋ、ｙ、ｚはＭ、Ｎ、Ｘ、ｉに応じて計算された値 となります。 Ｇの小さくなったパラメータに対して再帰的に値を求める処理を繰り 返し、最終的にはＨ、Ｃで求められるようになります。 上の式で、細かい点についての配慮が欠けている部分があります。 例えば、 ・Ｇ（ｉ，Ｎ－ｉ，ｊ）でＮ＜＝ｉとなる場合 ・残りの石（ｙ－ｊ）個を選択されたｉ種以外に全て配分が可能か 等です。プログラムする場合はこのほかにも注意すべき点が多々出て くると思いますので、注意が必要です。考え方にも問題があるかも 知れませんので、この解答例を参考に新たに考えてみてください。
関連する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の倍数になることがどうしても証明できません。どなたか教えてください。
- ベストアンサー
- 数学・算数
お礼
プログラム作るさいの参考になりました。ありがとうございました。 もう少し煮詰めてみようと思います。