*****************************************************************************
* www.FindStat.org - The Combinatorial Statistic Finder *
* *
* Copyright (C) 2019 The FindStatCrew <info@findstat.org> *
* *
* 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