# Order sequence of n numbers (with repetition) having 4 consecutive increasing numbers!!

Context:

I recently came across a question like “what’s the probability that a random number (integer) generator will generate four successive numbers as consecutive increasing numbers?”. Many people have solved this assuming each sample point consists of only 4 random numbers and counting number of cases four of them are consecutive & increasing and finally concluding the probability as $\frac{(N-4+1)}{N^4}$ assuming the generators produces integers in the range $[1,N]$. However this problem has induced many interesting thoughts in my mind such as what if we try to find the probability for the same event (i.e. 4 consecutive numbers) but in $n (n\ge4)$ picks! Of course in this case 4 consecutive increasing number would be rephrased as at least one occurrence of 4 or more consecutive increasing numbers in successive picks. Yet another interesting observation I made here is that with $n$ changing the probability also changes. I spent ample time to solve this question but couldn't figure out how to count size of the event space. In this regard I’m rephrasing my question below with equivalent Urn & Ball model and any help solving this question would be much appreciated.

Question:

An urn has $N$ balls marked with a integer number from $1$ to $N$. Thus there would be exactly one ball in the urn with a given number from $[1,N]$. If we randomly pick $n$ balls with replacement then we know that there would be $N^n$ possible ways of picking $n$ balls. The question is how many of such ways we’ll have at least one occurrence of $4(=c)$ or more successive picks having consecutive increasing numbers? We can assume $n\ge4$.

Example: For N=9 (range of numbering 1-9) , n=7 (number of pick), c=3(number of picks with consecutive numbers)

Sequences that are included:

i) $1,2,3,1,2,3,1$ (2 occurrences of 3 consecutive numbers)
ii) $1,2,3,3,4,5,6$ (1 occurrence of 3 consecutive numbers and 1 occurrence of 4 consecutive numbers)
iii) $8,9,9,9,4,5,6$ (1 occurrence of 2 consecutive numbers and 1 occurrence of 3 consecutive numbers)

Sequences that are NOT included:

i) $1,2,4,5,7,8$ (3 occurrences of 2 consecutive numbers)

@Hurkyl: I'm afraid that I could not guess whether you're criticizing the post or providing a hint to solution. In fact I didn't get why did you mention "no 4-sequence can begin with a digit in [N-2,N]"! To me if N $\ge$ 4+2=6 then a 4-sequence can start with N-2. Am I missing something! – BuckCherry Dec 17 '12 at 11:45
@BuckCherry: What you seem to be missing is that once you have chosen one of $\{N-2,N-1,N\}$, there is no possible way to continue for at least three steps, each time choosing the number that is one more than the previously chosen number. Therfore once such a number is drawn (and it is not itself one more than the previous number) one goes to a "nothing useful found yet" state. What Hurkyl suggests is that the process of checking whether a desired subsequence exists can be done by an automaton with only very few states. For me it is not convincing. – Marc van Leeuwen Dec 17 '12 at 16:27