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

2 thoughts on “FindStatFact 1: Narayana and area on Dyck paths

  1. Hm, looks like the number on the far RHS is the length of the longest sequence of zeros between two ones, on the LHS, EXCEPT for
    this entry: 10101010 => ([[1,3],[2,4]],[[1,3],[2,4]]) => 2143 => [[.,.],[[.,.],.]] => 11001100 => 2 ….

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s