2
$\begingroup$

A sequence of numbers is formed from the numbers $1, 2, 3, 4, 5, 6, 7$ where all $7!$ permutations are equally likely. What is the probability that anywhere in the sequence there will be, at least, five consecutive positions in which the numbers are in increasing order?

I approached this problem in the following way, but I am wondering if there is a better way, since my approach is quite complicated.

My Approach: There are three possibilities: a sequence have $7$ consecutive positions in which numbers increase, have $6$ consecutive positions in which numbers increase, and $5$ consecutive positions in which numbers increase.

There is only $1$ sequence that have $7$ consecutive positions. Namely, the sequence $(1,2,3,4,5,6,7)$.

There are $12$ sequences that have $6$ consecutive positions. Namely, we choose $1$ number from $(1,2,3,4,5,6,7)$, and move it to either sides. As an illustration, if we choose $3$, then we can get $(3,1,2,4,5,6,7)$ or $(1,2,4,5,6,7,3)$.

Now consider when there are $5$ consecutive positions in which numbers increase. We choose $2$ numbers that are not in the increasing subsequence.

If $1$ and $7$ are not chosen, we can place them in front of the subsequence, of after. For example, if we choose $(2,5)$, then we will have $(2,5,1,3,4,6,7)$,$(5,2,1,3,4,6,7)$, $(1,3,4,6,7,2,5)$ and $(1,3,4,6,7,5,2)$. This is $\binom{5}{2}\times4$.

Then I'm not sure how to proceed when we choose $1$ and/or $7$?

$\endgroup$
  • 1
    $\begingroup$ There are $\binom{7}{5}2!$ permutations with positions 1 to 5 ordered, same for positions 2 to 6 and 3 to 7. There are $\binom{7}{6}1!$ permutations with positions 1 to 5 and 2 to 6 ordered, same for positions 2 to 6 and 3 to 7, there are $\binom{7}{7}0!$ permutations with positions 1 to 5 and 3 to 7 ordered. There are $\binom{7}{7}0!$ permutations with positions 1 to 5 and 2 to 6 and 3 to 7 ordered. So by inclusion-exclusion: $\text{count}=3\binom{7}{5}2!-\left(2\binom{7}{6}1!+\binom{7}{7}0!\right)+\binom{7}{7}0!=112$. $\endgroup$ – N. Shales Oct 26 '17 at 2:09
  • $\begingroup$ @N.Shales I wrote a solution, only to realize I was basically reproducing your work. I suggest you post your comment as a solution. $\endgroup$ – N. F. Taussig Oct 26 '17 at 12:07
  • $\begingroup$ @N.F.Taussig, I don't mind at all if you want to post your solution however similar it is to mine. I will post in a little while if I don't see your answer (I'm a bit busy at the moment) but do feel free to post :) $\endgroup$ – N. Shales Oct 26 '17 at 13:40
1
$\begingroup$

This solution does not differ in any essential way from that of N. Shales. I am posting this here so N. Shales can compare our approaches.

Since the sequence contains seven numbers, any block of five consecutive increasing numbers must start in the first, second, or third positions. Let $A_1$, $A_2$, and $A_3$ denote, respectively, the set of sequences containing five consecutive increasing numbers that begin in the first, second, and third positions.

By the Inclusion-Exclusion Principle, the number of sequences containing a block of at least five consecutive increasing numbers is $$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$$

$|A_1|$: There are $\binom{7}{5}$ ways to select five of the seven numbers to be in a block of five consecutive increasing numbers and one way to arrange the numbers within that block so that they are increasing. There are $2!$ ways to arrange the remaining two numbers in the remaining two positions. Hence, $$|A_1| = \binom{7}{5}2!$$

By symmetry, $|A_1| = |A_2| = |A_3|$.

$|A_1 \cap A_2|$: If both the first five and second five numbers are increasing, then the first six numbers must form an increasing sequence. There are $\binom{7}{6}$ ways to select six of the seven numbers to be in the block of six consecutive increasing numbers and one way to arrange the numbers within the block so that they are increasing. There is one way to place the remaining number in the remaining position. Hence, $$|A_1 \cap A_2| = \binom{7}{6}1!$$

By symmetry, $|A_1 \cap A_2| = |A_2 \cap A_3|$.

$|A_1 \cap A_3|$: If the first five and last five of the seven numbers are increasing, then all seven numbers must be increasing. There is only one way to arrange all seven numbers in an increasing sequence. Hence, $$|A_1 \cap A_3| = \binom{7}{7}$$

$|A_1 \cap A_2 \cap A_3|$: There is only one way for all seven numbers to be arranged in increasing order. Hence, $$|A_1 \cap A_2 \cap A_3| = \binom{7}{7}$$

Therefore, $$|A_1 \cup A_2 \cup A_3| = 3\binom{7}{5}2! - 2\binom{7}{6}1! - \binom{7}{7} + \binom{7}{7} = 3\binom{7}{5}2! - 2\binom{7}{6}$$

Hence, the probability that a sequence of seven numbers contains a block of at least five consecutive increasing numbers is $$\frac{3\dbinom{7}{5}2! - 2\dbinom{7}{6}1!}{7!}$$

$\endgroup$
  • $\begingroup$ Ah, I see. Thank you very much for that. Nice explanation (+1). $\endgroup$ – N. Shales Oct 26 '17 at 20:22
1
$\begingroup$

Both myself and @N.F.Taussig used the following approach, although I'd like to see if it could be generalised to increasing runs of arbitrary length.

Define set $S_{i,j}$ as the set of permutations of $[7]$ with an increasing run between position $i$ and $j$ inclusive. Then by inclusion-exclusion the desired success count is

$$\begin{align}&(|S_{1,5}|+|S_{2,6}|+|S_{3,7}|) -\\ (|S_{1,5}\cap S_{2,6}| + |S_{1,5}&\cap S_{3,7}|+|S_{2,6}\cap S_{3,7}|)+ |S_{1,5}\cap S_{2,6}\cap S_{3,7}|\tag{1}\end{align}$$

Clearly

$$|S_{1,5}|=|S_{2,6}|=|S_{3,7}|=\binom{7}{5}2!\tag{2}$$

since we choose $5$ of the $7$ numbers to go in increasing order in positions $1$ to $5$, $2$ to $6$ or $3$ to $7$ and the remaining $2$ numbers can go in the remaining $2$ spots in $2!$ ways.

Also

$$S_{1,5}\cap S_{2,6}=S_{1,6}$$ $$\implies |S_{1,5}\cap S_{2,6}|=|S_{1,6}|=\binom{7}{6}1!\tag{3}$$

and

$$S_{1,5}\cap S_{3,7}=S_{1,7}$$ $$\implies |S_{1,5}\cap S_{3,7}|=|S_{1,7}|=\binom{7}{7}0!\tag{4}$$

and

$$S_{2,6}\cap S_{3,7}=S_{2,7}$$ $$\implies |S_{2,6}\cap S_{3,7}|=|S_{2,7}|=\binom{7}{6}1!\tag{5}$$

and

$$S_{1,5}\cap S_{2,6}\cap S_{3,7}=S_{1,7}$$ $$\implies |S_{1,5}\cap S_{2,6}\cap S_{3,7}|=|S_{1,7}|=\binom{7}{7}0!\tag{6}$$

using similar reasoning to $(2)$ in each case.

Putting the results of $(2)$, $(3)$, $(4)$, $(5)$ and $(6)$ into $(1)$ gives:

$$\text{success count}=3\binom{7}{5}2!-\left(2\binom{7}{6}1!+\binom{7}{7}0!\right)+\binom{7}{7}0!=112$$

Then since there are $7!$ permutations the desired probability is:

$$\text{probability of an increasing run of length $\ge 5$}=\frac{112}{7!}=\frac{1}{45}\tag{Answer}$$

$\endgroup$
  • 1
    $\begingroup$ The solution I wrote was the same except that I defined $A_1$ , $A_2$, and $A_3$ as sets of five consecutive increasing numbers that begin in the first, second, and third positions, respectively. I found that the key point here is to include and exclude sequences that contain one or more blocks of five consecutive increasing numbers rather than sequences of five or more increasing numbers since $|A_1 \cap A_3| = \binom{7}{7}$ while $|A_1 \cap A_2| = |A_2 \cap A_3| = \binom{7}{6}$. $\endgroup$ – N. F. Taussig Oct 26 '17 at 16:26
  • $\begingroup$ It gave you the same answer then? What happened to the $2!$,$1!$ and $0!$ factors? Is there some way they are incorporated? Perhaps you could post it: I'd like to see more clearly how it differs from mine. $\endgroup$ – N. Shales Oct 26 '17 at 16:49
  • $\begingroup$ I obtained the same answer. I did not include the factors of $1!$ or $0!$ in the comment since $1! = 0! = 1$. I am at work, but I will be able to post my solution in a few hours once I return home. $\endgroup$ – N. F. Taussig Oct 26 '17 at 17:11
  • $\begingroup$ Okay, no rush. Thanks for taking the time to reply :) $\endgroup$ – N. Shales Oct 26 '17 at 17:14
  • $\begingroup$ I have posted my version of your solution. $\endgroup$ – N. F. Taussig Oct 26 '17 at 19:44
