組み合わせの数式の質問です

A
B
C
D
.
.
.
Z
の中から任意の個数を選んで組み合わせをつくります。

AとBとDとZ
とか
AとBとDとXとYとZ
とか
1個も数に含めます。
ただし、AとBは同時に使えませんといったような制約があります。

■ABCDEFGH
A_○○○×○○○
B○_○○○×○○
C○○_○○○○○
D○○○_×○×○
E×○○×_○○○
F○×○○○_○○
G○○○×○○_○
H○○○○○○○_

※×は組み合わせ不可能
※1から5個まで選べる
※順は組み合わせに含まない ABCとCBAは一緒。

例えばこういった場合には
どういった数式で答えを出せば良いのでしょうか?
ズバリの方には200pt~差し上げます。
出来れば数が増えた場合への応用の仕方、選ぶ数が増えた場合の応用の仕方、
便利な計算ソフト等々も教えてもらえると幸いです。
よろしくお願い致します。

回答の条件
  • 1人2回まで
  • 登録:2006/05/05 21:10:34
  • 終了:2006/05/12 21:15:02

回答(7件)

id:l-lol-l No.1

l-lol-l回答回数310ベストアンサー獲得回数102006/05/05 21:52:59

ポイント18pt

答としてなにを求めているのでしょうか?

それがわからないと、回答のしようがありません。

id:reosucker

あ、すいません。

組み合わせの総数です。

何通りの組み合わせが作り出せるかです。

2006/05/05 22:09:22
id:kenfujita No.2

kenfujita回答回数29ベストアンサー獲得回数02006/05/05 23:09:46

ポイント17pt

同じ文字が2度出てくるようなのはどうするですか?

例えばAとAAは、別として考えるのですか?

表では_となっていますが・・・

id:reosucker

AとAは組み合わせできませんので

_としてます。

2006/05/06 02:13:01
id:jmpi No.3

jmpi回答回数29ベストアンサー獲得回数12006/05/05 23:42:19

ポイント17pt

8個の数から5個選ぶと8!/5!3!=56通り。(A)


その内、組み合わせAEを含む組み合わせは6!/3!3!=20通り。同様にBF,DE,DGを含む組み合わせも20通り。(B)


また、(B)の中でAEとBFを同時に含むものは4通り。同様にAEとDG、BFとDE,BFとDGを含むものも4通り。(C1)

更に、AEとDEを同時に含むものは5!/2!3!=10通り。同様にDEとDGを含むものも10通り。(C2)


また、(C1)(C2)の中で、AEとDEとBFを含むものは1通り。同様にDEとDGとBFを含むものも1通り。(D1)

更にAEとDEとDGを含むものは4通り。(D2)AEとBFとDGは含み得ない。


また、AEとBFとDEとDGは含み得ない。


以上より56(A)-4*20(B)+(4*4+10*2)(C)-(1*2+4)(D)=6

答えは6通りです。


と、書いたものの大分冗長な解き方ですね…。数が大きくなると手では解け無そうです。これは求めていた答えにはならないっぽいですね。一応この軸でプログラムを組めば対応出来るのでは、と言い訳^^;。

id:reosucker

実際は30以上の中から行いますので、

数式が欲しいですね。

含み得ない組み合わせも多数となりますので。

2006/05/06 02:14:08
id:l-lol-l No.4

l-lol-l回答回数310ベストアンサー獲得回数102006/05/06 07:19:40

ポイント17pt

私が解く場合もjmplさんと同じ方法ですね。

まず、すべての組み合わせを数えてそれから駄目な組み合わせを抜く。

ただ、問題なのが、駄目な組み合わせがたくさんあり、それをひとつずつ抜くのに適当な方法がなく、人海戦術で抜くしかなさそうな点です。

数式ですが次のようになります。

x個のアルファベットからy個を順不同で取り出す組み合わせの数をコンビネーションといい、

xCyであらわします。この場合yは1~5で、xは8なので、

