# Probability of achieving every possible permutation in a set for x number of random re-arrangements?

I'm trying to figure out the probability of achieving every possible permutation in a set for x number of random re-arrangements.

For example, for a set of 3 objects that get randomly re-arranged in their order each turn and there are x turns how can I figure out the probability that every permutation will come up?

Please note that the set member order matters - hence why I'm thinking about permutations.

• this is just a version of the Coupon Collector's Problem. You are looking for $n!$ coupons and making uniform draws with replacement from the list.
– lulu
Commented Sep 8, 2016 at 17:25
• Thanks for the reference @lulu. Unfortunately, that page is quite intimidating. What's the probability of seeing all permutations of 3 objects over 20 random re-arrangements? Commented Sep 8, 2016 at 17:40
• Maybe this article is better reading. The expected number of draws to see $6$ coupons is $14.7$, so $20$ should have a high probability. People usually refer to expected value in this context, because getting the exact probabilities for a specific number of draws is very messy (generally done with a computer).
– lulu
Commented Sep 8, 2016 at 17:54

Most direct approach is by Inclusion-Exclusion. That is, we start with $1$, then subtract the probability of missing at any given permutation, then add back the probability of missing any given pair, subtract the probability of missing any given triple, and so on. That is to say that your answer, $P$, is given by $$P=1-\sum_{i=1}^5(-1)^{i+1}\binom 6i \left(\frac {6-i}6\right)^{20}\sim 0.847987541$$
As a quick sanity check: the probability of missing a given permutation is, of course $\left( \frac 56\right)^{20}$. If you neglect the chance of missing two or more permutations then your answer would be $$1- 6\times \left( \frac 56\right)^{20}\sim 0.84349568$$ which is pretty much our value.