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
[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