# Throwing $6$-sided dice $N$ times [duplicate]

A $6$-sided die is thrown N times and the results are observed to form a monotonic sequence. What is the probability that every possible number occurs at least once in the sequence?

-
Rather low if $N \lt 6$ – Ross Millikan Sep 20 '12 at 15:45
Indeed, N>=6 otherwise prob is of course zero. – fpghost Sep 20 '12 at 17:04
Have you searched for answers to this question already given on this forum ? Evidently not ! Seek, and you shall find ! – true blue anil Sep 20 '12 at 17:05
Sorry, I did just see the other thread, I am still puzzled at how to get to the generic answer for number of mono seqs given there though if anyone could help.. – fpghost Sep 20 '12 at 17:29

## marked as duplicate by Hagen von Eitzen, M Turgeon, Peter Tamaroff, Steven Stadnicki, J. M.Sep 21 '12 at 8:49

Hint: Calculate how many monotonic sequences there are that "use" only $k$ numbers.
How many surjective and non-decreasing sequences of length $n$ of elements in $\{1, \ldots, k\}$ are there? If $(a_1, \ldots, a_n)$ is such a sequence, then $a_1=1$, $a_n=k$ and there must be exactly $k-1$ different $i$, $1\le i\le n-1$ with $a_{i+1}=a_i+1$. Thus the number of such sequences is $n-1\choose k-1$.
How many non-decreasing sequences of length $n$ of elements in $\{1, \ldots, 6\}$ with exactly $k$ different numbers are there? We can choose $k$ out of 6 numbers and then have $n-1\choose k-1$ sequences as in the previous paragraph. Hence the number of such sequences is ${6\choose k}\cdot {n-1\choose k-1}$.
The conditional probability of throwing a sequence containing all 6 numbers, given that the sequence is nondecresing is therefore $$p=\frac{n-1\choose 5}{{6\choose 1}{n-1\choose 0}+{6\choose 2}{n-1\choose 1}+{6\choose 3}{n-1\choose 2}+{6\choose 4}{n-1\choose 3}+{6\choose 5}{n-1\choose 4}+{6\choose 6}{n-1\choose 5}} \\ =\frac{\frac{1}{120} n^5 - \frac{1}{8} n^4 + \frac{17}{24} n^3 - \frac{15}{8} n^2 + \frac{137}{60} n - 1 }{ \frac{1}{120} n^5 + \frac{1}{8} n^4 + \frac{17}{24} n^3 + \frac{15}{8} n^2 + \frac{137}{60} n + 1 }\\ =1-30\cdot\frac{n^4 + 15 n^2 + 8 }{n^5 + 15 n^4 + 85 n^3 + 225 n^2 + 274 n + 120 } ,$$ which converges $\to1$ as $n\to\infty$.