Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.