A081054 Crossing matchings: linear chord diagrams with 2n nodes and n arcs in which each arc crosses another arc.

1, 0, 1, 4, 31, 288, 3272, 43580, 666143, 11491696, 220875237, 4681264432, 108475235444, 2728591657920, 74051386322580, 2156865088819692, 67113404608820943, 2221948578439255200, 77990056655776149179

Offset

0,4

Links

Table of n, a(n) for n=0..18.

Olivia Beckwith, Victor Luo, Stephen J. Miller, Karen Shen, Nicholas Triantafillou, Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles, arXiv:1112.3719 [math.PR], 2011-2012.

Olivia Beckwith, Victor Luo, Stephen J. Miller, Karen Shen, Nicholas Triantafillou, Distribution of Eigenvalues of Weighted, Structured Matrix Ensembles, Electronic Journal of Combinatorial Number Theory, Volume 15 (2015) #A21.

M. Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.

Alexander Stoimenow, On enumeration of chord diagrams and asymptotics of Vassiliev invariants, Dissertation, Mathematik und Informatik, University of Berlin, 1998; see chapter 3.

Formula

The g.f. (a formal power series) F = 1 + x^2 + 4*x^3 + ... satisfies the differential equation F' = (-x^2*F^3 + F - 1)/(2*x^3*F^2 + 2*x^2*F).

a(n) is asymptotic to (2n)!/(e 2^n n!). In other words, the probability that a random matching is a crossing matching is asymptotic to 1/e; see Lemma 3.12 of Stoimenow reference. - Benoit Cloitre, Apr 18 2003; corrected by Dean Hickerson, Apr 21 2003

Example

The 4 crossing matchings on nodes 1, 2, ..., 6 are {13, 25, 46}, {14, 25, 36}, {15, 24, 36} and {14, 26, 35}.

Mathematica

a[n_] := a[n]=Module[{x, y, z, i}, y=Sum[a[i]x^i, {i, 0, n-1}]+z*x^n+O[x]^(n+1); Solve[D[y, x]==(-1+y-x^2y^3)/(2x^2y(1+x*y)), z][[1, 1, 2]]]

Crossrefs

Cf. A000699, A004300.

Sequence in context: A077615 A039306 A265949 * A261053 A192407 A000858

Adjacent sequences: A081051 A081052 A081053 * A081055 A081056 A081057

Keyword

easy,nonn

Author

Martin Klazar, Apr 15 2003

Status

approved