4
$\begingroup$

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

  • 0
    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.2011-09-12

1 Answers 1

4

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.

  • 0
    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..2011-09-22