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

catalan-numberscombinatorial-proofscombinatorics

A Dyck path of order $n$ can be thought of as a sequence of $n$ $0$'s and $n$ $1$'s such that in any initial segment, the $1$'s do not outnumber the $0$'s. A peak is a $0$ which is immediately followed by a $1$. It can be shown that the number of Dyck paths of order $n$ with exactly $k$ peaks is counted by the Narayana numbers,
$$
N(n,k) = \frac1n\binom{n}k\binom{n}{k-1}.
$$

Using the above formula, it is easy to show that the Narayana numbers are symmetric in $k$, in the sense that $N(n,k)=N(n,n+1-k)$. However, the corresponding symmetry between Dyck paths with $k$ peaks and Dyck paths with $n+1-k$ peaks is not so clear (to me).

What is a bijection between Dyck paths of order $n$ with $k$ peaks and Dyck paths of order $n$ with $n+1-k$ peaks?

Best Answer

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.

Related Question