n種のガチャをm回でそろえる確率

質問

5種のガチャをn回でそろえる確率 - 数学・算数 | 【OKWAVE】
https://okwave.jp/qa/q9490043.html

の続きです。上記の質問では「全パターンをチェックすればいい」という回答をいただきました。私が「5種」と少ない数を指定していたので、その場合にはおおむね問題ないと言えます。

しかしこれを汎用的に考えた場合、単純にn^m回評価することになります。するとn, mが増えていくと
3種4回で81回、
5種6回で15625回、
7種8回で5764801回、
10種12回で1000000000000回、
10種15回で1000000000000000回、
と計算量が激増していきます。
これでは数が増えていったときに計算に時間がかかりすぎ使い物になりません。

もう少しスマートに計算する方法はないのでしょうか。
n, mが増えても計算量が変わらない算出方法が知りたいです。
あるいは、計算量の増加が緩やかな方法でも構いません。

この点について教えて下さい。よろしくお願いします。

回答No.4

f272

#3です。
プログラムでn=10にしているから，表示されている確率はすべて10種類ある時です。そして
0.9は2回でちょうど2種そろう確率
0.27は3回でちょうど2種そろう確率
です。

> 回数が増えるほど確率が上がらないとおかしいですよね。

3回やればちょうど2種そろうよりも，3種そろうほうが確率は高くなります。
もしちょうど2種とかちょうど3種ではなくて，2種以上そろう確率と言ったものを知りたければそれよりも横の数値の合計で考えてください。

お礼

なるほど。ようやく意味が分かりました。
結果が最下段で、それ以外は途中経過の数字ということなのですね。

少し変わった方法のように感じますがちゃんと計算できていそうですね。
ありがとうございました

回答No.3

f272

VBAで作ってみました。
n種のガチャをm回でそろえる確率を求めます。
縦の行は回数で，0回からm回まで
横の列は種類で，0種類からn種類まで
を表し，n種のガチャがあるときにi回でj種のガチャが揃う確率がi行j列に表示されます。n種のガチャをm回でそろえる確率はいちばん右下のm行n列に表示されます。

Sub aaa()
n = 10
m = 12
ReDim Prob(m, n)
Prob(0, 0) = 1
For j = 1 To n
Prob(0, j) = 0
Next j
For i = 1 To m
Prob(i, 0) = 0
For j = 1 To n
Prob(i, j) = Prob(i - 1, j - 1) * (1 - (j - 1) / n) + Prob(i - 1, j) * j / n
Next j
Next i
Range("B2").Resize(m + 1, n + 1) = Prob
End Sub

お礼

ありがとうございました

補足

数字の見方がよくわかりませんが…違っていませんか？

2種を2回でそろえるのが0.9で
2種を3回でそろえるのが0.27？

回数が増えるほど確率が上がらないとおかしいですよね。

回答No.2

HohoPapa

No1への追記です。

ごめんなさい。
総当たりのプログラムで検算してみたら全然違っていました。

5種6回：1800/5^6
5種7回：16800/5^7
5種8回：126000/5^8　でした。

どうやら、
5回を超える場合は、何番目（と何番目）で重複したかを考慮し
それごとに確率を求め、それらを積み上げる必要があるようです。

■例えば、

5種7回で、2回目、3回目に重複した場合は、
=5/5*1/5*1/5*4/5*3/5*2/5*1/5
=5*1*1*4*3*2*1/5^7

2回目と3回目は、1回目と同じガチャをゲットする必要があるので
1/5をそれぞれ掛け算しています。

■例えば、

5種7回で、4回目、6回目に重複した場合は、
=5/5*4/5*3/5*3/5*2/5*4/5*1/5
=5*4*3*3*2*4*1/5^7

4回目は、1,2,3回目でゲットしたガチャをゲットする必要があるので、
3/5を
6回目は、1,2,3,5回目にゲットした4種の何れかをゲットする必要があるので、
4/5を掛け算しています。

■5種7回の場合の計算を以下に書きます。
分母はすべて5^7ですので、分子のみを羅列します。

5*4*3*2*1*5*5=3000　6回目、7回目が重複
5*4*3*2*4*1*5=2400　5回目、7回目が重複
5*4*3*2*4*4*1=1920　5回目、6回目が重複
5*4*3*3*2*1*5=1800　以下省略
5*4*3*3*2*4*1=1440
5*4*3*3*3*2*1=1080
5*4*2*3*2*1*5=1200
5*4*2*3*2*4*1=960
5*4*2*3*3*2*1=720
5*4*2*2*3*2*1=480
5*1*4*3*2*1*5=600
5*1*4*3*2*4*1=480
5*1*4*3*3*2*1=360
5*1*4*2*3*2*1=240
5*1*1*4*3*2*1=120
計：16800

これを整形して並べ替えると
5! * 5 * 5 = 3000
5! * 5 * 4 = 2400
5! * 5 * 3 = 1800
5! * 5 * 2 = 1200
5! * 5 * 1 = 600
5! * 4 * 4 = 1920
5! * 4 * 3 = 1440
5! * 4 * 2 = 960
5! * 4 * 1 = 480
5! * 3 * 3 = 1080
5! * 3 * 2 = 720
5! * 3 * 1 = 360
5! * 2 * 2 = 480
5! * 2 * 1 = 240
5! * 1 * 1 = 120
計：16800

続いて
5種8回の場合の計算を以下に書きます。
分母はすべて5^8ですので、分子のみを羅列します。

5! * 5 * 5 * 5 = 15000
5! * 5 * 5 * 4 = 12000
5! * 5 * 5 * 3 = 9000
5! * 5 * 5 * 2 = 6000
5! * 5 * 5 * 1 = 3000
5! * 5 * 4 * 4 = 9600
5! * 5 * 4 * 3 = 7200
5! * 5 * 4 * 2 = 4800
5! * 5 * 4 * 1 = 2400
5! * 5 * 3 * 3 = 5400
5! * 5 * 3 * 2 = 3600
5! * 5 * 3 * 1 = 1800
5! * 5 * 2 * 2 = 2400
5! * 5 * 2 * 1 = 1200
5! * 5 * 1 * 1 = 600
5! * 4 * 4 * 4 = 7680
5! * 4 * 4 * 3 = 5760
5! * 4 * 4 * 2 = 3840
5! * 4 * 4 * 1 = 1920
5! * 4 * 3 * 3 = 4320
5! * 4 * 3 * 2 = 2880
5! * 4 * 3 * 1 = 1440
5! * 4 * 2 * 2 = 1920
5! * 4 * 2 * 1 = 960
5! * 4 * 1 * 1 = 480
5! * 3 * 3 * 3 = 3240
5! * 3 * 3 * 2 = 2160
5! * 3 * 3 * 1 = 1080
5! * 3 * 2 * 2 = 1440
5! * 3 * 2 * 1 = 720
5! * 3 * 1 * 1 = 360
5! * 2 * 2 * 2 = 960
5! * 2 * 2 * 1 = 480
5! * 2 * 1 * 1 = 240
5! * 1 * 1 * 1 = 120
計：126000

この計算式を汎用の形で
カッチョよく書き換えるのは断念しました。

お礼

ありがとうございました

回答No.1

HohoPapa

全5種類のガチャを6回まわすケースを考えます。

1回目から4回まわして4個のアイテムが重複しない確率は
=(5/5)　*　(4/5)　*　(3/5)　*　(2/5)
=(5*4*3*2)　/　(5*5*5*5)

その後2回まわし、
重複しない残り1個のアイテムをゲットできる確率は
=(1/5)　+　(1/5)
=(2/5)

双方を掛け算すると
=(5*4*3*2*2)　/　(5*5*5*5*5)

この延長上で考えてみました。

n種のガチャをm回まわした時に全種をゲットできる確率．．．

1回目から(n-1)回まわして(n-1)個のアイテムが重複しない確率は
=((n/n))　*　((n-1)/n)　*　((n-2)/n)　*　((n-3)/n)　*・・・　(2/n)
=(　(n!)　/　(n^(n-1))　)

その後(m-n+1)回まわし、
重複しない残り1個のアイテムをゲットできる確率は
=(　(m-n+1)　/　n　)

双方を掛け算すると
=(　(n!)　/　(n^(n-1))　)　*　(　(m-n+1)　/　n　)

お礼

ありがとうございました

補足

>その後2回まわし、重複しない残り1個のアイテムをゲットできる確率は
>=(1/5)　+　(1/5)

それだと、
その後5回まわしたら確率が100％になり、
その後6回まわしたら確率が100％を超えることになります。
…いくら何でもそれはないでしょう。