- FindStat

edit this statistic or download as text // json

Identifier

St000042: Perfect matchings ⟶ ℤ

Values

[(1,2)] => 0

[(1,2),(3,4)] => 0

[(1,3),(2,4)] => 1

[(1,4),(2,3)] => 0

[(1,2),(3,4),(5,6)] => 0

[(1,3),(2,4),(5,6)] => 1

[(1,4),(2,3),(5,6)] => 0

[(1,5),(2,3),(4,6)] => 1

[(1,6),(2,3),(4,5)] => 0

[(1,6),(2,4),(3,5)] => 1

[(1,5),(2,4),(3,6)] => 2

[(1,4),(2,5),(3,6)] => 3

[(1,3),(2,5),(4,6)] => 2

[(1,2),(3,5),(4,6)] => 1

[(1,2),(3,6),(4,5)] => 0

[(1,3),(2,6),(4,5)] => 1

[(1,4),(2,6),(3,5)] => 2

[(1,5),(2,6),(3,4)] => 1

[(1,6),(2,5),(3,4)] => 0

[(1,2),(3,4),(5,6),(7,8)] => 0

[(1,3),(2,4),(5,6),(7,8)] => 1

[(1,4),(2,3),(5,6),(7,8)] => 0

[(1,5),(2,3),(4,6),(7,8)] => 1

[(1,6),(2,3),(4,5),(7,8)] => 0

[(1,7),(2,3),(4,5),(6,8)] => 1

[(1,8),(2,3),(4,5),(6,7)] => 0

[(1,8),(2,4),(3,5),(6,7)] => 1

[(1,7),(2,4),(3,5),(6,8)] => 2

[(1,6),(2,4),(3,5),(7,8)] => 1

[(1,5),(2,4),(3,6),(7,8)] => 2

[(1,4),(2,5),(3,6),(7,8)] => 3

[(1,3),(2,5),(4,6),(7,8)] => 2

[(1,2),(3,5),(4,6),(7,8)] => 1

[(1,2),(3,6),(4,5),(7,8)] => 0

[(1,3),(2,6),(4,5),(7,8)] => 1

[(1,4),(2,6),(3,5),(7,8)] => 2

[(1,5),(2,6),(3,4),(7,8)] => 1

[(1,6),(2,5),(3,4),(7,8)] => 0

[(1,7),(2,5),(3,4),(6,8)] => 1

[(1,8),(2,5),(3,4),(6,7)] => 0

[(1,8),(2,6),(3,4),(5,7)] => 1

[(1,7),(2,6),(3,4),(5,8)] => 2

[(1,6),(2,7),(3,4),(5,8)] => 3

[(1,5),(2,7),(3,4),(6,8)] => 2

[(1,4),(2,7),(3,5),(6,8)] => 3

[(1,3),(2,7),(4,5),(6,8)] => 2

[(1,2),(3,7),(4,5),(6,8)] => 1

[(1,2),(3,8),(4,5),(6,7)] => 0

[(1,3),(2,8),(4,5),(6,7)] => 1

[(1,4),(2,8),(3,5),(6,7)] => 2

[(1,5),(2,8),(3,4),(6,7)] => 1

[(1,6),(2,8),(3,4),(5,7)] => 2

[(1,7),(2,8),(3,4),(5,6)] => 1

[(1,8),(2,7),(3,4),(5,6)] => 0

[(1,8),(2,7),(3,5),(4,6)] => 1

[(1,7),(2,8),(3,5),(4,6)] => 2

[(1,6),(2,8),(3,5),(4,7)] => 3

[(1,5),(2,8),(3,6),(4,7)] => 4

[(1,4),(2,8),(3,6),(5,7)] => 3

[(1,3),(2,8),(4,6),(5,7)] => 2

[(1,2),(3,8),(4,6),(5,7)] => 1

[(1,2),(3,7),(4,6),(5,8)] => 2

[(1,3),(2,7),(4,6),(5,8)] => 3

[(1,4),(2,7),(3,6),(5,8)] => 4

[(1,5),(2,7),(3,6),(4,8)] => 5

[(1,6),(2,7),(3,5),(4,8)] => 4

