Combinatorial maps from Dyck paths to permutations

1. Dyck paths to 132-avoiding permutations

1.1. Definition

Let $\{ i_1,\ldots,i_n \}$ be the set of heights at the starting points of the up steps of the Dyck path $D$ of semilength $n$. For example, the Dyck path $D$ given by the word $1101110100100010$, this set is given by $\{ 0,1,1,2,3,3,2,0 \}$. The image of $D$ under this bijection is then the permutation $\pi \in \mathcal{S}_n$ such that to the right of $\pi_i$ there are $i_{n+1-i}$ many letters bigger than $\pi_i$ in the one-line notation of $\pi$. In our example, this is saying that there are $i_n = 0$ many letters bigger than $\pi_1$, thus $\pi_1 = 8$. Next, there are $2$ letters to its right bigger than $pi_2$, thus $\pi_2 = 5$. Going on this way, we get that the image of $D$ is $\pi = [8,5,3,2,4,6,1,7]$.

This map was, with a slight change of conventions, described by C. Krattenthaler in [Kra01].

1.2. Examples

1.3. Properties

1.4. Remark

2. Dyck paths to 312-avoiding permutations


3. Dyck paths to 321-avoiding permutations

This bijection was defined in [Knu73] and as well studied in [EP04].

3.1. Definition

Let $D = d_1,\ldots,d_{2n} \in \mathcal{D}_n$ be a Dyck path of size $n$.

Define a pair $(P,Q)$ of standard Young tableaux of the same shape with at most two rows, such that

Then, the $321$-avoiding permutation $\sigma \in \mathcal{S}_n$ is given by the unique permutation $RSK$-corresponding to $(P,Q)$.

3.2. Examples

The map applied to all Dyck paths of size $4$:

3.3. Properties

It was shown in [EP04] that this map sends

4. Dyck paths to noncrossing permutation


5. References

[EP04]   S. Elizalde and I. Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105(2) (2004).

[Knu73]   D. Knuth, The art of computer programming III, Addison-Wesley, Reading, MA (1973).

[Kra01]   C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), pp. 510-530.

6. Sage examples