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
up vote 11 down vote accepted

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

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

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.

  • 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
  • 1
    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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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