8

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?

Martin Rubey
  • 5,563
T. Amdeberhan
  • 41,802
  • 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
  • So Martin's statement is even more refined, it appears. The PIs question is whether the number of permutations having a k-descent is the same as the number of permutations having a k-excedence. And Martin (and actually my test above also) tests for the distribution of k-descents is the same as the distribution of k-excedences. – Christian Stump Nov 21 '16 at 18:20

2 Answers2

13

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

Richard Stanley
  • 49,238
6

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.

Martin Rubey
  • 5,563