5
$\begingroup$

A dyck path with $2n$ steps is a lattice path in $\mathbb{Z}^2$ starting at the origin $(0,0)$ and going to $(2n,0)$ using the steps $(1,1)$ and $(1,-1)$ without going below the x-axis. What are some natural bijections between the set of such dyck path with $2n$ steps? For example of course the identity is such a bijection but also the map sending a given dyck path to the same dyck path but viewing $(2n,0)$ as the origin is a bijection. What are some other examples of natural(or easy to write down) bijections? Note that dyck path correspond to ballot sequences, which are sequences of length $2n$ consisting of 1(corresponding to (1,1)) and -1(corresponding to (1,-1)) with the property that in this sequence the partial sums are never negative. So maybe its sometimes easier to write down such bijections explicitly using ballot sequences. Note that the number of dyck paths is the Catalan number.

$\endgroup$
4
$\begingroup$

There are tons of such bijections. Here are a few that came to my mind, and maybe I'll make some updates later. Or maybe it should be a community wiki if this hasn't been asked before.

  1. Since Dyck paths are in a natural 1-1 correspondence with binary trees, this bijection corresponds to recursively switching the left and right subtrees of every node: $$ \varphi(\emptyset)=\emptyset, \qquad \varphi(uD_1dD_2)=u\varphi(D_2)d\varphi(D_1), $$ where $D_1$ and $D_2$ are arbitrary Dyck paths.

  2. Every Dyck path $D$ with unit steps $u$ (up) and $d$ (down) can be uniquely decomposed into a sequence of raised Dyck paths: $$ D=(uD_1d)(uD_2d)\dots(uD_kd). $$ This can be mapped bijectively onto $$ D'=(D_1u)(D_2u)\dots(D_ku)\underbrace{d\dots d}_{k}, $$ so that the $i$th "special" $u$ (the step following $D_i$) from the left matches the $i$th (special) $d$ from the right for $i=1,\dots,k$. Another way to find the position of the $i$th $u$ is to note that this is the last time the path $D'$ is at height $i$ until the final block of $d$'s. Alternatively, this bijection can be given recursively as: $$ \psi(\emptyset)=\emptyset, \qquad \psi(uD_1dD_2)=D_1u\psi(D_2)d. $$

  3. A $321$-avoiding permutation is uniquely determined by the positions and values of its left-to-right maxima as well as by the positions and values of its right-to-left minima. The LR-maxima correspond to a Dyck path on or above the main diagonal, and the RL-minima correspond to a Dyck path on or below the main diagonal. So this determines another bijection between Dyck paths. (E.g. if $\pi=24153$, then $D_{LRmax}=uuduuddudd$ and $D_{RLmin}=uuudduuddd$.)

  4. Elizalde-Deutsch bijection

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