# Two statistics on the permutation group

Let $\mathfrak{S}_n$ be the permutation group on an $n$-element set. For each fixed $k\in\mathbb{N}$, consider the two sets $$A_n(k)=\{\sigma\in\mathfrak{S}_n\vert\,\, \text{\exists i,\,\, 1\leq i\leq n\, such that \,\sigma(i)-i=k}\}$$ and $$B_n(k)=\{\sigma\in\mathfrak{S}_n\vert\,\, \text{\exists i,\,\, 1\leq i\leq n\, such that \,\sigma(i+1)-\sigma(i)=k}\}.$$

QUESTION. I believe the following is true, for each $n$ and $k$: $$\# A_n(k)=\# B_n(k).$$ Is there a combinatorial proof of this? If it is known, then can you provide references?

• Isn't $A_n(0)$ the set of non-derangements (i.e., those permutations having a fixed point), while $B_n(0) = \emptyset$? – Christian Stump Nov 21 '16 at 17:59
• Okay, it appears to hold for $k>0$ (tested for $n \leq 8, 1 \leq k \leq n$. – Christian Stump Nov 21 '16 at 18:05
• usual suspects here :-) - yes, apparently $\mathbb N=\{1,2,3,\dots\}$. – Martin Rubey Nov 21 '16 at 18:05
• Since this generalises the equidistribution of descents and excedences, you might get lucky with one of the bijections showing this. – Martin Rubey Nov 21 '16 at 18:09
• Indeed, I just checked that - experimentally -- for each $k$ the distribution of the number of $k$-excedences equals the distribution of $k$-descents. – Martin Rubey Nov 21 '16 at 18:14

A simple variant of the "transformation fondamentale" of Rényi and of Foata-Schützenberger does the trick. Write a permutation $\sigma$ in disjoint cycle form, with the smallest element of each cycle first, and the cycles arranged in decreasing order of the smallest element, e.g., $(7,8)(5,6,9)(3)(1,4,2)$. Erase the parentheses to get another permutation $\hat{\sigma}$, written as a word, e.g., $785693142$. This gives a bijection $\mathfrak{S}_n\to\mathfrak{S}_n$ with the property that $\sigma(i)-i=k>0$ if and only if $\hat{\sigma}(j+1)-\hat{\sigma}(j)=k$, where $\hat{\sigma}(j)=i$.

• I think that this is precisely what Find Stat found, reproduced in the other answer. – Martin Rubey Nov 21 '16 at 19:40
• @Stanley: I like this cute and crisp proof. – T. Amdeberhan Nov 21 '16 at 20:04

You can use sage and www.findstat.org to find a candidate for a bijection as follows. First define the statistics you are interested in:

def A_num(s, k):
return len([1 for i,e in enumerate(s,1) if e-i==k])

def B_num(s, k):
return len([1 for e,f in zip(s, s[1:]) if f-e==k])


sage: findstat("Permutations", lambda s: A_num(s, 2), depth=3)
0: (St000534: The number of 2-rises of a permutation., [Mp00066: inverse, Mp00087: inverse first fundamental transformation, Mp00064: reverse], 200)

sage: findstat("Permutations", lambda s: B_num(s, 2), depth=3)
0: (St000534: The number of 2-rises of a permutation., [], 200)

sage: findstat("Permutations", lambda s: A_num(s, 1), depth=3)
0: (St000237: The number of indices $i$ such that $\pi_i=i+1$., [], 200)
1: (St000214: The number of adjacencies (or small descents) of a permutation., [Mp00066: inverse, Mp00087: inverse first fundamental transformation], 200)
2: (St000441: The number of successions (or small ascents) of a permutation., [Mp00066: inverse, Mp00087: inverse first fundamental transformation, Mp00064: reverse], 200)

sage: findstat("Permutations", lambda s: B_num(s, 1), depth=3)
0: (St000441: The number of successions (or small ascents) of a permutation., [], 200)
1: (St000214: The number of adjacencies (or small descents) of a permutation., [Mp00064: reverse], 200)
2: (St000237: The number of indices $i$ such that $\pi_i=i+1$., [Mp00064: reverse, Mp00086: first fundamental transformation, Mp00066: inverse], 200)


So, this suggests that using the composition of the maps http://www.findstat.org/MapsDatabase/Mp00066, http://www.findstat.org/MapsDatabase/Mp00087 and http://www.findstat.org/MapsDatabase/Mp00064 might be a good idea. No guarantee, of course.

• I think this is an answer -- I also tested this, and this combination of maps does yield the desired bijection for $n \leq 8$ and all $k$. – Christian Stump Nov 21 '16 at 18:44
• I guess I should now create a new mathoverflow account Find Stat. Is Shalosh Ekhad a mathoverflow user? – Martin Rubey Nov 21 '16 at 18:51
• To see this bijection in action, you can go to www.findstat.org/St000650 and then click on "search for values" to find that the third hit is exactly this map. – Christian Stump Nov 21 '16 at 18:57
• @MartinRubey: this is a good tool. Thank you! – T. Amdeberhan Nov 21 '16 at 20:03
• @MartinRubey: Regarding Ekhad, you may contact Doron Zeilberger. – T. Amdeberhan Nov 22 '16 at 0:02