Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Question

Here's a problem I've solved:

Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4).

So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, where $i,i+1,i+2,i+3$ are consecutive numbers. Only $A_1,A_2,A_3,A_4$ are non-empty, so we can use inclusion-exclusion principle. So, if $S_0$ is the set of all permutations of $[7]$ and $S_j=\sum_{i_1\leq i_2 \leq ...\leq i_j} |A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_j}|$, then we can easily count that $S_1 = 4 * 4!$ (choose which number starts block of 4 consecutive numbers (4 choices), then permute this block and 3 remaining numbers in $4!$ ways), $S_4 = 1$, and for $S_2, S_3$ I've used brute-force - I listed all possible set arrangements and counted them by hand (there are only $\binom{4}{2}+\binom{4}{3}$ cases to consider). Then the answer is $S_0-S_1+S_2-S_3+S_4$ by inclusion-exclusion principle.

The question is - can the brute-force part of the solution be omitted? Is there any smarter way to do this?

Answer 1

Here's another semi-brutish way of counting the number of permutations that include a run of four consecutive numbers.

Note that for any permutation $abcdefg$ with a run of four consecutive numbers, the middle number $d$ must participate in the run. Let $n_i$ be the number of such permutations in which the middle number is $i$, for $i=1$ to $7$. A modest amount of brute force gives

$$n_1+n_2+n_3+n_4+n_5+n_6+n_7=6+10+14+18+14+10+6=78$$

One sanity check is that $n_{8-i}=n_i$. This is because subtracting each number in a permutation from $8$ and then writing the permutation backwards preserves consecutive runs.

Just to show this isn't completely brute force, here's the corresponding answer for permutations of the numbers $1$ to $9$ with a run of five consecutive numbers, presented in a suggestive form:

$$4!+(4!+1\cdot3\cdot3!)+(4!+2\cdot3\cdot3!)+(4!+3\cdot3\cdot3!)\\+(4!+4\cdot3\cdot3!)\\+(4!+3\cdot3\cdot3!)+(4!+2\cdot3\cdot3!)+(4!+1\cdot3\cdot3!)+4!$$

It should be reasonably clear this leads to a simple formula for the number of permutations of the numbers $1$ to $2n-1$ with a run of $n$ consecutive numbers:

$$(n^2-n+1)(n-1)!$$

Answer 2

May be you will find this way less brutish, though hardly elegant !

1. Look only at the 2 extremities of the sequence (call them L & R) and how many #s are removed to create blocks of consecutive #s, and we shall count for blocks of exactly 4,5,....7.

2. We shall count blocks of exactly 4 (which will pose most difficulty, and illustrate the process most clearly). Note that such blocks can be of two types: starting/ending blocks "insecure" at only one end, and intermediate blocks "insecure" at both ends.

3. Block 1234, side L is secure, side R is not: Thus only 2 of the removed #s can be placed adjacent to R: 3-0 placed L-R in 3! ways, a little thought will show that 2-1 or 1-2 and 0-3 will each have 4 ways of placement (total 18). Ditto for block 5678. [There is a pattern to all this madness ! ]

4. Block 2345 (insecure at both ends): It can easily be seen that there will be 4 placements each for 3-0 or 0-3, and 3 placements each for 2-1 or 1-2 (total 14). Ditto for block 3456

5. So for blocks of exactly 4, there will be $(18+14)*2$ = 64 ways.

6. Counting for blocks of 5, 6 & 7 is relatively trivial, 11,2, & 1 respectively.

7. Thus final answer = 64+11+2+1 = 78.

Answer 3

The brute-force cases are calculated exactly the same way as the case you correctly calculated: to find the number of ways to permute $n$ numbers with a run of $k$, choose the initial number of the run in $n-k+1$ ways, and then permute the position of the run and the remaining $n-k$ numbers in $(n-k+1)!$ ways. You need to include/exclude runs of $4$ or greater. So the result is $$ 7! - 4\cdot 4! + 3\cdot 3! - 2\cdot 2! + 1\cdot 1!=7!-96+18-4+1=7!-81. $$

---

Update: The simple inclusion/exclusion reasoning above doesn't quite work, because you need to exclude the cases where there are two runs of length $k$... not the cases where there is a run of length $k+1$... from the enumeration of cases with a run of length $k$. This is different because you can have two runs of length $k$ that overlap by any number of positions from $2k-n$ to $k-1$ (assuming $2k-n\ge 1$), and an overlap of length $m$ produces a run of length $2k-m$. Fixing $n$ sufficiently large, and letting $N_k$ be the number of ways to arrange $n$ elements with a run of at least $k$, we have $N_n=1\cdot 1!$, and $$N_{n-1}=2\cdot 2! - N_n = 2\cdot 2! - 1\cdot 1! = 3,$$ and $$ N_{n-2}=3\cdot 3! - N_{n-1} - N_{n} = 3\cdot 3! - (2\cdot 2! - N_n) - N_n \\ = 3\cdot 3! - 2\cdot 2!=14. $$ Next, $$ N_{n-3}=4\cdot 4! - N_{n-2} - N_{n-1} - N_{n} = 4\cdot 4! - (3\cdot 3! - N_{n-1} - N_{n}) - N_{n-1} - N_{n} \\ = 4\cdot 4! - 3\cdot 3! = 78. $$ And so on. For $2k-n\ge 1$, the number of permutations of $n$ elements with a run of length $k$ is given by $(n-k+1)\cdot(n-k+1)!-(n-k)\cdot(n-k)!$. For $2k\le n$, on the other hand, there is the additional complication that you can also have two non-overlapping runs of length $k$ that aren't joined into a single run of length $2k$, and these cases also need to be subtracted. For instance, for $n=6$ and $k=3$, you get $4\cdot 4! - 3\cdot 3!-1=77$, where the final $1$ comes from the single case $456123$.