0
$\begingroup$

${}_7 C_2 = 21$, are the number of ways of choosing two out of the seven numbers. We pull them out. The remaining five retain their increasing order. So now find the number of ways you can replace those two values at either the beginning and/or end of the sequence, and multiply this result by 21. If they happen to be replaced where they started then the length of the increasing sub-sequence grows, but this is allowed anyway. Two elements can be replaced in the sequence in 6 ordered ways, by my count. That is $2!=2$ orders times 3 ways of splitting them up. In total then I figure there are 126 ways of creating sequences with 5 or more increasing elements anywhere in the sequence. Divide by your $7!=5040$ permutations for a probability.

$\endgroup$
  • 1
    $\begingroup$ You are counting sequences with six consecutive increasing numbers twice and seven consecutive increasing numbers thrice. $\endgroup$ – N. F. Taussig Oct 26 '17 at 2:14
  • $\begingroup$ How am I over-counting? I dont see it. $\endgroup$ – CogitoErgoCogitoSum Oct 26 '17 at 7:28
  • $\begingroup$ You are counting sequences with six consecutive increasing numbers twice, once each when you count the leftmost and rightmost five numbers of the block of six consecutive increasing as the five consecutive increasing numbers. For the block of seven consecutive increasing numbers, you count it three times, once each when you count the leftmost, middle, and rightmost five numbers of the sequence as the five consecutive increasing numbers. You can fix your count by using the Inclusion-Exclusion Principle. $\endgroup$ – N. F. Taussig Oct 26 '17 at 8:59
  • $\begingroup$ Please read the solution by N. Shales. $\endgroup$ – N. F. Taussig Oct 26 '17 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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