OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

組み合わせの問題

  • すぐに回答を!
  • 質問No.211256
  • 閲覧数41
  • ありがとう数2
  • 気になる数0
  • 回答数7
  • コメント数0

お礼率 13% (5/36)

↑ ○○○・・○
| ●●●・・●
M △△△・・△
種 ▲▲▲・・▲
類 ◆◆◆・・◆
| □□□・・□
↓ ■■■・・■
  ←ーN個ー→

この中からX個を取り出したい。その時の組み合わせの数はいくつになるんでしょう?
通報する
  • 回答数7
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.6
レベル9

ベストアンサー率 75% (28/37)

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

 だいぶ煩雑になりますが、再帰処理を使ってプログラムで数値的に解く
ことは可能のようです。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種以外に全て配分が可能か
等です。プログラムする場合はこのほかにも注意すべき点が多々出て
くると思いますので、注意が必要です。考え方にも問題があるかも
知れませんので、この解答例を参考に新たに考えてみてください。
お礼コメント
googlegoogle

お礼率 13% (5/36)

プログラム作るさいの参考になりました。ありがとうございました。
もう少し煮詰めてみようと思います。
投稿日時 - 2002-02-09 02:19:24
-PR-
-PR-

その他の回答 (全6件)

  • 回答No.2
レベル7

ベストアンサー率 20% (3/15)

直感的ですが、M、N、Xの大小関係は場合分けしないといけない気がします。 それさえ定まればなんとかなるんじゃないでしょうか。 ...続きを読む
直感的ですが、M、N、Xの大小関係は場合分けしないといけない気がします。
それさえ定まればなんとかなるんじゃないでしょうか。
補足コメント
googlegoogle

お礼率 13% (5/36)

M>X>N の場合を考えてます。

もっとしぼるなら、X=14、M=34、N=4でどうでしょう?
投稿日時 - 2002-02-04 15:31:49

  • 回答No.1
レベル13

ベストアンサー率 61% (647/1050)

    一応、補足要求として尋ねます。     これは、何かの式で、答えがあるのでしょうか? それとも簡単な式の答えはないのでしょうか?     何故こう問いかけるかと言いますと、組み合わせ問題には、理論的には解法がなく、実際に数えないとならないという問題が時にあるのです。例えば、組み合わせ問題ではありませんが、或る数以下の素数は幾つあるかというような問題は、一般解がありません。その数以下の素数 ...続きを読む
 
  一応、補足要求として尋ねます。
 
  これは、何かの式で、答えがあるのでしょうか? それとも簡単な式の答えはないのでしょうか?
 
  何故こう問いかけるかと言いますと、組み合わせ問題には、理論的には解法がなく、実際に数えないとならないという問題が時にあるのです。例えば、組み合わせ問題ではありませんが、或る数以下の素数は幾つあるかというような問題は、一般解がありません。その数以下の素数を計算で出して、数えるしかないのです。
 
  この問題も、わたしには、一般解のない、場合に応じて計算しなければならない問題のように思えます。M,N,Xを指定すると、その時の答えが、具体的な「場合分け」計算で出てくるような問題のように思えるということです。
 
  そう思えるのですが、そうでないという人の回答があれば、わたしも参考にしたく思います。(なお、具体的な計算手順というのはありますが、場合分け計算であるので、一般には書くことができないのです)。
 
補足コメント
googlegoogle

お礼率 13% (5/36)

M>X>N の場合を考えてます。

もっとしぼるなら、X=14、M=34、N=4でどうでしょう?
投稿日時 - 2002-02-04 19:09:54
  • 回答No.3
レベル8

ベストアンサー率 37% (6/16)

「M<X<N」の場合ですと、かなり沢山場合分けして求める方法しかおもいつきません。 実際、、X=14、M=34、N=4でも試みましたが、C(コンビネーション)の数が膨大(50個ぐらい)になり、とても計算出来るようなモノではありませんでした。(気分的に・・・) たぶん、スゴイ人が考えれば、画期的な計算方法があると思うので、もう少し、様子を見て下さい。 ちなみに、「M<X<N」ではなく「N≧X>0、M> ...続きを読む
「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の値に依存しないんですね。
って、間違ってたら、ごめんなさいデス。
もう少し、考えてみます。では、また。
  • 回答No.4
レベル9

ベストアンサー率 75% (28/37)

 漸化式を使って表現できそうですのでプログラムを作って数値的に 答えを求められるかと思います。  先ず、この答えを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に関係なく求まります。 ...続きを読む
 漸化式を使って表現できそうですのでプログラムを作って数値的に
答えを求められるかと思います。

 先ず、この答えを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を決定してください。

 概略の考え方は問題ないと思いますが、細部についてのチェックは
お願いします。
  • 回答No.5
レベル9

ベストアンサー率 75% (28/37)

申し訳ありません。ANO#4のtgbですが、明らか な間違い(最初のN個の取り出しの場合の数)があり ますので撤回させていただきます。  ご迷惑をおかけしました。
申し訳ありません。ANO#4のtgbですが、明らか
な間違い(最初のN個の取り出しの場合の数)があり
ますので撤回させていただきます。
 ご迷惑をおかけしました。
  • 回答No.7
レベル10

ベストアンサー率 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通り。 ...続きを読む
結論から言うと答えはまだわかりません。去年までお世話になった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とかの条件でもあればもう少しはやりやすいかもしれませんが…。もっと一般的な方法があるかもしれないし…
お礼コメント
googlegoogle

お礼率 13% (5/36)

プログラム作るさいの参考になりました。ありがとうございました。
もう少し煮詰めてみようと思います。
投稿日時 - 2002-02-09 02:20:31
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