8C5+8C4+8C3+8C2+8C1が、駄目な組み合わせを含んだすべての組み合わせ数になります。

xCyは x!/(y-x)!y!で計算できます。!は階乗です。従って、

8!/5!3!+8!/4!4!+8!/3!5!+8!/2!6!+8!/1!7!

=56+70+56+28+8

=218

ここから駄目な場合をひくのですが、問題はすべての場合を丹念に広い、重複を避けなければならない点ですね。

だめな組み合わせはAE,BF,DE,DG

AEを含む組み合わせは、AEを除く残り6個のなかから3個、2個、1個、0個を選ぶ組み合わせですので、それぞれ6C3,6C2,6C1,6C0に成ります。これは6!/3!3!+6!/2!4!+6!/1!4!+6!/0!/6!=20+15+6+1=42通り

BFを含む組み合わせは、同じく42通りですが、

このうちAEを含む組み合わせはすでにカウントしてますので引かなければなりません。

AEBFを含む組み合わせは、AEBFを除く残り4個の中から1個、0個組み合わせですので、それぞれ4C1,4C0に成ります。これは4!/1!3!+4!/0!4!=4+1=5通り

DEを含む組み合わせは、同じく42通りですが、

このうちAEおよびBFを含む組み合わせはすでにカウントしてますので引かなければなりません。

ADEを含む組み合わせは、ADEを除く残り5個の中から2個、1個、0個選ぶ組み合わせですので、それぞれ5C2,5C1,5C0に成ります。これは5!/2!3!+5!/1!4!+5!/0!5!=10+5+1=16通り

BFDEを含む組み合わせは、BFDEを除く残り4個の中から1個、0個組み合わせですので、それぞれ4C1,4C0に成ります。これは4!/1!3!+4!/0!4!=4+1=5通り

さらに問題は、この抜く数を数える過程で、ADEBFを2回カウントしているので、これを元に戻さないといけないので+1

DGを含む組み合わせは、同じく42通りですが、

このうちAE,BFおよびDEを含む組み合わせはすでにカウントしてますので引かなければなりません。

DEGを含む組み合わせは、DEGを除く残り5個の中から2個、1個、0個選ぶ組み合わせですので、それぞれ5C2,5C1,5C0に成ります。これは5!/2!3!+5!/1!4!+5!/0!5!=10+5+1=16通り

AEDGを含む組み合わせは、DEGを含む組み合わせにすべて入ってますから、数えてはいけません。

BFDGを含む組み合わせは、BFDGを除く残り4個の中から1個、0個選ぶ組み合わせですので、それぞれ4C1,4C0に成ります。これは4!/1!3!+4!/0!4!=4+1=5通り

ここで、BFDEGを2回カウントしているので、これを元に戻さないといけないので+1

結局、駄目な組み合わせは、

42+42-5+42-16-5+1+42-5-16+1=123

結局最終的にとりえる組み合わせは218-123=95通りです。

だめな組み合わせをどう取り除くかが、プログラムをくむ最大の鍵になりそうです。

あと、xCyの計算ですが、エクセルを使う場合だと、COMBIN(x,y)で計算できます。

id:reosucker

なるほど、勢い組み合わせのエクセルをアップしてお願いした方が良いかもですね。

再質問の際にはよろしくお願い致します。

2006/05/06 20:31:59
id:hkmd No.5

hkmd回答回数20ベストアンサー獲得回数02006/05/06 15:38:53

ポイント17pt

すみません。回答にはなってないのですが。

ちょっと考えてみましたが、これは解析的に解く(数式を求める)のは面倒ですね。D, E が重複してるのが厄介です。

n=3(ABCとかDTFとかEHCとか)の時は

・全ての組合せ = 2600

・AE, BF, DE, DG のうち少なくとも1つを含む = 96 - 2 = 94

で、

2600 - 94 = 2506 だと思います。

同様に n=4 の時は 14950 - 1055 = 13895 だと思います。

検算に使えるかもしれません……。

id:reosucker

