Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this? 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?
 A: 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$.
A: 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)!$$
A: May be you will find this way less brutish, though hardly elegant  !


*

*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.

*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.

*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 ! ]

*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

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

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

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