2
$\begingroup$

I tried to find the number of permutations of $\{1,\cdots,6\}$ which do not contain

the strings 123, 234, 345, or 456 using the following method,

and I would like to find out why this method does not give the right answer.

(In particular, which permutations does it count incorrectly?)


Take the total number of permutations and then subtract those with 3 consecutive integers, add back those with 4 consecutive integers, subtract the ones with 5 consecutive integers, and finally add the one permutation with all digits consecutive to get

$6!-4\cdot4!+3\cdot3!-2\cdot2!+1\cdot1!=720-96+18-4+1=\color{blue}{639}$.

$\endgroup$
  • 1
    $\begingroup$ I think you also need to apply GPIE within the sets of permutations with 5 consecutive integers (and other similar cases), otherwise you will "double count" some of these, e.g. there are three permutations with at least 5 consecutive digits: $612345, 234561,12356$. The last one can easily be overcounted. $\endgroup$ – Marconius Aug 12 '15 at 22:24
  • $\begingroup$ The number of permutations that include two patterns is not always $3!$. For instance, there are only $2!$ permutations that include both 123 and 345. $\endgroup$ – user940 Aug 12 '15 at 22:39
  • $\begingroup$ @ByronSchmuland I agree with your observation. (I used a different approach, though, which doesn't give the right answer.) $\endgroup$ – Monty Hall Aug 13 '15 at 0:15
  • $\begingroup$ @Marconius You're right - I am double-counting 123456 when I am counting the number of permutations with 5 consecutive integers, but I am subtracting it once in the next term. $\endgroup$ – Monty Hall Aug 13 '15 at 16:36
2
$\begingroup$

It appears very difficult to answer this question using GPIE. So, count the number of permutations for distinct cases instead, and use symmetry where possible.

Let $R_n$ be the set of all permutations having a maximal run of $n$ consecutive digits in order but not having another disjoint run of three or more (there is one permutation having two disjoint runs of three consecutive digits), and $R_{3,3}$ be the set of all permutations having two disjoint runs of three.

Let $N(\ldots,x,y,z,\ldots)$ be the number of permutations having $(x,y,z)$ in order starting at any digit in the permutation, and $N(\ast,x,y,z,\tilde{}m,\ldots)$ be the number of permutations having $(x,y,z)$ (starting in the second digit) followed by anything other than $m$, and an otherwise unrestricted first digit.

Then $$\begin{align} N(R_3) &= N(\ldots,1,2,3,\ldots) + N(\ldots,2,3,4,\ldots) + N(\ldots,3,4,5,\ldots) + N(\ldots,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,\ldots) + 2N(\ldots,2,3,4,\ldots)\qquad(\text{by symmetry}) \end{align}$$

and $$\begin{align} N(\ldots,1,2,3,\ldots) &= N(1,2,3,\tilde{}4,\ast,\ast) + N(\ast,1,2,3,\tilde{}4,\ast) + N(\ast,\ast,1,2,3,\tilde{}4) + (N(\ast,\ast,\ast,1,2,3) - N(4,5,6,1,2,3)) \\ &= 4 + 4 + 4 + (6-1) \\ &= 17 \end{align}$$

and $$\begin{align} N(\ldots,2,3,4,\ldots) &= N(2,3,4,\tilde{}5,\ast,\ast) + N(\tilde{}1,2,3,4,\tilde{}5,\ast) + N(\ast,\tilde{}1,2,3,4,\tilde{}5) + N(\ast,\ast,\tilde{}1,2,3,4) \\ &= 4 + 3 + 3 + 4 \\ &= 14 \end{align}$$

So $\boxed{N(R_3) = 2(17) + 2(14) = 62}$

Then $$\boxed{N(R_{3,3}) = N(4,5,6,1,2,3) = 1}$$

Also $$\begin{align} N(R_4) &= N(\ldots,1,2,3,4,\ldots) + N(\ldots,2,3,4,5,\ldots) + N(\ldots,3,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,4,\ldots) + N(\ldots,2,3,4,5,\ldots)\qquad(\text{by symmetry}) \end{align}$$

where $$\begin{align} N(\ldots,1,2,3,4,\ldots) &= N(1,2,3,4,\tilde{}5,\ast) + N(\ast,1,2,3,4,\tilde{}5) + N(\ast,\ast,1,2,3,4) \\ &= 1 + 1 + 2 \\ &= 4 \end{align}$$

and $$\begin{align} N(\ldots,2,3,4,5,\ldots) &= N(2,3,4,5,\tilde{}6,\ast) + N(\tilde{}1,2,3,4,5,\tilde{}6) + N(\ast,\tilde{}1,2,3,4,5) \\ &= 1 + 1 + 1 \\ &= 3 \end{align}$$

So $\boxed{N(R_4) = 2(4) + 3 = 11}$

Also $$\begin{align} N(R_5) &= N(\ldots,1,2,3,4,5,\ldots) + N(\ldots,2,3,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,4,5,\ldots)\qquad(\text{by symmetry}) \end{align}$$

where $$\begin{align} N(\ldots,1,2,3,4,5,\ldots) &= N(1,2,3,4,5,\tilde{}6) + N(\ast,1,2,3,4,5) \\ &= 0 + 1 \\ &= 1 \end{align}$$

So $\boxed{N(R_5) = 2(1) = 2}$

Finally $\boxed{N(R_6) = 1}$

So the number of permutations without three digits in order is given by: $$\begin{align} 6! - N(R_3) - N(R_{3,3}) - N(R_4) - N(R_5) - N(R_6) &= 720 - 62 - 1 - 11 - 2 - 1 \\ &= 643 \end{align}$$

$\endgroup$
  • $\begingroup$ There is a potentially simpler way. Every run of six gets counted as two different runs of five, so $N(R_5) = 2\cdot 2! - 2\cdot 1 = 2$. Every run of six gets counted as three different runs of four, and every maximal run of five gets counted as two different runs of four, so $N(R_4) = 3\cdot 3! - 3N(R_6) - 2N(R_5) = 18-3-2\cdot2 = 11$. Runs of three might be trickier. $\endgroup$ – Marconius Aug 13 '15 at 17:27
0
$\begingroup$

Let $A_i$ be the set of permutations containing the string $i, i+1, i+2$ for $1\le i\le 4$, and

let $S$ be the set of all permutations of $\{1,\cdots,6\}$.

Then $\displaystyle\big|A_1^c\cap\cdots\cap A_4^c\big|=\big|S\big|-\sum_{i}\big|A_i\big|+\sum_{i<j}\big|A_i\cap A_j\big|-\sum_{i<j<k}\big|A_i\cap A_j\cap A_k\big|+\big|A_1\cap\cdots\cap A_4\big|$

$\displaystyle\hspace{1.4 in}=6!-4\cdot4!+\big(3\cdot3!+3\cdot2!\big)-\big(2\cdot2!+2\cdot1\big)+1=643.$


Your method counts each of the following permutations twice, instead of just once,

when the number of permutations in the complement is being counted:

$\hspace{.5 in}123456, \;\;612345,\;\;234561,\;\;456123$

$\endgroup$

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.