3
$\begingroup$

I would like to have a list of pairs (or tuples) of combinatorial statistics that are (known or conjectured) to have symmetric distribution. Ideally, something like this has already been compiled, otherwise, maybe this is the place to do so.

Some examples:

  • on Dyck paths: area and bounce, returns to the axis and length of the last descent

  • on permutations: major index and number of inversions

  • on perfect matchings, set partitions and permutations: crossings and nestings, the maximal crossing number and the maximal nesting number

Maybe it's best to have one family of objects per answer. Edit: originally, I had only joint symmetric distribution in mind. However, lists of equidistributed tuples are also very good to have. Please indicate in your answer what your tuple satisfies!

Definitions:

Statistics $stat_1,stat_2,\dots,stat_n$ on a set $X$ are equidistributed if $$\sum_{x\in X}q^{stat_1(x)} = \sum_{x\in X}q^{stat_2(x)} = \dots \sum_{x\in X}q^{stat_n(x)}.$$

A tuple of statistics $(stat_1,stat_2,\dots,stat_n)$ on a set $X$ has a symmetric distribution if its generating function $$F_{stat_1,stat_2}(q,t) := \sum_{x\in X}x_1^{stat_1(x)}x_2^{stat_2(x)}\dots x_n^{stat_n(x)}$$ is symmetric in $x_1,x_2,\dots,x_n$.

Improve this question
$\endgroup$

11 Answers 11

Reset to default
6
$\begingroup$

We started writing up combinatorial statistics on http://www.findstat.org . There you already find some (but not yet many) symmetric statistics. People who are interested and would like to contribute are very welcome!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Many thanks for the invitation! And yes, that's actually one intention of this question... I have one request with your answer: Although a list of equidistributed statistics is also very very nice, I am most interested in joint symmetric distributions. (I will clarify this in my question) Could you clarify this in your answer for later use. (eg. as far as I know, area and bounce are symmetric, but eg. area and dinv are not.) Symmetric distribution implies equidistribution of course... $\endgroup$
    – Martin Rubey
    Commented Jul 4, 2012 at 5:44
  • $\begingroup$ Christian, would it be OK for you to split this answer in three? (One for findstat, one for permutations - merged with Patricia's, and one for Dyck paths.) $\endgroup$
    – Martin Rubey
    Commented Jul 4, 2012 at 5:52
  • 1
    $\begingroup$ Ooops, area and dinv is symmetric, bounce and dinv is not, sorry. $\endgroup$
    – Martin Rubey
    Commented Jul 4, 2012 at 6:00
2
$\begingroup$

For parking functions it is conjectured that dinv and area are symmetric.

Improve this answer
$\endgroup$
1
$\begingroup$

The distribution of descents and leaves in forests of rooted trees is symmetric. See http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r8/pdf.

Improve this answer
$\endgroup$
1
$\begingroup$

Eulerian statistics on permutations:

A statistic $stat$ is Eulerian if it is equidistributed with the number of descents, i.e., $$\sum_{\sigma\in S_n}q^{stat(\sigma)} = \sum_{\sigma\in S_n} q^{des(\sigma )}$$ where $S_n$ denotes the group of permutations of $1,\dots ,n$.

The following statistics are Eulerian:

  • number of descents, this is the number of positions $i$ for which $\sigma_i>\sigma_{i+1}$,
  • number of exceedances, this is the number of positions $i$ for which $\sigma_i >i$,
  • number of substairs, as defined in M. Skandera, An Eurerian partner for inversions, SLC 46 (2001) [I just made up that name, if someone comes up with something better, let me know.]
Improve this answer
$\endgroup$
1
$\begingroup$

In increasing trees, the depth of the k-th node is equidistributed with the number of edges between two nodes whose labels are consecutive integers <= k, see

here

and

here.

Another, rather curious example: the number of leaves in plane trees, modulo 2, is equidistributed with the internal path length (sum of all distances to the root) modulo 2, see here.

Improve this answer
$\endgroup$
1
$\begingroup$

Symmetric statistics on permutations:

  • (maj,inv),
  • (des,dez),
  • (number of crossings, number of nestings)
  • (maximal cardinality of a crossing, maximal cardinality of a nesting)
Improve this answer
$\endgroup$
0
$\begingroup$

Euler-Mahonian statistics on permutations:

A pair of statistic $stat_1,stat_2$ is Euler-Mahonian if it is equidistributed with the bistatistic given by the number of descents and the major index, i.e., $$\sum_{\sigma\in S_n}q^{stat_1(\sigma)}t^{stat_2(\sigma)} = \sum_{\sigma\in S_n} q^{des(\sigma)}t^{maj(\sigma)}$$ where $S_n$ denotes the group of permutations of $1,\dots ,n$.

The following statistics are Euler-Mahonian:

  • (des,maj),
  • (dez,maz), for a definition click here
  • (sst,inv), as defined in M. Skandera, An Eurerian partner for inversions, SLC 46 (2001),
Improve this answer
$\endgroup$
0
$\begingroup$

Mahonian statistics on permutations:

A statistic $stat$ is Mahonian if it is equidistributed with the major index, i.e., $$\sum_{\sigma\in S_n}q^{stat(\sigma)} = \sum_{\sigma\in S_n} q^{maj(\sigma )}$$ where $S_n$ denotes the group of permutations of $1,\dots ,n$.

The following statistics are Mahonian:

Improve this answer
$\endgroup$
0
$\begingroup$

Symmetric statistics on Dyck paths:

The following statistics have a symmetric joint distribution on Dyck paths:

  • (area,bounce), see here
  • (area,dinv), see here
  • (number of returns, length of last descent)
Improve this answer
$\endgroup$
0
$\begingroup$

Symmetric statistics on set partitions:

  • (number of crossings, number of nestings)
  • (maximal cardinality of a crossing, maximal cardinality of a nesting)
Improve this answer
$\endgroup$
0
$\begingroup$

Symmetric statistics on perfect matchings:

  • (number of crossings, number of nestings)
  • (maximal cardinality of a crossing, maximal cardinality of a nesting)
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .