5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the wonderful answer! It is clear that this operation reverses the number of leaves, since a vertex becomes a leaf if and only if it is the leftmost child of a vertex which is not a leaf. It is less clear why replacing “right” and “left” results in an inverse operation, but I bet I can figure it out. $\endgroup$ – Mike Earnest Aug 19 at 16:48
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Oh hi Sam! Thanks for the answer; that is quite a simple, beautiful mapping. $\endgroup$ – Mike Earnest Aug 20 at 2:37
  • $\begingroup$ Excellent ref : it is indeed simpler to think in term of Ferrers diagrams as far as the symmetry is concerned indeed ! $\endgroup$ – Olivier Aug 20 at 10:20
1
$\begingroup$

There is a nice bijection between Dyck paths of order $n$ and planar binary trees. The bijection $\phi$ can be described recursively. Every Dyck path $D$ of order $n$ can be uniquely decomposed as $(0,D',1,D'')$, where $D'$ and $D''$ are smaller (possible empty) Dyck paths. Explicitly, the "$1$" in that formula is the end of the shortest, nonempty prefix with an equal number of $0$'s and $1$'s. Then $\phi(D)$ is defined to be the planar binary tree whose left subtree of the root is $\phi(D')$ and whose right subtree is $\phi(D'')$.

Under this bijection, peaks in the original path correspond to left children in the resulting tree. There is an obvious involution on planar binary trees with reverses left and right children; just reflect the tree vertically! Composing this with the bijection in the last paragraph, you get an involution on Dyck paths which takes a path with $k$ peaks to one with $n+1-k$ peaks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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