|
Search: id:A081054
|
|
|
| A081054 |
|
Crossing matchings: linear chord diagrams with 2n nodes and n arcs in which each arc crosses another arc. |
|
+0
1
|
|
| 1, 0, 1, 4, 31, 288, 3272, 43580, 666143, 11491696, 220875237, 4681264432, 108475235444, 2728591657920, 74051386322580, 2156865088819692, 67113404608820943, 2221948578439255200, 77990056655776149179
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
REFERENCES
|
M. Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Adv. in Appl. Math., 30 (2003), 126-136.
|
|
LINKS
|
Alexander Stoimenow, On enumeration of chord diagrams and asymptotics of Vassiliev invariants., 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 (benoit7848c(AT)orange.fr), Apr 18 2003; corrected by Dean Hickerson (dean(AT)math.ucdavis.edu), 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.
Adjacent sequences: A081051 A081052 A081053 this_sequence A081055 A081056 A081057
Sequence in context: A077615 A025506 A039306 this_sequence A000858 A003436 A114475
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Martin Klazar (klazar(AT)kam.mff.cuni.cz), Apr 15 2003
|
|
|
Search completed in 0.002 seconds
|
