# How many permutations of $0123456789$ are possible if $0123$, $2345$, $4567$, $6789$ sequences are not allowed?

How many permutations of $P=0123456789$ are possible if $0123$, $2345$, $4567$, $6789$ are not allowed as consecutive subsequences?

For example, $0167895432$ is an illegal permutation of $P$ because it contains the subsequence of $6789$. I think inclusion/exclusion can be applied here. We can count the complement of the problem: permutations of $P$ when there's one, two, three or four occurrences of illegal sequences.

1. The number of cases when there's one illegal subsequence is: $${4\choose 1}{10\choose 4}6!$$ because there're four ways to choose an illegal sequence and we need to allocate four consecutive positions in $P$ to place the sequence and we permute the rest of the digits.

2. The case when there're two illegal sequences is the trickiest: $${4\choose 2}{10\choose 4}{6\choose 4}2!+{4\choose 2}{10\choose 6}4!$$ because there's one case when the two sequences are not adjacent to each other and there's a case when the two sequences overlap.

3. The only way three sequences can be fit into $P$ is if they all overlap: $${4\choose 3}{10\choose 8}2!$$

Finally there's only one way that all four illegal sequences are present in $P$: if the permutation is $0123456789$. So the solution is: $$10!-{4\choose 1}{10\choose 4}6!+{4\choose 2}{10\choose 4}{6\choose 4}2!+{4\choose 2}{10\choose 6}4!-{4\choose 3}{10\choose 8}2!+1$$

Did I miss anything?

• This is a classic inclusion-exclusion question. – Thomas Andrews Jun 12 '18 at 16:27

Note that there are $7!$ ways to have a permutation that includes $0123.$

Write a permutation of $(X,4,5,6,7,8,9),$ and then replace $X$ with $0123.$

Also the number of permutations with $0123$ and $2345$ is different from the number of permutations with $0123$ and $4567.$ In the first case, this is just a permutation containing $012345$, so there are $5!$ such permutation. In the second case, we can take a permutation of $XY89$ and replace $X$ with $0123$ and $Y$ by $4567,$ getting a total of $4!$ such permutations.

Let $\Sigma$ be the set of all permutations, and let $A_{1},A_{2},A_{3},A_4$ be the set of permutations that include $0123,$ $2345$, $4567,$ and $6789,$ respectively.

Then you need to consider the sizes of each of the sets:

\begin{align}|\Sigma|&=10!\\ |A_1|=|A_2|=|A_3|=|A_4|&=7!\\ |A_1\cap A_3|=|A_1\cap A_4|=|A_2\cap A_4|&=4!\\ |A_1\cap A_2|=|A_2\cap A_3|=|A_3\cap A_4|&=5!\\ |A_1\cap A_2\cap A_3|=|A_2\cap A_3\cap A_4|&=3!\\ |A_1\cap A_3\cap A_4|=|A_1\cap A_2\cap A_4|&=2!\\ |A_1\cap A_2\cap A_3\cap A_4|&=1 \end{align}

$$\left|\Sigma-\left(A_1\cup A_2\cup A_3\cup A_4\right)\right|=10!-4\cdot 7!+3\cdot 4!+3\cdot 5! -2\cdot 3!-2\cdot 2!+1$$
With the alternate definition of subsequence (not supported by the example) which also excludes $98765\mathbf04\mathbf{123},$ we start to get something that looks like your answer, but you assume $|A_1\cap A_2\cap A_3|=|A_1\cap A_3\cap A_4|,$ which is not true. Instead, you get:
\begin{align}|\Sigma|&=10!\\ |A_1|=|A_2|=|A_3|=|A_4|&=\binom{10}{4}6!\\ |A_1\cap A_3|=|A_1\cap A_4|=|A_2\cap A_4|&=\binom{10}{4}\binom{6}{4}2!\\ |A_1\cap A_2|=|A_2\cap A_3|=|A_3\cap A_4|&=\binom{10}{6}4!\\ |A_1\cap A_2\cap A_3|=|A_2\cap A_3\cap A_4|&=\binom{10}{8}2!\\ |A_1\cap A_3\cap A_4|=|A_1\cap A_2\cap A_4|&=\binom{10}{4}\\ |A_1\cap A_2\cap A_3\cap A_4|&=1 \end{align}
• I understand everything in your answer but I don't understand conceptually why ${10\choose 4}6!$ is not equivalent to $7!$. My logic was: choose $4$ spots out of $10$ available and permute the rest. Why is wrong with the ${10\choose 4}$ part? – Yos Jun 12 '18 at 16:51
• I'm not sure what you mean. Since $\binom{10}{4}\neq 7$, $\binom{10}{4}6!\neq 7\cdot 6!=7!.$ Why do you want to choose four spots from $10$? After you've permuted $456789$, you can insert $0123$ in any of seven places, not into four of ten places. – Thomas Andrews Jun 12 '18 at 16:54
• But even with that definition, you'd still have $|A_1\cap A_2|\neq |A_1\cap A_3|.$ – Thomas Andrews Jun 12 '18 at 17:01
• I meant consecutive subsequences, I should have mentioned this. So your first answer answers the question. The example you provided in the second part of the answer $98765\mathbf04\mathbf{123},$ wouldn't be valid for the OP. But it's still an interesting solution to learn from – Yos Jun 12 '18 at 17:10