<s>[INST] Permutations of the set $\{1,\ldots,n\}$ are there such that, no two of the numbers $1,2,3$ are consecutive 
How many permutations of the set $\{1,\ldots,n\}$ are there such that no two of the numbers $1,2,3$ are consecutive?

My first thought was the inclusion-exclusion formula, like here, but it got messy, so I decided to work with partitions.
Let's consider $3$ places for the numbers $1,2,3$. Later, we can arrange them in $3!$ ways. Then, we're left with $n-3$ elements. The gaps between $1^{\mathrm{st}}$ and $2^{\mathrm{nd}}$ and $2^{\mathrm{nd}}$ and $3^{\mathrm{rd}}$ element should in no way be empty, so, we need partitions of the set $\{4,\ldots,n\}$ into $4,3$ and $2$ subsets. There are $S(n-3,4),S(n-3,3)$ and $S(n-3,2)$ of them respectively, where $S(n,k)$ is a Stirling number of the second kind. After the sizes of sets have been chosen, we can permute those remaining $n-3$ elements from the original set. If I'm not wrong, this should be equivalent to the problem of placing distinct objects (here numbers) into distinct boxes (here, gaps). Therefore, my answer is $\#=3!(n-3)!\left(S(n-3,4)+2S(n-3,3)+S(n-3,2)\right).$
Is this correct? Or did I over/undercount?
 [/INST] I will solve the problem in two ways.
Method 1:  We use the Inclusion-Exclusion Principle.
There are $n!$ permutations of the elements of the set $\{1, 2, 3, \ldots, n\}$.  From these, we must exclude those permutations in which at least two of the numbers $1, 2, 3$ are consecutive.
Since there are only three numbers in the subset, there can be at most two pairs of consecutive numbers from the subset $\{1, 2, 3\}$ in the permutation, with two pairs occurring when all three of those numbers appear consecutively in the permutation.
A pair of consecutive numbers from the subset $\{1, 2, 3\}$:  There are $\binom{3}{2}$ ways to select which two of those three numbers are consecutive.  We now have $n - 1$ objects to permute, a block of two consecutive numbers and the other $n - 2$ numbers in the set $\{1, 2, 3, \ldots, n\}$.  The $n - 1$ objects can be permuted in $(n - 1)!$ ways.  The numbers in the block can be permuted in $2!$ ways.  Hence, there are
$$\binom{3}{2}(n - 1)!2!$$
such permutations.
However, if we subtract that amount, we will have subtracted each permutation in which there are two pairs of consecutive numbers drawn from the subset $\{1, 2, 3\}$ twice, once when we designate the first two of the three consecutive numbers as the pair of consecutive numbers and once when we designate the last two of the three consecutive numbers as the pair of consecutive numbers.  We only want to subtract such permutations once, so we must add them to the total.
Two pairs of consecutive numbers from the subset $\{1, 2, 3\}$:  For this to occur, the three numbers in the subset must appear in consecutive positions.  Consequently, we have $n - 2$ objects to permute, the block consisting of the numbers $1, 2, 3$ and the other $n - 3$ numbers in the set $\{1, 2, 3, \ldots, n\}$.  The $n - 2$ objects can be permuted in $(n - 2)!$ ways.  The numbers in the block can be permuted in $3!$ ways.  Hence, there are
$$\binom{3}{3}(n - 2)!3!$$
such permutations.
By the Inclusion-Exclusion Principle, the number of admissible permutations is
$$n! - \binom{3}{2}(n - 1)!2! + \binom{3}{3}(n - 2)!3!$$
Method 2: We arrange the $n - 3$ numbers in the subset $\{4, 5, 6, \ldots, n\}$, then place the numbers $1, 2, 3$ in the spaces this creates.
There are $(n - 3)!$ ways to arrange the $n - 3$ numbers in the subset $\{4, 5, 6, \ldots, n\}$.  This creates $n - 2$ spaces in which to place the numbers $1, 2, 3$, including $n - 4$ spaces between successive numbers in the permutation of the numbers in the subset $\{4, 5, 6, \ldots, n\}$ and two at the ends of the row.  To ensure that no two of the three numbers $1, 2, 3$ are consecutive, we must choose three of these $n - 2$ spaces in which to place the numbers $1, 2, 3$, which can be done in $\binom{n - 2}{3}$ ways.  The three numbers $1, 2, 3$ can be arranged in the selected spaces in $3!$ ways.  Hence, the number of admissible permutations is
$$(n - 3)!\binom{n - 2}{3}3!$$
We show that the above methods yield equivalent results.
\begin{align*}
n! - \binom{3}{2}(n - 1)!2! + \binom{3}{3}(n - 2)!3! & = n! - 3 \cdot 2 \cdot (n - 1)! + 1 \cdot 6 \cdot (n - 2)!\\
& = n(n - 1)(n - 2)! - 6(n - 1)(n - 2)! + 6(n - 2)!\\
& = (n - 2)![n(n - 1) - 6(n - 1) + 6]\\
& = (n - 2)!(n^2 - n - 6n + 6 + 6)\\
& = (n - 2)!(n^2 - 7n + 12)\\
& = (n - 2)!(n - 3)(n - 4)
\end{align*}
\begin{align*}
(n - 3)!\binom{n - 2}{3}3! & = (n - 3)! \cdot \frac{(n - 2)!}{3!(n - 5)!} \cdot 3!\\
& = (n - 3)!(n - 2)(n - 3)(n - 4)\\
& = (n - 2)!(n - 3)(n - 4)                          
\end{align*}
so the results we obtained are equivalent.
Let's compare your result with the above result.
In order for no two of the numbers $1, 2, 3$ to be consecutive in a permutation of the set $\{1, 2, 3, \ldots, n\}$, $n$ must be at least $5$.
For $n = 5$ and $n = 6$, our answers agree.
However, if $n = 7$, my formula yields
$$(n - 2)!(n - 3)(n - 4) = 5! \cdot 4 \cdot 3 = 1440$$
Using the table of Stirling numbers of the second kind, we see that your result gives
\begin{align*}
3!(n - 3)![S(n - 3, 2) + S(n - 3, 3) + S(n - 3, 4)] & = 3!4![S(4, 2) + S(4, 3) + S(4, 4)]\\
& = 3!4!(7 + 6 + 1)\\
& = 2016
\end{align*}
so your method overcounts.
I suspect the error lies in permuting elements which are in different blocks.  Once you separate the numbers $4, 5, 6, \ldots, n$, they can only be permuted within each block.
</s>