FindStatFact 3: Spin and dinv adjustment on partition

This FindStatFact is a simple observation we made a few weeks ago, which we think shows one strength of the FindStat project very well:

The paper Loehr, N. A., Warrington, G. S. Nested quantum Dyck paths and \nabla(s_\lambda) [MathSciNet, arXiv] defines the two statistics spin and dinv adjustment on integer partitions. These are also discussed in an appendix of the book Haglund, J. The q,t-Catalan numbers and the space of diagonal harmonics [MathSciNet]. We refer to these two references for the definitions. These can as well be found at www.FindStat.org/St000319 and at www.FindStat.org/St000320, respectively.

The Ferrers shape of an integer partition \lambda can be decomposed into border strips. For 0 \leq j < \lambda_1 let n_j be the length of the border strip starting at (\lambda_1-j,0).

  • The spin of \lambda is defined to be the total number of crossings of these border strips with the vertical lines in the Ferrers shape.
  • The dinv adjustment is defined as \sum (\lambda_1-1-j) where the sum ranges over all indices j such that n_j > 0.

When we added them to FindStat recently, the search engine told us that these appear to coincide. And indeed, it is obvious that the border strip starting at (\lambda_1-j,0) crosses the vertical lines in the Ferrers shape exactly n_j-1-j times.

Multiple people have looked at these statistics defined on the same page in a well-received paper. But no one had a reason to check whether or not these statistics coincide, so this obvious coincidence stayed undiscovered since 2007.

FindStatFact 2: Weak exceedances on Dyck paths

Who knows of a way to describe the number of weak exceedances of a permutation in terms of Dyck paths?

Go to http://www.findstat.org/St000213, click on search for statistic, and you will find out that

  • applying the inverse of the first fundamental transformation $\latex \phi$ given by sending the maximal entries in the cycles of a permutation \pi to the left-to-right maxima of \phi(\pi), then
  • sending $\phi(\pi)$ to its increasing tree T(\phi(\pi)), and finally
  • sending T(\phi(\pi)) to the Dyck path D by identifying an up step in D with a left subtree in T(\phi(\pi)), and a down step inĀ D with a right subtree in T(\phi(\pi)),

will send the number of weak exceedances of \pi to the number of peaks of a Dyck path.

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

FindStatFact 0: Introduction

We believe that the FindStat database at www.findstat.org contains many interesting connections – most of which are probably known, but others are yet to be found and proven.

We created this blog to post statistics that appear to be connected through combinatorial maps between various combinatorial collections, and

  • which we think are worth sharing, and
  • for which we would like to ask the community to come up with an explanation.

Currently, we plan to only post the plain observations from the database — FindStatFact1 will contain an example of how to play with the database to find such connections. We only post connections that we find surprising, seeking for a (more or less) detailed explanation or a reference in the literature.

If it turns out that we find multiple interesting and unexpected connections (previously known and unknown), we plan to publish these connections. Before doing so, we will ask anyone who contributed a solution or reference, for his/her agreement for including it with a corresponding acknowledgement in the publication. Obviously, this will only happen once we have collected enough connections, most likely not within the first year of this blog.