If we resort numbers in permutations of length $n$ by their positions, ex.
$12=12, 21=21$
$123=123, 132=132, 213=213, \color{red}{231=312}, \color{red}{312=231}, 321=321$
$1234=1234, 1243=1243, 1324=1324, \color{blue}{1342=1423}, \color{blue}{1423=1342}, 1432=1432, 2134=2134, 2143=2143, \color{blue}{2314=3124}, \color{red}{2341=4123}, \color{red}{2413=3142}, \color{blue}{2431=4132}, \color{blue}{3124=2314}, \color{red}{3142=2413}, 3214=3214, \color{blue}{3241=4213}, 3412=3412, \color{red}{3421=4312}, \color{red}{4123=2341}, \color{blue}{4132=2431}, \color{blue}{4213=3241}, 4231=4231, \color{red}{4312=3421}, 4321=4321$
so quantity of permutations, which have $k$ same numbers in same positions with it's resort equals
$$q(n,k)=\binom{n}{k}s(k)t(n-k)$$
where
$$\sum\limits_{k=0}^{\infty} s(k)\frac{x^k}{k!}=\exp(\frac{x}{2}(x+2))$$
$$1,1,2,4,10,26,76,232,\cdots$$
$$\sum\limits_{k=0}^{\infty} t(k)\frac{x^k}{k!}=\frac{\exp(-\frac{x}{2}(x+2))}{1-x}$$
$$1,0,0,2,6,24,160,1140,\cdots$$
For example
$q(0,0)=0$
$q(1,0)=0, q(1,1)=1 [1]$
$q(2,0)=0, q(2,1)=0, q(2,2)=2 [12,21]$
$q(3,0)=2 [\color{red}{231,312}], q(3,1)=0, q(3,2)=0, q(3,3)=4 [123,132,213,321]$
$q(4,0)=6 [\color{red}{2341, 2413, 3142, 3421, 4123, 4312}], q(4,1)=8 [\color{blue}{1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213}], q(4,2)=0, q(4,3)=0, q(4,4)=10 [1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321]$
How can I prove it?
Best Answer
The "resort" of a permutation is its inverse, and $\pi(i)=\pi^{-1}(i)$ iff $i$ is either fixed by $\pi$ or belongs to a 2-cycle in $\pi$. That means $q(n,k)$ is the number of permutations of $n$ things with exactly $k$ numbers $i$ such that $\pi^2(i)= i$.
To count these, first choose the $k$ numbers fixed by $\pi^2$ - there are $n\choose k$ ways to do that. On these $k$ numbers $\pi$ acts as an involution: there are A000085 of those, which is your $s(k)$. On the other $n-k$ numbers $\pi$ must be fixed point free with all cycles of length at least 3, and there are A038205 of those, which is your $t(n-k)$.
So all you need is to prove that these sequences have the claimed generating sequences. Here's a sketch of how to do that: for the details (and for much greater generality) look at chapter 3 of Wilf's Generatingfunctionology, freely available online.
Suppose you want to count the number of permutations on $n$ letters all of whose cycle lengths come from a particular set $S$. The exponential generating function is defined to be: $$ \mathcal{H}_S(x) = \sum_{n \geq 0} h_S(n) x^n /n!$$ where $h_S(n)$ counts how many permutations in $S_n$ can be written as a product of cycles with lengths in $S$. We then have the following lemma: let $S_1$ and $S_2$ be disjoint and let $S =S_1 \cup S_2$. Then $$ \mathcal{H}_S = \mathcal{H}_{S_1}\mathcal{H}_{S_2}.$$ This is a very special case of the Fundamental Lemma from Wilf $\S3.4$ (put $y=1$ there). It's not difficult to prove: if you compare coefficients of $x^n$, it is equivalent to proving that $$ h_S(n) = \sum_{m \geq 0} \binom{n}{m} h_{S_1}(m)h_{S_2}(n-m).$$ To see this, consider building a permutation on $n$ letters whose cycle lengths come from $S=S_1 \cup S_2$, such that $m$ of those $n$ letters are involved in cycles with lengths from $S_1$ and the rest from $S_2$. There are $\binom{n}{m}$ ways to choose those $m$ letters, then $h_{S_1}(m)$ ways to choose a permutation of those $m$ letters with lengths from $S_1$. On the remaining $n-m$ letters has cycle lengths from $S_2$, and there are therefore $h_{S_2}(n-m)$ ways to choose it. Summing over the possible values of $m$ gives the result.
Here's a simple example where we can compute $\mathcal{H}_S$ directly: let $S = \{r\}$, so you are counting the number of permutations in $S_n$ all of whose cycles have length $r$. Clearly $h_S(n)=0$ unless $n=kr$, in which case $h_S(n) = \frac{n!}{r^k k!}$ (each of the $k$ $r$-cycles can be written in $r$ different ways, hence the $r^k$, and the order of the cycles doesn't matter, hence the $k!$). It follows $$\mathcal{H}_S(x) = \sum_{k} \frac{x^{kr}}{(kr)!} \frac{(kr)!}{r^k k!} = \exp(x^r/r).$$
For your $s(n)$ we need to look at permutations all of whose cycles have lengths 1 or 2. Using the fundamental lemma and the cases $r=1$ and $r=2$ of our example and putting $y=1$, the exponential generating function is $$ \exp( x) \exp(x^2/2) = \exp(x + x^2/2)$$ as you observed. For $t(n)$, which counts permutations all of whose cycles have length at least 3, we end up with $$ \exp(x^3/3)\exp(x^4/4)\cdots = \exp\left( \sum_{i \geq 3} x^i/i\right) = \exp\left(\log \frac{1}{1-x} - x - x^2/2\right) = \frac{e^{-x-x^2/2}}{1-x}$$ again agreeing with your observation.