# Quantity of same numbers in same positions of permutations and its resort

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?

• Where/how did you find it? – Gerry Myerson Oct 15 '18 at 3:56
• @GerryMyerson, thank you for comment! I calculate values in excel, search first column and diagonal in OEIS and after some time see pattern. – user514787 Oct 15 '18 at 4:01
• @GerryMyerson, looks like question is very simple. Is it well-known result? How is it obvious? – user514787 Oct 15 '18 at 4:15
• Doesn't look simple to me, and I don't recognize it. – Gerry Myerson Oct 15 '18 at 4:21

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.

• Thank you very much for editing! Sorry, that I see it just now. I think it will be better to add comment to question about your editing. Also English not my native, so if there some mistakes, sorry! – user514787 Dec 4 '18 at 3:28