Bijection between Dyck paths with $k$ peaks and $n+1-k$ peaks

A picture will help to visualize the bijection described in this post : please take your pencil.

First, the setting : it will be easier to view Dyck paths as (ordered rooted) trees, using the traditional device of the contour function (I put a ref below). A peak is then a leaf of the tree (a vertex without children). Also, Dyck paths being of length 2, the trees will have n edges, so that the minimal number of leaves will be 1 and the maximal number will be . Call brothers of a vertex the children of the same father (by convention, we discard the vertex itself).

Your claim is that, among trees on $n$ edges, there is as many with $k$ leaves as with $n+1-k$ leaves.

The bijection goes as follows : to a (rooted) tree on $n$ edges, we will associate another (rooted) tree with $n$ edges, by keeping the same vertex set (also the same root) and changing the edge set. To that end, it is enough to define the father of every vertex distinct from the root in the new tree, let's call it the new father.

Consider a vertex distinct from the root and look for the most recent ancestor of that vertex that has a brother to its right : this will the vertex itself if it has a brother to its right, or the father of this vertex if the vertex itself has no brother to its right but its father has, and so on...

  • In case there is such an ancestor : the new father is the brother immediately to the right of that ancestor.

  • In case there is no such ancestor : the new father is the root of the tree.

The converse map is obtained by replacing the word "right" by the word "left" in the above description.

I'll let you check this works with respect to the property you have in mind for the leaves : a possible proof is by recurrence on the number of leaves (it is easy to see it works for one leave, then one looks at the shape of trees with two leaves, and from there, the idea os the recurrence should be quite clear)

(This is closely related, but in a subtle way distinct from what is called rotation bijection in computer science, see Flajolet and Sedgewick on p.73.)

--

The reference on the contour function (in French sorry):

https://fr.wikipedia.org/wiki/Arbre_de_Galton-Watson#Processus_de_contour.

--

From far, the question of MathSE on which I spent the most time. Perhaps it is known in combinatorics, I have done no research on the topic.


Such a bijection is constructed by Panyushev in Theorem 4.2 of https://arxiv.org/abs/math/0303107. It is the Type A version of a more general conjectured duality for "ad-nilpotent ideals of Borel subalgebras of simple Lie algebras" he proposes in that paper.