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

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

A 回答 (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種以外に全て配分が可能か
等です。プログラムする場合はこのほかにも注意すべき点が多々出て
くると思いますので、注意が必要です。考え方にも問題があるかも
知れませんので、この解答例を参考に新たに考えてみてください。
    • good
    • 0
この回答へのお礼

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

お礼日時:2002/02/09 02:19

結論から言うと答えはまだわかりません。

去年までお世話になった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とかの条件でもあればもう少しはやりやすいかもしれませんが…。もっと一般的な方法があるかもしれないし…
    • good
    • 0
この回答へのお礼

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

お礼日時:2002/02/09 02:20

申し訳ありません。

ANO#4のtgbですが、明らか
な間違い(最初のN個の取り出しの場合の数)があり
ますので撤回させていただきます。
 ご迷惑をおかけしました。
    • good
    • 0

 漸化式を使って表現できそうですのでプログラムを作って数値的に


答えを求められるかと思います。

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

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

「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の値に依存しないんですね。
って、間違ってたら、ごめんなさいデス。
もう少し、考えてみます。では、また。
    • good
    • 0

直感的ですが、M、N、Xの大小関係は場合分けしないといけない気がします。


それさえ定まればなんとかなるんじゃないでしょうか。

この回答への補足

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

もっとしぼるなら、X=14、M=34、N=4でどうでしょう?

補足日時:2002/02/04 15:31
    • good
    • 0

 


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

この回答への補足

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

もっとしぼるなら、X=14、M=34、N=4でどうでしょう?

補足日時:2002/02/04 19:09
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Q|aーb|≦|aーc|+|b - c| の証明

|aーb|≦|aーc|+|b - c|  が成り立つ(らしい)のですが、
うまく証明ができません。

証明や直観的な理解の方法など分かる方がいましたら教えてください。
よろしくお願いします。

Aベストアンサー

紙の上に定規で直線引いて, 適当に a と b を決めて, あとは c をいろんなところにおいてじっと見てみる.

Q|a(n+1)|≦r|an|⇒|an|≦r^(n-1)|a1|

|a(n+1)|≦r|an|⇒|an|≦r^(n-1)|a1|

これはどういう変形を行っているのでしょうか?
nで割っている?教えてください。

Aベストアンサー

任意の n ≧ 1 で |a(n+1)| ≦ r |an| ( r>0 )が成り立つと言っているわけですから、
n≧2で |a(n)| ≦ r |a(n-1)|
さらに、n>2 のとき |a(n-1)| ≦ r |a(n-2)| も成り立つのだから、
|a(n)| ≦ r |a(n-1)| ≦ r (r |a(n-2)|) = r^2 |a(n-2)|

これを次々と繰り返せば
|a(n)| ≦ r |a(n-1) ≦ r^2 |a(n-2)| ≦・・・ ≦ r^i |a(n-i)| ≦ r^(i+1) |a(n-i-1)| ≦ ・・・
≦ r^(n-2) |a(2)| ≦ r^(n-1) |a(1)|

∴ n≧2 において、|a(n)| ≦ r^(n-1) |a(1)|

Q不等式 |a-b|<(1/2)|b| ならば |a|>(1/2)|b| (a,b:複素数) の証明

解析の本で
ある複素数列がある複素数に収束するとき
その逆数の数列が収束値の逆数に収束する証明で使われています。
なんか自明のように使われていました。

虫のいいお願いですが、
複素平面を利用した幾何的な証明と
代数的な(式による)証明と
いただけるとうれしいです。

Aベストアンサー

幾何的証明は図を描けば明らかなので、代数的証明を。


|a-b|≧|b|-|a|が成立すれば、
|a|≧|b|-|a-b|>|b|-(1/2)|b|=(1/2)|b|
となるので、|a-b|≧|b|-|a|を証明することにします。


a=a1+ia2、b=b1+ib2、とおくと、
(|a-b|)^2-(|b|-|a|)^2
=(a1-b1)^2+(a2-b2)^2-(a1^2+a2^2+b1^2+b2^2-2|a||b|)
=2(|a||b|-a1b1-a2b2)

ここで、
(|a||b|)^2-(a1b1+a2b2)^2
=(a1^2+a2^2)(b1^2+b2^2)-(a1^2*b1^2+a2^2*b2^2+2a1a2b1b2)
=a1^2*b2^2+a2^2*b1^2-2a1a2b1b2
=(a1b2-a2b1)^2≧0
なので、
(|a-b|)^2-(|b|-|a|)^2≧0

∴|a-b|≧|b|-|a|



なお、|a||b|-(a1b1+a2b2)≧0 は、
内積 a・b=a1b1+a2a2=|a||b|cosθ≦|a||b|
からでも証明可能です。

幾何的証明は図を描けば明らかなので、代数的証明を。


|a-b|≧|b|-|a|が成立すれば、
|a|≧|b|-|a-b|>|b|-(1/2)|b|=(1/2)|b|
となるので、|a-b|≧|b|-|a|を証明することにします。


a=a1+ia2、b=b1+ib2、とおくと、
(|a-b|)^2-(|b|-|a|)^2
=(a1-b1)^2+(a2-b2)^2-(a1^2+a2^2+b1^2+b2^2-2|a||b|)
=2(|a||b|-a1b1-a2b2)

ここで、
(|a||b|)^2-(a1b1+a2b2)^2
=(a1^2+a2^2)(b1^2+b2^2)-(a1^2*b1^2+a2^2*b2^2+2a1a2b1b2)
=a1^2*b2^2+a2^2*b1^2-2a1a2b1b2
=(a1b2-a2b1)^2≧0
なので、
(|a-b|)^2-(|b|-...続きを読む

Q異なる4点A(α)、B(β)、C(γ)、D(δ)で、|α|=|β|=|γ|=|δ|、α+β+γ+δ=

異なる4点A(α)、B(β)、C(γ)、D(δ)で、|α|=|β|=|γ|=|δ|、α+β+γ+δ=0のとき、A、B、C、Dを頂点とする四角形が長方形になることの証明を、どなたかお願いします。

Aベストアンサー

(1) 2次元ユークリッド平面上のベクトルの話だという限定を付けないと、長方形にはならない。(3次元なら、たとえば原点に重心がある正四面体の頂点がα,β,γ,δでも条件を満たすでしょ。)
(2) |α|=0の場合は例外だし、α,β,γ,δのうちに同じものが含まれる場合も例外。
ということに注意した上で
(3) |α|=|β|=|γ|=|δ|=1の場合に証明すれば、他の場合は自明なので、=1の場合だけ考える。
(4) x = (α+β) とすると、αとxがなす角θはxとβがなす角と同じ。
(5) (γ+δ) = -xでなくちゃならない。で、γとxがなす角ξはxとδがなす角と同じ。
あとはθ=ξを示せばよかろ。


人気Q&Aランキング

おすすめ情報