# FindStatFact 1: Narayana and area on Dyck paths

This first FindStatFact is about the connection of two classes of statistics on Dyck paths, namely statistics that are Narayana distributed and those that have the same distribution as the area statistic. Some quick background, which is taken from www.findstat.org/DyckPaths:

• A Dyck path of size $n$ is a a lattice path in $\mathbb{N}\times\mathbb{N}$ from $(0,0)$ to $(n,n)$ consisting of $n$. They are counted by the $n$-th Catalan number $Cat_n = \frac{1}{n}\binom{2n}{n-1}$.
• The Narayana number $Nar_{n,k} = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$ then counts Dyck paths with exactly $k$ peaks (www.findstat.org/St000015/), or Dyck paths with exactly $k$ left tunnels (www.findstat.org/St000120/), or various other refinements of Dyck paths.
• The area of a Dyck path $D$ is given by the number of complete boxes below $D$ and completely above the diagonal $x=y$ (www.findstat.org/St000012/). Other statistics that are equidistributed with the area are for example the bounce and the dinv statistics (www.findstat.org/St000005/ and www.findstat.org/St000006/).

If you now search the FindStat database for the number of left tunnels by clicking “run the finder on the first 200 of these values” on this statistic at www.findstat.org/St000120/, you will find that starting with a Dyck path $D$,

• turning $D$ into a $312$-avoiding permutation $\pi$ (description),
• Let $D = d_1,d_2,\ldots,d_{2n}$. 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$. $\pi$ is then the unique permutation RSK-corresponding to $(P,Q)$. Observe that it is $321$-avoiding since $P$ and $P$ have at most $2$ rows.
• turning $\pi$ into a binary search tree $T$ (description), and finally
• The binary tree $T$ is obtained from $\pi$ by inserting the one-line notation of $\pi$ into an empty binary tree.
• turning $T$ again into a Dyck path $D'$ (description),
• Map $T$ into a Dyck path $D'$ recursively by sending $T$ to $1$ followed by the left subtree of $T$ followed by $0$ followed by the right subtree of $T$.

maps the number of left tunnels of $D$ to the area of $D'$. The first map to $321$-avoiding permutations is known to preserve several statistics including the various tunnel statistics, the more surprising part is that magically, the area statistics comes into play…

We find it quite surprising that such a map naturally exists!

• Did YOU know of such a map?
• Is there a direct/easy description of this map?

Below, we list all Dyck paths of size $2$, $3$, and $4$, together with their images:

1010     => ([[1],[2]],[[1],[2]])         => 21   => [[.,.],.]         => 1100     => 1
1100     => ([[1,2]],[[1,2]])             => 12   => [.,[.,.]]         => 1010     => 0
101010   => ([[1,3],[2]],[[1,3],[2]])     => 213  => [[.,.],[.,.]]     => 110010   => 1
101100   => ([[1,3],[2]],[[1,2],[3]])     => 231  => [[.,.],[.,.]]     => 110010   => 1
110010   => ([[1,2],[3]],[[1,3],[2]])     => 312  => [[.,[.,.]],.]     => 110100   => 2
110100   => ([[1,2],[3]],[[1,2],[3]])     => 132  => [.,[[.,.],.]]     => 101100   => 1
111000   => ([[1,2,3]],[[1,2,3]])         => 123  => [.,[.,[.,.]]]     => 101010   => 0
10101010 => ([[1,3],[2,4]],[[1,3],[2,4]]) => 2143 => [[.,.],[[.,.],.]] => 11001100 => 2
10101100 => ([[1,3],[2,4]],[[1,2],[3,4]]) => 2413 => [[.,.],[[.,.],.]] => 11001100 => 2
10110010 => ([[1,3,4],[2]],[[1,3,4],[2]]) => 2134 => [[.,.],[.,[.,.]]] => 11001010 => 1
10110100 => ([[1,3,4],[2]],[[1,2,4],[3]]) => 2314 => [[.,.],[.,[.,.]]] => 11001010 => 1
10111000 => ([[1,3,4],[2]],[[1,2,3],[4]]) => 2341 => [[.,.],[.,[.,.]]] => 11001010 => 1
11001010 => ([[1,2],[3,4]],[[1,3],[2,4]]) => 3142 => [[.,[.,.]],[.,.]] => 11010010 => 2
11001100 => ([[1,2],[3,4]],[[1,2],[3,4]]) => 3412 => [[.,[.,.]],[.,.]] => 11010010 => 2
11010010 => ([[1,2,4],[3]],[[1,3,4],[2]]) => 3124 => [[.,[.,.]],[.,.]] => 11010010 => 2
11010100 => ([[1,2,4],[3]],[[1,2,4],[3]]) => 1324 => [.,[[.,.],[.,.]]] => 10110010 => 1
11011000 => ([[1,2,4],[3]],[[1,2,3],[4]]) => 1342 => [.,[[.,.],[.,.]]] => 10110010 => 1
11100010 => ([[1,2,3],[4]],[[1,3,4],[2]]) => 4123 => [[.,[.,[.,.]]],.] => 11010100 => 3
11100100 => ([[1,2,3],[4]],[[1,2,4],[3]]) => 1423 => [.,[[.,[.,.]],.]] => 10110100 => 2
11101000 => ([[1,2,3],[4]],[[1,2,3],[4]]) => 1243 => [.,[.,[[.,.],.]]] => 10101100 => 1
11110000 => ([[1,2,3,4]],[[1,2,3,4]])     => 1234 => [.,[.,[.,[.,.]]]] => 10101010 => 0