Two statistics on the permutation group

Question

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?

Answer 1

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$.

Answer 2

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])

Then ask, what findstat knows about them:

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.