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

• $1100 \mapsto [1,2]$

• $1010 \mapsto [2,1]$

• $11010011010100 \mapsto [6,5,4,7,2,1,3]$

• $1101110100100010 \mapsto [8,5,3,2,4,6,1,7]$

1.3. Properties

• Under this bijection, reversing the Dyck path corresponds to inverting the 132-avoiding permutation.
• The inverse map is given by sending a 132-avoiding permutation to the reverse of its Rothe diagram.

1.4. Remark

• We should change our definition to match exactly Krattenthaler's.

TBA

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

• $P = (\lambda_1,\lambda_2)$ records the $1$'s in $d_1,d_2,\ldots,d_n$ in $\lambda_1$ and $0$'s in $\lambda_2$, and

• $Q = (\mu_1,\mu_2)$ records the $0$'s in $d_{2n},d_{2n-1},\ldots,d_{n+1}$ in $\mu_1$ and $1$'s in $\mu_2$.

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$:

• $10101010 \mapsto [[1,3],[2,4]],[[1,3],[2,4]] \mapsto 2143$

• $10101100 \mapsto [[1,3],[2,4]],[[1,2],[3,4]] \mapsto 2413$

• $10110010 \mapsto [[1,3,4],[2]],[[1,3,4],[2]] \mapsto 2134$

• $10110100 \mapsto [[1,3,4],[2]],[[1,2,4],[3]] \mapsto 2314$

• $10111000 \mapsto [[1,3,4],[2]],[[1,2,3],[4]] \mapsto 2341$

• $11001010 \mapsto [[1,2],[3,4]],[[1,3],[2,4]] \mapsto 3142$

• $11001100 \mapsto [[1,2],[3,4]],[[1,2],[3,4]] \mapsto 3412$

• $11010010 \mapsto [[1,2,4],[3]],[[1,3,4],[2]] \mapsto 3124$

• $11010100 \mapsto [[1,2,4],[3]],[[1,2,4],[3]] \mapsto 1324$

• $11011000 \mapsto [[1,2,4],[3]],[[1,2,3],[4]] \mapsto 1342$

• $11100010 \mapsto [[1,2,3],[4]],[[1,3,4],[2]] \mapsto 4123$

• $11100100 \mapsto [[1,2,3],[4]],[[1,2,4],[3]] \mapsto 1423$

• $11101000 \mapsto [[1,2,3],[4]],[[1,2,3],[4]] \mapsto 1243$

• $11110000 \mapsto [[1,2,3,4]],[[1,2,3,4]] \mapsto 1234$

3.3. Properties

It was shown in [EP04] that this map sends

• the number of centered tunnels to the number of fixed points,
• the number of right tunnels to the number of exceedences, and
• the semilength plus the height of the middle point to 2 times the length of the longest increasing subsequence.

TBA

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.