Combinatorial maps from Dyck paths to permutations

Contents

# 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

*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