3
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – user514787 Dec 4 '18 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.