組み合わせの問題

質問

↑　○○○・・○
｜　●●●・・●
Ｍ　△△△・・△
種　▲▲▲・・▲
類　◆◆◆・・◆
｜　□□□・・□
↓　■■■・・■
　　←ーＮ個ー→

この中からＸ個を取り出したい。その時の組み合わせの数はいくつになるんでしょう？

回答No.6

tgb · ベストアンサー

汚名挽回のため、引き続き、考えてみました。

　だいぶ煩雑になりますが、再帰処理を使ってプログラムで数値的に解く
ことは可能のようです。Ｃ、Ｈ、ＧはＡＮｏ．＃４と同様にします。
また、取り出す対象を取りあえず「石」としておきます。

　先ず、どの種類についても個数Ｘまで取り出すことが可能とする問題を
考えると
　　　Ｇ（Ｍ，Ｘ，Ｘ）＝Ｈ（Ｍ，Ｘ）
この場合の数のうち、１種類でもＮを越える個数を取り出しているケース
になる場合の数を
　　　Ｆ（Ｍ，Ｎ，Ｘ）
とすると、求める場合の数は
　　　Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ，Ｘ）－Ｆ（Ｍ，Ｎ，Ｘ）
ここで、Ｘ＞Ｎを想定して、
　　　Ｘ＝ｋ・Ｎ１＋ｘ　（Ｎ１＝Ｎ＋１、０＜＝ｘ＜Ｎ１、ｋ＞＝１）
とします。即ちｋは取り出し個数がＮを越えるような最大の種類数です。
このような設定でＦを数え上げることを考えます。
　Ｆ（Ｍ，Ｎ，Ｘ）の場合の数を取り出し個数がＮを越える種類が何種類
あるかで分類すると
　　　ｉ＝１，２，．．．ｋ　　（ｉ＝３なら「３種類ある」とする）
のｋ通りで、このｉの各々についてどの種類をｉ（個の）種類選択するか
でＣ（Ｍ，ｉ）通り考えられるます。
このＣ（Ｍ，ｉ）通りの各々について、残りの石をどう配分して取り出す
かを考えます。
取り出すべき石の残りの個数は
　　　ｙ＝Ｘ－ｉ・Ｎ１＝ｘ＋（ｋ－ｉ）・Ｎ１
このうちｊ個を選択されたｉ種のいずれかに追加配分し、更に
その残り（ｙ－ｊ）個をそれ以外の種類（ｉ種以外）にＮ個を越えない
ように配分することにするとします。このような処理に対する場合の数は
　　ｚ＝ｍｉｎ（ｙ，（Ｘ－Ｎ１）・ｉ）
として、ｊ＝１，２，．．．．，ｚの各々に対して
・ｊ個をｉ種に追加配分する場合の数がＧ（ｉ，Ｎ－ｉ，ｊ）通り、
・この各々に対して残りの石（ｙ－ｊ）個を選択されたｉ種以外に配分
　する場合の数がＧ（Ｍ－ｉ，Ｎ，ｙ－ｊ）通り
となります。

　以上をまとめて
　　Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ、Ｘ）

　　　　　　　　　　　ｉ＝ｋ
　　　　　　　　　－　　Σ　　Ｃ（Ｍ，ｉ）・Ｄ（ｉ）
　　　　　　　　　　　ｉ＝１
　　　　　　ｊ＝ｚ
　　Ｄ（ｉ）＝Σ　Ｇ（ｉ，Ｎ－ｉ，ｊ）・Ｇ（Ｍ－ｉ，Ｎ，ｙ－ｊ）
　　　　　　ｊ＝１
　　　　但し、ｋ、ｙ、ｚはＭ、Ｎ、Ｘ、ｉに応じて計算された値
となります。
　Ｇの小さくなったパラメータに対して再帰的に値を求める処理を繰り
返し、最終的にはＨ、Ｃで求められるようになります。

　上の式で、細かい点についての配慮が欠けている部分があります。
例えば、
・Ｇ（ｉ，Ｎ－ｉ，ｊ）でＮ＜＝ｉとなる場合
・残りの石（ｙ－ｊ）個を選択されたｉ種以外に全て配分が可能か
等です。プログラムする場合はこのほかにも注意すべき点が多々出て
くると思いますので、注意が必要です。考え方にも問題があるかも
知れませんので、この解答例を参考に新たに考えてみてください。

お礼

プログラム作るさいの参考になりました。ありがとうございました。
もう少し煮詰めてみようと思います。

回答No.7

guowu-x

