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?

  • 2
    $\begingroup$ This is a classic inclusion-exclusion question. $\endgroup$ – 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}$$

Your final answer will be:

$$\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}$$

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Yos Jun 12 '18 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jun 12 '18 at 16:54
  • $\begingroup$ I suppose there is another definition of sub-sequence that would restrict not just '9876540123' but also '9081726354,' since '0,1,2,3' appear in order in the permutation. But if that is what the question means then it gave an irritating example. $\endgroup$ – Thomas Andrews Jun 12 '18 at 16:59
  • $\begingroup$ But even with that definition, you'd still have $|A_1\cap A_2|\neq |A_1\cap A_3|.$ $\endgroup$ – Thomas Andrews Jun 12 '18 at 17:01
  • $\begingroup$ 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 $\endgroup$ – Yos Jun 12 '18 at 17:10

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.