Combinatorical permutation-cycles problem How many permutations $\pi$ $\in$ $Sn$ ($n>2$) where $1$ and $2$ belong to the same cycle?
Here is what I have so far:
First I put $1$ and $2$ in the same cycle and make $j$ elements from the other $(n-2)$ join them in the same cycle: ${n-2 \choose j}$ with $0<j<n-2$
Then I must put the $(n-2-j)$ elements in other cycles. For that I use the Stirling numbers (which garantees that at least 1 element is put in a cycle) in  to distribuite those elements in the $k$ cycles, with $(1<k<j)$:
$S(n-2-j,k)$
My final answer is
$\sum_{j=0}^{\ n-2} {{n-2 \choose j} . \sum_ {k=0}^{\ j} {S(j,k)}}$
Is there something wrong with my resolution or a simpler way to solve it?
 A: We have from first principles the closed form
$$S_n = \sum_{j=0}^{n-2} {n-2\choose j} \frac{(j+2)!}{j+2} (n-2-j)!.$$
This is for n $\ge 2$
$$S_n = (n-2)! \sum_{j=0}^{n-2} (j+1) = \frac{1}{2} (n-2)! (n-1) n
= \frac{1}{2} n!.$$
We may think of the permutation in table notation to explain the factor $(n-2-j)!.$ Once we choose the $j$ extra elements for the cycle containing $1$ and $2$, the corresponding $j+2$ pre-image / image pairs are removed from the table. The table now has the remaining $n-2-j$ values in the pre-image and the image and we may permute the values in the image any way we like.
A: There is a purely combinatorial approach as well. Let $\pi\in S_n$, and let $$\pi=\sigma_1\sigma_2\ldots\sigma_m\tag{1}$$ be its complete representation as a product of cycles, including the $1$-cycles for its fixed points. We can always take $(1)$ to be in the following standard form:

*

*each cycle is written with its smallest element first, and

*the cycles are arranged in descending order of their smallest elements.

Since $1$ is necessarily the smallest element of the cycle containing it, it must be the first element of $\sigma_m$.
Let $T$ be the set of $\pi\in S_n$ such that $1$ and $2$ are in different cycles of $\pi$. If
$$\pi=\sigma_1\sigma_2\ldots\sigma_m\in T\,,$$
then $2$ is the first element of $\sigma_{m-1}$. Let $\sigma'$ be the concatenation $\sigma_m\sigma_{m-1}$. That is, if $\sigma_{m-1}=(2\ldots s_k)$ and $\sigma_m=(1\ldots t_\ell)$, then $\sigma'=(1\ldots t_\ell 2\ldots s_k)$. (Note that this is not the product of $\sigma_m$ and $\sigma_{m-1}$.) Let $\hat\pi=\sigma_1\ldots\sigma_{m-2}\sigma$. Then $\hat\sigma\in S_n\setminus T$ and is written in the standard form $(1)$.
This transformation is invertible. If $\pi=\sigma_1\ldots\sigma_m\in S_n\setminus T$ is in standard form, then $\sigma_m$ has the form $(1\ldots t_\ell 2\ldots s_k)$. Let $\sigma_{m+1}'=(1\ldots t_\ell)$ and $\sigma_m'=(2\ldots s_k)$; then $\pi'=\sigma_1\ldots\sigma_{m-1}\sigma_m'\sigma_{m+1}'\in T$ is in the standard form $(1)$, and $\widehat{\pi'}=\pi$. Thus,
$$|S_n\setminus T|=|T|=\frac12|S_n|=\frac{n!}2\,.$$