結論から言うと答えはまだわかりません。去年までお世話になったZ会の問題を解いてるような気分です。
N＞＝X>0，M>0のときはいいですね。No3の人が書いている通りで重複順列です。
で、M＞X>Nより、M種類全部は使えません。この場合が１通り。
M-N＝０のとき　M=Nで全部同じ種類をとる。これがM通り。
M-N＝１のとき　同じのがN+1個になっちゃうのがあってこれもM通り。
M-N＝２のとき　N+1個が同じで残りはM種の内なんでもいい。よって、M・(CのMの1　これはCの右がM、左が１ということをあらわす。）＝Mの２乗
という風にやって
M-N＝ｋのとき　M・(CのM＋k-2のM-1)＝M(M+k-2）!/(k-1)!（M-1)!でΣというのも考えましたが計算がややこしいうえ、M-N=2k，3kとなったらどうするかという問題があり悩んでいます。別の方法も含めてもう少し考えてみます。２N>Mとかの条件でもあればもう少しはやりやすいかもしれませんが…。もっと一般的な方法があるかもしれないし…

お礼

プログラム作るさいの参考になりました。ありがとうございました。
もう少し煮詰めてみようと思います。

回答No.5

tgb

申し訳ありません。ＡＮＯ＃４のｔｇｂですが、明らか
な間違い（最初のＮ個の取り出しの場合の数）があり
ますので撤回させていただきます。
　ご迷惑をおかけしました。

回答No.4

tgb

漸化式を使って表現できそうですのでプログラムを作って数値的に
答えを求められるかと思います。

　先ず、この答えをＧ（Ｍ，Ｎ，Ｘ）で表します。また、よく知られて
いるＭ種からＸ個取り出す場合の数をＨ（Ｍ，Ｘ）、Ｎ個からＸ個取り
出す場合の数をＣ（Ｎ，Ｘ）とします。
　そこで、場合分けをして、
１）Ｘ＜＝Ｎの場合
　　　　Ｇ（Ｍ，Ｎ，Ｘ）＝Ｈ（Ｍ，Ｘ）
　　と、Ｎに関係なく求まります。
２）Ｘ＞Ｎの場合
　　この場合は工夫が必要で漸化式を使って求めます。
　Ｘ＞Ｎですから、手始めにＮ個のみ取り出すことを考えます。この
　場合、Ｍ種の中から１種類まるまる取ることになるのでＭ通りとなり
　ます。残ったＸ－Ｎ個はＭ通りの各々に対して残りから取り出す場合
　の数になります。これは
　　　　Ｍ－１　＜－－－　Ｍ
　　　　Ｘ－Ｎ　＜－－－　Ｘ
　　　　Ｎ　　　＜－－－　Ｎ
　のように置き換えて元の問題と同様になり、Ｇの式を使って表現
　できます。

　従って元の問題は次のように漸化式を使って表せます。
　　　　Ｇ（Ｍ，Ｎ，Ｘ）＝　Ｈ（Ｍ，Ｘ）
　　　　　　　　　　　　　　　　　　　　　　　　（Ｘ＜＝Ｎ）
　　　　　　　　　　　　＝　Ｍ＊Ｇ（Ｍ－１，Ｎ，Ｘ－Ｎ）
　　　　　　　　　　　　　　　　　　　　　　　　（Ｘ＞Ｎ）
また、
　　　　Ｇ（１，Ｎ，Ｘ）＝　Ｃ（Ｎ，Ｘ）
結局次のような形になります。
　　　　Ｇ（Ｍ，Ｎ，Ｘ）
　　　　　　＝Ｍ・（Ｍ－１）・．．．．（Ｉ＋１）・ｇ（Ｉ，Ｎ，Ｊ）
ｇ（Ｉ，Ｎ，Ｊ）は　Ｈ（Ｉ，Ｊ）、Ｃ（Ｎ，Ｘ）のいずれかであり、
ｇ、ＩはＭ、Ｎ、Ｘにより決まりますので、Ｍ、Ｘを順次小さくして
行ってｇ、Ｉを決定してください。

　概略の考え方は問題ないと思いますが、細部についてのチェックは
お願いします。

回答No.3

nyonta

「Ｍ＜Ｘ＜Ｎ」の場合ですと、かなり沢山場合分けして求める方法しかおもいつきません。
実際、、Ｘ＝１４、Ｍ＝３４、Ｎ＝４でも試みましたが、Ｃ(コンビネーション)の数が膨大(50個ぐらい)になり、とても計算出来るようなモノではありませんでした。(気分的に・・・)
たぶん、スゴイ人が考えれば、画期的な計算方法があると思うので、もう少し、様子を見て下さい。
ちなみに、「Ｍ＜Ｘ＜Ｎ」ではなく「Ｎ≧Ｘ＞0、Ｍ＞0」であれば、簡単に出来ます。
(X+M-1)/{(M-1)!X!}
により求められます。そう、Ｎの値に依存しないんですね。
って、間違ってたら、ごめんなさいデス。
もう少し、考えてみます。では、また。

回答No.2

hiroshi0405

直感的ですが、M、N、Xの大小関係は場合分けしないといけない気がします。
それさえ定まればなんとかなるんじゃないでしょうか。

補足

Ｍ＞Ｘ＞Ｎ　の場合を考えてます。

もっとしぼるなら、Ｘ＝１４、Ｍ＝３４、Ｎ＝４でどうでしょう？

回答No.1

starflora

一応、補足要求として尋ねます。

　　これは、何かの式で、答えがあるのでしょうか？　それとも簡単な式の答えはないのでしょうか？

　　何故こう問いかけるかと言いますと、組み合わせ問題には、理論的には解法がなく、実際に数えないとならないという問題が時にあるのです。例えば、組み合わせ問題ではありませんが、或る数以下の素数は幾つあるかというような問題は、一般解がありません。その数以下の素数を計算で出して、数えるしかないのです。

　　この問題も、わたしには、一般解のない、場合に応じて計算しなければならない問題のように思えます。Ｍ，Ｎ，Ｘを指定すると、その時の答えが、具体的な「場合分け」計算で出てくるような問題のように思えるということです。

　　そう思えるのですが、そうでないという人の回答があれば、わたしも参考にしたく思います。（なお、具体的な計算手順というのはありますが、場合分け計算であるので、一般には書くことができないのです）。

補足

Ｍ＞Ｘ＞Ｎ　の場合を考えてます。

もっとしぼるなら、Ｘ＝１４、Ｍ＝３４、Ｎ＝４でどうでしょう？