Let $n\geq4$ how many permutations $\pi$ of $S_n$ has the property that $1,2,3$ appear in the same cycle of $\pi$....

Question

Let $n\geq4$ how many permutations $\pi$ of $S_n$ has the property that $1,2,3$ appear in the same cycle of $\pi$,while $4$ appears in a different cycle of $\pi$ from $1,2,3$?

My attempt:For $n=4$ I have found two such permutations $(123)(4)$ and $(132)(4)$

For $n=5$ I have found four such permutations $(123)(45),(132)(45),(123)(4)(5),(132)(4)(5)$

For $n=6$ I have found $12$ such permutations.

$(123)(456),(132)(456),(123)(465),(132)(465),(123)(45)(6),(132)(45)(6),(123)(46)(5),(132)(46)(5),(123)(56)(4),(132)(56)(4),(123)(4)(5)(6),(132)(4)(5)(6)$

My problem:How we can generally solve this?What will be the general formula for number of such permutations?

Edit: For $n=5$ we also have the permutations $(1235)(4),(1325)(4),(1532)(4)$ and similarly these are 6.So in $S_5$ we have $4+6=10$ such permutations.

Answer 1

If a permutation $\sigma \in S_n$ consists of a $j$-cycle with $1, 2, 3$, call that cycle $\gamma_j$ and the set of numbers it is cycling $\Gamma_j = \{ 1, 2, 3, ... \} \not\ni 4$. The number of such $j$-cycles is $\color{blue}{(j-1)!}$

We can write $\sigma = \gamma_j\sigma'$ where $\sigma'$ is a member of all the permutations on $\Gamma_j' = \{ 1, 2, 3, ..., n \} - \Gamma_j$. As the cardinality of $\Gamma_j$ is $j$, the cardinality of $\Gamma_j' = n - j$ and the number of such permutations $\sigma'$ is $\color{blue}{(n-j)!}$

Hence when $1, 2, 3$ is in a $j$-cycle, there are $\color{blue}{(j-1)!(n-j)!}$ possible permutations $\sigma$.

Summing up now over all possible $j$, the total number $t_n$ of such permutations for a given $n \geq 4$ is

$$t_n = \sum_{j=3}^{n-1} (j-1)!(n-j)!$$

Calculating the first few values,

$t_4 = \sum_{j=3}^{3} (j-1)!(4-j)! = 2!1! \hspace{25mm} = \ \ 2$

$t_5 = \sum_{j=3}^{4} (j-1)!(5-j)! = 2!2! + 3!1! \hspace{13mm} = 10$

$t_6 = \sum_{j=3}^{5} (j-1)!(6-j)! = 2!3! + 3!2! + 4!1! \, = 60$

Answer 2

For $n\ge 4$, let $f(n)$ be the number of permutations in $S_n$ in which $1,2,3$ are all in the same cycle and $4$ is in a different cycle.

To go from $f(n)$ to $f(n+1)$ observe that for each desirable permutation in $S_n$ we can build $n+1$ desirable permutations in $S_{n+1}$ by inserting $n+1$ somewhere in each existing cycle ($n$ ways) or by mapping $n+1$ to itself.

For example, from the desirable permutation $(1532)(46)(7)$ in $S_7$, we have correspondingly $8$ desirable permutations ins $S_8$:

$(18532)(46)(7)$

$(15832)(46)(7)$

$(15382)(46)(7)$

$(15328)(46)(7)$

$(1532)(486)(7)$

$(1532)(468)(7)$

$(1532)(46)(78)$

$(1532)(46)(7)(8)$

So in general $f(n+1)=(n+1)f(n)$

This also implies that the ratio of desirable permutations to total permutations remains constant.

You already noted that $f(4)=2$.