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.

2. Dyck paths to 312-avoiding permutations

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.

4. Dyck paths to noncrossing permutation

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.