A list of symmetric statistics - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T18:03:49Z http://mathoverflow.net/feeds/question/101265 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics A list of symmetric statistics Martin Rubey 2012-07-03T23:08:37Z 2012-07-08T14:04:45Z <p>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 <a href="http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics" rel="nofollow">this</a> is the place to do so.</p> <p>Some examples:</p> <ul> <li><p>on Dyck paths: area and bounce, returns to the axis and length of the last descent</p></li> <li><p>on permutations: major index and number of inversions</p></li> <li><p>on perfect matchings, set partitions and permutations: crossings and nestings, the maximal crossing number and the maximal nesting number</p></li> </ul> <p>Maybe it's best to have one family of objects per answer. Edit: originally, I had only <em>joint</em> symmetric distribution in mind. However, lists of equidistributed tuples are also very good to have. Please indicate in your answer what your tuple satisfies! </p> <p>Definitions:</p> <p>Statistics $stat_1,stat_2,\dots,stat_n$ on a set $X$ are <em>equidistributed</em> 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)}.$$</p> <p>A tuple of statistics $(stat_1,stat_2,\dots,stat_n)$ on a set $X$ has a <em>symmetric</em> 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$.</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101267#101267 Answer by Patricia Hersh for A list of symmetric statistics Patricia Hersh 2012-07-03T23:19:32Z 2012-07-05T08:11:45Z <h2><a href="http://www.findstat.org/Permutations/descents-major#Euler-Mahonian_statistics" rel="nofollow">Eulerian statistics</a> on permutations:</h2> <p>A statistic $stat$ is <em>Eulerian</em> 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$.</p> <p>The following statistics are Eulerian:</p> <ul> <li>number of <em>descents</em>, this is the number of positions $i$ for which $\sigma_i>\sigma_{i+1}$,</li> <li>number of <em>exceedances</em>, this is the number of positions $i$ for which $\sigma_i >i$,</li> <li>number of <em>substairs</em>, as defined in M. Skandera, <em>An Eurerian partner for inversions</em>, SLC 46 (2001) [I just made up that name, if someone comes up with something better, let me know.]</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101283#101283 Answer by Christian Stump for A list of symmetric statistics Christian Stump 2012-07-04T04:55:23Z 2012-07-05T08:28:47Z <p>We started writing up combinatorial statistics on <a href="http://www.findstat.org" rel="nofollow">http://www.findstat.org</a> . There you already find some (but not yet many) symmetric statistics. People who are interested and would like to contribute are very welcome!</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101290#101290 Answer by Gjergji Zaimi for A list of symmetric statistics Gjergji Zaimi 2012-07-04T07:01:06Z 2012-07-04T07:01:06Z <p>For parking functions it is <em>conjectured</em> that <strong>dinv</strong> and <strong>area</strong> are symmetric.</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101318#101318 Answer by Ira Gessel for A list of symmetric statistics Ira Gessel 2012-07-04T16:27:05Z 2012-07-04T16:27:05Z <p>The distribution of descents and leaves in forests of rooted trees is symmetric. See <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r8/pdf" rel="nofollow">http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r8/pdf</a>.</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101375#101375 Answer by Christian Stump for A list of symmetric statistics Christian Stump 2012-07-05T08:15:00Z 2012-07-05T11:43:31Z <h2><a href="http://www.findstat.org/Permutations/descents-major#Euler-Mahonian_statistics" rel="nofollow">Mahonian statistics</a> on permutations:</h2> <p>A statistic $stat$ is <em>Mahonian</em> 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$.</p> <p>The following statistics are Mahonian:</p> <ul> <li>major index, this is the sum of positions $i$ for which $\sigma_i>\sigma_{i+1}$,</li> <li><a href="http://www.findstat.org/Permutations/descents-major#A_variation_of_descents_and_major_indices" rel="nofollow">mazor index</a>,</li> <li><a href="http://www.findstat.org/Permutations/descents-major#A_variation_of_descents_and_major_indices" rel="nofollow">mafor index</a>,</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101376#101376 Answer by Christian Stump for A list of symmetric statistics Christian Stump 2012-07-05T08:19:39Z 2012-07-05T08:19:39Z <h2><a href="http://www.findstat.org/Permutations/descents-major#Euler-Mahonian_statistics" rel="nofollow">Euler-Mahonian statistics</a> on permutations:</h2> <p>A pair of statistic $stat_1,stat_2$ is <em>Euler-Mahonian</em> 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$.</p> <p>The following statistics are Euler-Mahonian:</p> <ul> <li>(des,maj),</li> <li>(dez,maz), for a definition click <a href="http://www.findstat.org/Permutations/descents-major#A_variation_of_descents_and_major_indices" rel="nofollow">here</a></li> <li>(sst,inv), as defined in M. Skandera, An Eurerian partner for inversions, SLC 46 (2001),</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101377#101377 Answer by Christian Stump for A list of symmetric statistics Christian Stump 2012-07-05T08:24:57Z 2012-07-08T13:52:30Z <p>Symmetric statistics on permutations:</p> <ul> <li>(maj,inv),</li> <li>(des,dez),</li> <li>(number of crossings, number of nestings)</li> <li>(maximal cardinality of a crossing, maximal cardinality of a nesting)</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101378#101378 Answer by Christian Stump for A list of symmetric statistics Christian Stump 2012-07-05T08:27:41Z 2012-07-08T13:49:17Z <h2>Symmetric statistics on Dyck paths:</h2> <p>The following statistics have a symmetric joint distribution on Dyck paths:</p> <ul> <li>(area,bounce), see <a href="http://www.findstat.org/Dyck%20paths/bounce-dinv" rel="nofollow">here</a></li> <li>(area,dinv), see <a href="http://www.findstat.org/Dyck%20paths/bounce-dinv" rel="nofollow">here</a></li> <li>(number of returns, length of last descent)</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101607#101607 Answer by Stephan Wagner for A list of symmetric statistics Stephan Wagner 2012-07-07T22:54:27Z 2012-07-07T23:01:12Z <p>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 &lt;= k, see</p> <p><a href="http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199608/09)9:1/2%3C79::AID-RSA5%3E3.0.CO;2-8/abstract" rel="nofollow">here</a></p> <p>and</p> <p><a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r137" rel="nofollow">here</a>.</p> <p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0195669808001649" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101669#101669 Answer by Martin Rubey for A list of symmetric statistics Martin Rubey 2012-07-08T13:55:50Z 2012-07-08T13:55:50Z <p>Symmetric statistics on set partitions:</p> <ul> <li>(number of crossings, number of nestings)</li> <li>(maximal cardinality of a crossing, maximal cardinality of a nesting)</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101670#101670 Answer by Martin Rubey for A list of symmetric statistics Martin Rubey 2012-07-08T13:56:28Z 2012-07-08T13:56:28Z <p>Symmetric statistics on perfect matchings:</p> <ul> <li>(number of crossings, number of nestings)</li> <li>(maximal cardinality of a crossing, maximal cardinality of a nesting)</li> </ul>