Probability of getting {1,2,..,k} each at least once from a k-sided dice out of n rolls?

Question

Example, for k=6, and n=20 what is the probability of having every side of {1,2,3,4,5,6} show up at least once out of 20 rolls.
At first thought it would be (1-(5/6)^20)^6 but that is wrong since for 5 rolls (1-(5/6)^5)^6=.045 but it should be zero percent chance as it's impossible for all 6 sides to show up in only 5 rolls.

k=2, n=5 would be the probability of both {heads} and {tails} showing up at least once out of 5 flips of the coin.

etc.

Looking for the general case.

Answer 1

This is not an easy problem to formulate.
Consider a 6 sided die being tossed n times.
P(no 5s) = (5/6)^n
P(no 6s) = (5/6)^n
BUT those two values have events in common
P(no 5s and no 6s) = (4/6)^n

So P(no 5s or no 6s) = (5/6)^n + (5/6)^n - (4/6)^n

Now you have to extend this formula to find:
P(no1s or no 2s or no 3s .... or no k's)

Let me give you a start:
P(no 4s OR no 5s OR no 6s) =
P(no 4s) + P(no 5s) + P(no 6s)
- P(no 4s AND no 5s) - P(no 4s AND no 6s)
- P(no 5s AND no 6s) + P(no 4s AND no 5s AND no 6s)

= 3*(5/6)^n - 3*(4/6)^n + (3/6)^n
Good luck with the rest.

With the coins it's easy.
P(no H's) = 1/32
P(no T's) = 1/32
P(no T's or no H's) = 1/16
P(at least one of each) = 15/16

*EDIT*
I was able to find a general formula:
For a k sided dice tossed n times
P(every number appears at least once) =

k
∑ (-1)^i * (kCi) * [(k-i)/k]^n
i=0

I've tested it for a few scenarios and it works.

Answer 2

It looks like your on the correct track here, and the easiest way to do this is would be to specify exactly when this is the case. i.e. the general case would be

1 - [(1-1/k)^(n-1)](1/k) - for n >= k

0 otherwise.

This does make sense as essentially you are looking for a smooth curve that angles at a discrete point (no such function exists)

Answer 3

well in 6 rolls the probability is one sixth. So 18 rolls would give you 3 sixths which is 0.5. For more than that just go with 19 rolls.

Answer 4

wanted=P(all k sides show at least once in n rolls)

for k=2
P=1 - 2(1/2)^n
=1 - 1/2^(n-1)

for k=3
P=1 - 3*[2^n -1]/3^n
=1 - [2^n -1]/3^(n-1)

that's all i know, and i'm not so sure about k=3.
but k=2 is surely that.