[(1,7),(2,6),(3,5),(4,8)] => 3

[(1,8),(2,6),(3,5),(4,7)] => 2

[(1,8),(2,5),(3,6),(4,7)] => 3

[(1,7),(2,5),(3,6),(4,8)] => 4

[(1,6),(2,5),(3,7),(4,8)] => 5

[(1,5),(2,6),(3,7),(4,8)] => 6

[(1,4),(2,6),(3,7),(5,8)] => 5

[(1,3),(2,6),(4,7),(5,8)] => 4

[(1,2),(3,6),(4,7),(5,8)] => 3

[(1,2),(3,5),(4,7),(6,8)] => 2

[(1,3),(2,5),(4,7),(6,8)] => 3

[(1,4),(2,5),(3,7),(6,8)] => 4

[(1,5),(2,4),(3,7),(6,8)] => 3

[(1,6),(2,4),(3,7),(5,8)] => 4

[(1,7),(2,4),(3,6),(5,8)] => 3

[(1,8),(2,4),(3,6),(5,7)] => 2

[(1,8),(2,3),(4,6),(5,7)] => 1

[(1,7),(2,3),(4,6),(5,8)] => 2

[(1,6),(2,3),(4,7),(5,8)] => 3

[(1,5),(2,3),(4,7),(6,8)] => 2

[(1,4),(2,3),(5,7),(6,8)] => 1

[(1,3),(2,4),(5,7),(6,8)] => 2

[(1,2),(3,4),(5,7),(6,8)] => 1

[(1,2),(3,4),(5,8),(6,7)] => 0

[(1,3),(2,4),(5,8),(6,7)] => 1

[(1,4),(2,3),(5,8),(6,7)] => 0

[(1,5),(2,3),(4,8),(6,7)] => 1

[(1,6),(2,3),(4,8),(5,7)] => 2

[(1,7),(2,3),(4,8),(5,6)] => 1

[(1,8),(2,3),(4,7),(5,6)] => 0

[(1,8),(2,4),(3,7),(5,6)] => 1

[(1,7),(2,4),(3,8),(5,6)] => 2

[(1,6),(2,4),(3,8),(5,7)] => 3

[(1,5),(2,4),(3,8),(6,7)] => 2

[(1,4),(2,5),(3,8),(6,7)] => 3

>>> Load all 1386 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of crossings of a perfect matching.
This is the number of pairs of edges $((a,b),(c,d))$ such that $a\le c\le b\le d$, i.e., the edges $(a,b)$ and $(c,d)$ cross when drawing the perfect matching as a chord diagram.
The generating function for perfect matchings $M$ of $\{1,\dots,2n\}$ according to the number of crossings $\textrm{cr}(M)$ is given by the Touchard-Riordan formula ([2], [4], a bijective proof is given in [7]):
$$ \sum_{M} q^{\textrm{cr}(M)} = \frac{1}{(1-q)^n} \sum_{k=0}^n\left(\binom{2n}{n-k}-\binom{2n}{n-k-1}\right)(-1)^k q^{\binom{k+1}{2}} $$

References

[1] de Médicis, A., Viennot, X. G. Moments des $q$-polynômes de Laguerre et la bijection de Foata-Zeilberger MathSciNet:1288802
[2] Riordan, J. The distribution of crossings of chords joining pairs of $2n$ points on a circle MathSciNet:0366686
[3] Simion, R., Stanton, D. Octabasic Laguerre polynomials and permutation statistics MathSciNet:1418763
[4] Touchard, J. Sur un problème de configurations et sur les fractions continues MathSciNet:0046325
[5] Josuat-Vergès, M., Rubey, M. Crossings, Motzkin paths and moments MathSciNet:2819649
[6] Triangle read by rows: T(n,k) gives number of ways of arranging n chords on a circle with k simple intersections (i.e. no intersections with 3 or more chords) - positive values only. OEIS:A067311
[7] Penaud, J.-G. Une preuve bijective d'une formule de Touchard-Riordan MathSciNet:1336847

Code

def statistic(x):
    return len(x.crossings())

Created

Mar 01, 2013 at 02:53 by Alejandro Morales

Updated

Dec 25, 2017 at 17:42 by Martin Rubey