Take the 2-minute tour ×

Given a vertex set $\{1,\ldots,n\}$, two edges $\{i,j\}$ and $\{k,\ell\}$ are crossing iff $i\lt k\lt j \lt \ell$.

I'm interested in the number of 1-factors in the complete graph over $2n$ vertices, such that each edge of the 1-factor crosses some other edge of the 1-factor.

Does anyone have any ideas about this?

Edit: This is closely related enumerating circle graphs.

Thank you

share|improve this question
You might try to search for papers about non-crossing matchings for geometric graphs. These latter being graphs in the plane where the edges are all straight line segments. –  Joseph Malkevitch Sep 12 '11 at 18:46
add comment

1 Answer

up vote 4 down vote accepted

OEIS knows about your sequence, which it calls Crossing matchings: linear chord diagrams with $2n$ nodes and $n$ arcs in which each arc crosses another arc.

Some highlights:

The sequence starts $$ \begin{multline*} 1, 0, 1, 4, 31, 288, 3272, 43580, 666143, 11491696, \\ 220875237, 4681264432, 108475235444, 2728591657920, 74051386322580, \\ 2156865088819692, 67113404608820943, \\ 2221948578439255200, 77990056655776149179, \ldots \end{multline*} $$

The generating function $F$ is the solution of $$ F' = \frac{-x^2F^3 + F - 1}{2x^3F^2 + 2x^2F}. $$

There is a reference: M. Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Adv. in Appl. Math., 30 (2003), 126-136.

There is a link: Alexander Stoimenow, On enumeration of chord diagrams and asymptotics of Vassiliev invariants, Chapter 3.

If you're wondering how I found the link: I just calculated the first 4 numbers and asked OEIS. I could also have guessed the name, though to be extra sure you need to calculate some numbers anyway.

share|improve this answer
Thank you very much. Do you know anything about the number of almost perfect matchings which are crossing in $K_n$ for any n? almost perfect meaning that if n is odd, then one vertex is allowed to have 2 edges adjacent in the "matching". –  stefan Sep 19 '11 at 4:42
No, but if you can count them for small $n$, you can ask OEIS. Or you can look for "related sequences". Or perhaps, after you calculate you discover a simple connection between the sequences. –  Yuval Filmus Sep 21 '11 at 20:10
Thank you: just to let you know: starting with n = 3, the sequence is: 3, 15, 126,1395,... Im currently thinking about some connection between odd and even case.. –  stefan Sep 22 '11 at 18:05
add comment

Your Answer