なるほど。

実は理科大の友人にも同じような事をいわれてて

結構難儀してます。

改めて質問すると思うのでよろしくお願い致します。

2006/05/06 20:33:19
id:takomaro No.6

takomaro回答回数36ベストアンサー獲得回数02006/05/06 20:57:07

ポイント17pt

理解が違っていたら申し訳ないので確認したいのですが

仮に全体のデータ数3(ABC)で2個アイテムを選んだときの組み合わせ

AB

AC

BC

計3個

全体のデータ数4(ABCD)で3個アイテムを選んだときの組み合わせ

ABC

ABD

ACD

BCD

計4個

ルール

○重複するアルファベットは使用不可

○順番が入れ替わってるだけのものは不可

○データはA~Z(26個)、アイテムは任意に1から5個

という感じですよね。

「例題の表の"_"は分かるのですが"×"のルールが理解できませんでしたm(_ _)m」

スマートではないですがエクセルマクロで作ってみました。

セルB1に任意に選ぶアイテム数

セルB2に元のデータ数1~26(アルファベットでA~Z)

セルB3に組み合わせ数が出力

ちなみにA~Z(26個)で任意に5個選んだ場合の種類総数は

65780となりました。

選ぶアイテムの個数を増やすのはこのやり方だとループする階層を

増やしていかなければならないので可能ではありますが大変です。

マクロ↓

Option Explicit

Dim I, J, K, L, Y

Dim Item1, Data1, Ans1

'

Sub Macro1() 'Item n個の計算

Item1 = Cells(1, 2) 'セルB1

Data1 = Cells(2, 2) 'セルB2

Ans1 = 0

Y = 0

'データ総数よりアイテムが上回ったら終了

If Data1 < Item1 Or Item1 > 5 Then

Cells(5, 10) = Ans1

Exit Sub

End If

Select Case Item1 'アイテムの個数によって振り分け

Case 1 'アイテム1個

Ans1 = Data1

Case 2 'アイテム2個

For I = 1 To Data1 - Item1 + 1

Y = Y + 1

Ans1 = Ans1 + Y

Next

Case 3 'アイテム3個

For J = 0 To Data1 - Item1

For I = 0 To Data1 - Item1 - J

Y = Y + 1

Ans1 = Ans1 + Y

Next I

Y = 0

Next

Case 4 'アイテム4個

For L = 0 To Data1 - Item1

For K = 0 To Data1 - Item1 - L

For J = 0 To Data1 - Item1 - K

For I = 0 To Data1 - Item1 - (J + K + L)

Y = Y + 1

Ans1 = Ans1 + Y

Next I

Y = 0

Next J

Next K

Next L

Case 5 'アイテム5個

For L = 0 To Data1 - Item1

For K = 0 To Data1 - Item1 - L

For J = 0 To Data1 - Item1 - K

For I = 0 To Data1 - Item1 - (J + K + L)

Y = Y + 1

Ans1 = Ans1 + Y

Next I

Y = 0

Next J

Next K

Next L

End Select

Cells(3, 2) = Ans1 'セルB3

End Sub

id:reosucker

なぜか回答できない状態でした、、、

投稿ありがとうございます。

×の部分は特にルールは無く

AとCが×なら

C行のAも×

ってくらいです。

2006/05/11 19:26:59
id:i_kumagoro No.7

i_kumagoro回答回数170ベストアンサー獲得回数582006/05/08 22:03:55

ポイント17pt

一般化はかなり難しい(というか、できないのではと思います)ので、私なら総当たりでやります。

今時のパソコンなら30とか40くらいの中から選ぶ程度ならすぐにできますし、メモリの消費もしれています。何より確実です。

解法を考える時間も考慮すればそれが一番早いと思います。

http://d.hatena.ne.jp/i_kumagoro/20060508

にC言語ですがコードを置いていますのでご覧下さい。

id:reosucker

おお、ありがとうございます。

早速試してみます。

2006/05/11 17:13:20

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません