# Throw a die $N$ times, observe results are a monotonic sequence. What is probability that all 6 numbers occur in the sequence?

I throw a die $N$ times and the results are observed to be a monotonic sequence. What is probability that all 6 numbers occur in the sequence?

I'm having trouble with this. There are two cases: when the first number is 1, and when the first number is 6. By symmetry, we can just consider one of them and double the answer at the end. I've looked at individual cases of $N$, and have that

For $N = 6$, the probability is $\left(\frac{1}{6}\right)^2 \frac{1}{5!}$.

For $N = 7$, the probability is $\left(\frac{1}{6}\right)^2 \frac{1}{5!}\left(\frac{1}{6} + \frac{1}{5} + \frac{1}{4} + \frac{1}{3} + \frac{1}{2} + 1\right)$.

I'm not sure if the above are correct. When it comes to $N = 8$, there are many more cases to consider. I'm worried I may be approaching this the wrong way.

I've also thought about calculating the probability that a number doesn't occur in the sequence, but that doesn't look to be any easier.

Any hints/corrections would be greatly appreciated. Thanks

-
Do you mean that in the sequence of $N$ outcomes, you look for a longest monotonic subsequence ? Should the sequence be increasing or decreasing ? – Sasha Aug 24 '11 at 12:43
Apologies, see my edit. I need to find the probability that all 6 numbers occur, given that the N results form a monotonic sequence. – TRY Aug 24 '11 at 12:45

As you observe, you can reduce the problem to monotonically increasing.

Consider how many cases give a monotonically increasing sequence from 1 to 6. That requires that you throw a 1 on the first throw; that on five of the later throws you increase by 1; and that on the other later throws you remain that same. So there are $\binom{N-1}{5}$ choices for the throws which change.

Now, how many possible monotonically increasing sequences are there? One way to look at this combinatorically is to take the $N$ elements of the sequence, prepend $1$, and postpend $6$. There are $N+1$ places in this sequence where the value can increase, and $5$ of them are used (with repetition). That gives $\binom{N+5}{5}$

Now to convert the reduction into the final answer we want the number of monotonically increasing or decreasing sequences with all values over the number of monotonically increasing or decreasing sequences. A sequence cannot be monotonically increasing through all values and monotonically decreasing through all values, but it can be both monotonically increasing and monotonically decreasing if it is constant, so we must apply inclusion-exclusion for the denominator. Therefore we have

$$\begin{eqnarray} P(\text{All 6 included}|\text{Monotonic}) & = & \frac{ 2\binom{N-1}{5} }{ 2\binom{N+5}{5} - 6 } \\ & = & \frac{(N-1)!\;N!}{(N-6)!\;((N+5)! - 360\;N!)} \\ & = & \frac{(N-5)(N-4)(N-3)(N-2)(N-1)}{(N+5)(N+4)(N+3)(N+2)(N+1) - 360} \end{eqnarray}$$

-
@Byron, excellent point. Thanks. – Peter Taylor Aug 24 '11 at 14:21
As Tom states in his solution below, there is a subtle problem with reducing the question to monotonically increasing only: monotonic includes constant. – David Bevan Jan 3 '12 at 18:21

I have a slightly different answer to the above, comments are very welcome :)

The number of monotonic sequences we can observe when we throw a dice $N$ times is 2$N+5\choose5$-$6\choose1$ since the six sequences which consist of the same number repeatedly are counted as both increasing and decreasing (i.e. we have counted them twice so need to subtract 6 to take account of this).

The number of increasing sequences involving all six numbers is $N-1\choose5$ (as has already been explained). Similarly the number of decreasing sequences involving all six numbers is also $N-1\choose5$.

Therefore I believe that the probability of all seeing all six numbers given a monotonic sequence is
2$N+5\choose5$-$6\choose1$ divided by 2$N-1\choose5$.

This is only slightly different to the above answers but if anyone has any comments as to whether you agree or disagree with my logic or if you require further explanation I'd be interested to hear from you.

-
I think you mean, divide $2\binom{N-1}{5}$ by $2\binom{N+5}{5}-6$. Well done for pointing out the subtle error in considering increasing and decreasing sequences individually. – David Bevan Jan 3 '12 at 18:19

Consider monotonically increasing outcomes. Let there be $k_1$ of ones, $k_2$ of twos, and so on. Clearly $k_1+k_2+k_3+k_4+k_5+k_6 = N$ and $k_i>0$. The probability is then, the number of aforementioned configuration $C$ divided by $6^N$.

To count how many $\{k_i\}$ are there, it is best to use generating functions.

$$C = [t]_n \left( \frac{t}{1-t} \right)^6 = [t]_{n-6} \left( \frac{1}{1-t} \right)^6 = \binom{n-1}{5}$$

Added: In order to compute the conditional probability, we should count how many monotonically increasing sequences of outcomes are there. To this end we need to drop $k_i>0$ requirement, while keeping $\sum_{i=1}^6 k_i = n$. Let this count be $T$, then

$$T = [t]_n \left( \frac{1}{1-t} \right)^6 = \binom{n+5}{5}$$

The final result, thus is

$$p = \frac{\binom{n-1}{5}}{\binom{n+5}{5} } = \frac{(n)^{(6)}}{(n)_6}$$ where $(n)_m$ is Pochhammer symbol, and $(n)^{(m)}$ is falling factorial.

-
As Tom states in his solution below, there is a subtle problem with reducing the question to monotonically increasing only: monotonic includes constant. – David Bevan Jan 3 '12 at 18:22