8
$\begingroup$

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?

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

2 Answers 2

13
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ I think that this is precisely what Find Stat found, reproduced in the other answer. $\endgroup$ Nov 21, 2016 at 19:40
  • $\begingroup$ @Stanley: I like this cute and crisp proof. $\endgroup$ Nov 21, 2016 at 20:04
6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ Nov 21, 2016 at 18:44
  • 1
    $\begingroup$ I guess I should now create a new mathoverflow account Find Stat. Is Shalosh Ekhad a mathoverflow user? $\endgroup$ Nov 21, 2016 at 18:51
  • $\begingroup$ 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. $\endgroup$ Nov 21, 2016 at 18:57
  • $\begingroup$ @MartinRubey: this is a good tool. Thank you! $\endgroup$ Nov 21, 2016 at 20:03
  • $\begingroup$ @MartinRubey: Regarding Ekhad, you may contact Doron Zeilberger. $\endgroup$ Nov 22, 2016 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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