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:

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?
  • Was this map studied before?

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
Advertisements