***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St000044 ----------------------------------------------------------------------------- Collection: Perfect matchings ----------------------------------------------------------------------------- Description: The number of vertices of the unicellular map given by a perfect matching. If the perfect matching of $2n$ elements is viewed as a fixed point-free involution $\epsilon$ This statistic is counting the number of cycles of the permutation $\gamma \circ \epsilon$ where $\gamma$ is the long cycle $(1,2,3,\ldots,2n)$. '''Example''' The perfect matching $[(1,3),(2,4)]$ corresponds to the permutation in $S_4$ with disjoint cycle decomposition $(1,3)(2,4)$. Then the permutation $(1,2,3,4)\circ (1,3)(2,4) = (1,4,3,2)$ has only one cycle. Let $\epsilon_v(n)$ is the number of matchings of $2n$ such that yield $v$ cycles in the process described above. Harer and Zagier [1] gave the following expression for the generating series of the numbers $\epsilon_v(n)$. $$ \sum_{v=1}^{n+1} \epsilon_{v}(n) N^v = (2n-1)!! \sum_{k\geq 0}^n \binom{N}{k+1}\binom{n}{k}2^k. $$ ----------------------------------------------------------------------------- References: [1] Harer, J., Zagier, D. The Euler characteristic of the moduli space of curves [[MathSciNet:0848681]] [2] Lando, S. K., Zvonkin, A. K. Graphs on surfaces and their applications [[MathSciNet:2036721]] ----------------------------------------------------------------------------- Code: def statistic(pm): p = Permutation(pm.to_permutation())*Permutation(list(range(2,pm.size()+1)) + [1,]) return len(p.cycle_type()) ----------------------------------------------------------------------------- Statistic values: [(1,2)] => 2 [(1,2),(3,4)] => 3 [(1,3),(2,4)] => 1 [(1,4),(2,3)] => 3 [(1,2),(3,4),(5,6)] => 4 [(1,3),(2,4),(5,6)] => 2 [(1,4),(2,3),(5,6)] => 4 [(1,5),(2,3),(4,6)] => 2 [(1,6),(2,3),(4,5)] => 4 [(1,6),(2,4),(3,5)] => 2 [(1,5),(2,4),(3,6)] => 2 [(1,4),(2,5),(3,6)] => 2 [(1,3),(2,5),(4,6)] => 2 [(1,2),(3,5),(4,6)] => 2 [(1,2),(3,6),(4,5)] => 4 [(1,3),(2,6),(4,5)] => 2 [(1,4),(2,6),(3,5)] => 2 [(1,5),(2,6),(3,4)] => 2 [(1,6),(2,5),(3,4)] => 4 [(1,2),(3,4),(5,6),(7,8)] => 5 [(1,3),(2,4),(5,6),(7,8)] => 3 [(1,4),(2,3),(5,6),(7,8)] => 5 [(1,5),(2,3),(4,6),(7,8)] => 3 [(1,6),(2,3),(4,5),(7,8)] => 5 [(1,7),(2,3),(4,5),(6,8)] => 3 [(1,8),(2,3),(4,5),(6,7)] => 5 [(1,8),(2,4),(3,5),(6,7)] => 3 [(1,7),(2,4),(3,5),(6,8)] => 1 [(1,6),(2,4),(3,5),(7,8)] => 3 [(1,5),(2,4),(3,6),(7,8)] => 3 [(1,4),(2,5),(3,6),(7,8)] => 3 [(1,3),(2,5),(4,6),(7,8)] => 3 [(1,2),(3,5),(4,6),(7,8)] => 3 [(1,2),(3,6),(4,5),(7,8)] => 5 [(1,3),(2,6),(4,5),(7,8)] => 3 [(1,4),(2,6),(3,5),(7,8)] => 3 [(1,5),(2,6),(3,4),(7,8)] => 3 [(1,6),(2,5),(3,4),(7,8)] => 5 [(1,7),(2,5),(3,4),(6,8)] => 3 [(1,8),(2,5),(3,4),(6,7)] => 5 [(1,8),(2,6),(3,4),(5,7)] => 3 [(1,7),(2,6),(3,4),(5,8)] => 3 [(1,6),(2,7),(3,4),(5,8)] => 3 [(1,5),(2,7),(3,4),(6,8)] => 3 [(1,4),(2,7),(3,5),(6,8)] => 1 [(1,3),(2,7),(4,5),(6,8)] => 3 [(1,2),(3,7),(4,5),(6,8)] => 3 [(1,2),(3,8),(4,5),(6,7)] => 5 [(1,3),(2,8),(4,5),(6,7)] => 3 [(1,4),(2,8),(3,5),(6,7)] => 3 [(1,5),(2,8),(3,4),(6,7)] => 3 [(1,6),(2,8),(3,4),(5,7)] => 3 [(1,7),(2,8),(3,4),(5,6)] => 3 [(1,8),(2,7),(3,4),(5,6)] => 5 [(1,8),(2,7),(3,5),(4,6)] => 3 [(1,7),(2,8),(3,5),(4,6)] => 1 [(1,6),(2,8),(3,5),(4,7)] => 1 [(1,5),(2,8),(3,6),(4,7)] => 1 [(1,4),(2,8),(3,6),(5,7)] => 1 [(1,3),(2,8),(4,6),(5,7)] => 1 [(1,2),(3,8),(4,6),(5,7)] => 3 [(1,2),(3,7),(4,6),(5,8)] => 3 [(1,3),(2,7),(4,6),(5,8)] => 1 [(1,4),(2,7),(3,6),(5,8)] => 3 [(1,5),(2,7),(3,6),(4,8)] => 3 [(1,6),(2,7),(3,5),(4,8)] => 1 [(1,7),(2,6),(3,5),(4,8)] => 3 [(1,8),(2,6),(3,5),(4,7)] => 3 [(1,8),(2,5),(3,6),(4,7)] => 3 [(1,7),(2,5),(3,6),(4,8)] => 1 [(1,6),(2,5),(3,7),(4,8)] => 3 [(1,5),(2,6),(3,7),(4,8)] => 1 [(1,4),(2,6),(3,7),(5,8)] => 3 [(1,3),(2,6),(4,7),(5,8)] => 1 [(1,2),(3,6),(4,7),(5,8)] => 3 [(1,2),(3,5),(4,7),(6,8)] => 3 [(1,3),(2,5),(4,7),(6,8)] => 1 [(1,4),(2,5),(3,7),(6,8)] => 1 [(1,5),(2,4),(3,7),(6,8)] => 3 [(1,6),(2,4),(3,7),(5,8)] => 1 [(1,7),(2,4),(3,6),(5,8)] => 1 [(1,8),(2,4),(3,6),(5,7)] => 3 [(1,8),(2,3),(4,6),(5,7)] => 3 [(1,7),(2,3),(4,6),(5,8)] => 3 [(1,6),(2,3),(4,7),(5,8)] => 3 [(1,5),(2,3),(4,7),(6,8)] => 3 [(1,4),(2,3),(5,7),(6,8)] => 3 [(1,3),(2,4),(5,7),(6,8)] => 1 [(1,2),(3,4),(5,7),(6,8)] => 3 [(1,2),(3,4),(5,8),(6,7)] => 5 [(1,3),(2,4),(5,8),(6,7)] => 3 [(1,4),(2,3),(5,8),(6,7)] => 5 [(1,5),(2,3),(4,8),(6,7)] => 3 [(1,6),(2,3),(4,8),(5,7)] => 3 [(1,7),(2,3),(4,8),(5,6)] => 3 [(1,8),(2,3),(4,7),(5,6)] => 5 [(1,8),(2,4),(3,7),(5,6)] => 3 [(1,7),(2,4),(3,8),(5,6)] => 3 [(1,6),(2,4),(3,8),(5,7)] => 1 [(1,5),(2,4),(3,8),(6,7)] => 3 [(1,4),(2,5),(3,8),(6,7)] => 3 [(1,3),(2,5),(4,8),(6,7)] => 3 [(1,2),(3,5),(4,8),(6,7)] => 3 [(1,2),(3,6),(4,8),(5,7)] => 3 [(1,3),(2,6),(4,8),(5,7)] => 3 [(1,4),(2,6),(3,8),(5,7)] => 1 [(1,5),(2,6),(3,8),(4,7)] => 3 [(1,6),(2,5),(3,8),(4,7)] => 3 [(1,7),(2,5),(3,8),(4,6)] => 1 [(1,8),(2,5),(3,7),(4,6)] => 3 [(1,8),(2,6),(3,7),(4,5)] => 3 [(1,7),(2,6),(3,8),(4,5)] => 3 [(1,6),(2,7),(3,8),(4,5)] => 3 [(1,5),(2,7),(3,8),(4,6)] => 1 [(1,4),(2,7),(3,8),(5,6)] => 3 [(1,3),(2,7),(4,8),(5,6)] => 3 [(1,2),(3,7),(4,8),(5,6)] => 3 [(1,2),(3,8),(4,7),(5,6)] => 5 [(1,3),(2,8),(4,7),(5,6)] => 3 [(1,4),(2,8),(3,7),(5,6)] => 3 [(1,5),(2,8),(3,7),(4,6)] => 3 [(1,6),(2,8),(3,7),(4,5)] => 3 [(1,7),(2,8),(3,6),(4,5)] => 3 [(1,8),(2,7),(3,6),(4,5)] => 5 ----------------------------------------------------------------------------- Created: Mar 01, 2013 at 03:31 by Alejandro Morales ----------------------------------------------------------------------------- Last Updated: Nov 12, 2017 at 17:34 by Martin Rubey