Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
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
add comment

1 Answer

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$.

share|improve this answer
    
If N=1,monoseqs is 6, N=2:21, N=3:56, N=4:126..? The way I get this is write out a table like: N=1: LHC| RHC {1,6},{1,5}{1,4}{1,3}{1,2}{1,1} N=2: LHC| RHC {1,6} {2,5},{3,4}{4,3},{5,2},{6,1} N=3: LHC| RHC {1,6},{3,5},{6,4},{10,3},{15,2},{21,1} then multiply the LHC by RHC and add up. The RHC always runs 6 down 1(if seq ends 1 seeds 6 more if inc N by 1) since and the LHC entry can be obtained from the previous N-1 table by adding up the corresponding entry in the LHC and those in the cells directly above , e.g. for N=3 my third row 6 in the LHC is obtained from the N=2 table by adding 3+2+1. –  fpghost Sep 20 '12 at 16:58
    
Since some sequences are common to both increasing and decreasing monotonic sequences, shouldn't both be considered ? –  true blue anil Sep 21 '12 at 5:17
    
Also, for the final expression, I'm getting the polynomial in the denominator to be identical to that in the numerator except that all the coefficients are positive. –  true blue anil Sep 21 '12 at 8:39
    
I've finally understood the answer in the other thread and that answer converges to 1 as n->infty, so not sure why this result does not? –  fpghost Sep 21 '12 at 9:36
    
@fpghost: There seems to have been a mistake in the polynomial expansion or me copying the coefficients. After running the binomials through gp again, th eresut is like in th eother (more elegant) thread. –  Hagen von Eitzen Sep 24 '12 at 20:08
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.