

A054726


Number of graphs with n nodes on a circle without crossing edges.


55



1, 1, 2, 8, 48, 352, 2880, 25216, 231168, 2190848, 21292032, 211044352, 2125246464, 21681954816, 223623069696, 2327818174464, 24424842461184, 258054752698368, 2742964283768832, 29312424612462592, 314739971287154688, 3393951437605044224, 36739207546043105280
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Related to Schröder's second problem.
A001006 gives number of ways of drawing any number of nonintersecting chords between n points on a circle, while this sequence gives number of ways of drawing noncrossing chords between n points on a circle. The difference is that nonintersection chords have no point in common, while noncrossing chords may share an endpoint.  David W. Wilson, Jan 30 2003
For n>0, a(n) = number of lattice paths from (0,0) to (n1,n1) that consist of steps (i,j), i,j nonnegative integers not both 0 and that stay strictly below the line y=x except at their endpoints. For example, a(3)=8 counts the paths with following step sequences: {(2, 2)}, {(2, 1), (0, 1)}, {(2, 0), (0, 2)}, {(2, 0), (0, 1), (0, 1)}, {(1, 0), (1, 2)}, {(1, 0), (1, 1), (0, 1)}, {(1, 0), (1, 0), (0, 2)}, {(1, 0), (1, 0), (0, 1), (0, 1)}. If the word "strictly" is replaced by "weakly", the counting sequence becomes A059435.  David Callan, Jun 07 2006
The nodes on the circle are distinguished by their positions but are otherwise unlabeled.  Lee A. Newberg, Aug 09 2011
From Gus Wiseman, Jun 22 2019: (Start)
Conjecture: Also the number of simple graphs with vertices {1..n} not containing any pair of nesting edges. Two edges {a,b}, {c,d} where a < b and c < d are nesting if a < c and b > d or a > c and b < d. For example, the a(0) = 1 through a(3) = 8 nonnesting edgesets are:
{} {} {} {}
{12} {12}
{13}
{23}
{12,13}
{12,23}
{13,23}
{12,13,23}
Cf. A001519, A117662, A326244, A326256, A326257, A326279.
(End)


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascallike Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
F. Cazals, Combinatorics of NonCrossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on noncrossing configurations, Discrete Math. 327 (2014), 103117. MR3192420. See Eq. (3).  N. J. A. Sloane, May 18 2014
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203229
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 10.
Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv preprint arXiv:1504.04993 [cs.DS], 2015.
Gus Wiseman, The a(4) = 48 noncrossing graphs.
Gus Wiseman, The a(5) = 352 noncrossing graphs.
Gus Wiseman, The a(4) = 48 nonnesting simple graphs.
Anssi YliJyrä and Carlos GómezRodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.
Sequences related to chord diagrams


FORMULA

a(n) = 2^n*A001003(n2) for n>2.
From Lee A. Newberg, Aug 09 2011: (Start)
G.f.: 1 + (3/2)*z  z^2  (z/2)*sqrt(1  12*z + 4*z^2);
a(n) = ((12*n30)*a(n1)  (4*n16)*a(n2)) / (n1) for n>1. (End)
a(n) ~ 2^(n  7/4) * (1 + sqrt(2))^(2*n3) / (sqrt(Pi) * n^(3/2)).  Vaclav Kotesovec, Oct 11 2012, simplified Dec 24 2017


MAPLE

with(combstruct): br:= {EA = Union(Sequence(EA, card >= 2), Prod(V, Sequence(EA), Sequence(EA))), V=Union(Prod(Z, G)), G=Union(Epsilon, Prod(Z, G), Prod(V, V, Sequence(EA), Sequence(EA), Sequence(Union(Sequence(EA, card>=1), Prod(V, Sequence(EA), Sequence(EA)))))) }; ggSeq := [seq(count([G, br], size=i), i=0..20)];


MATHEMATICA

Join[{a = 1, b = 1}, Table[c = (6*(2*n  3)*b)/n  (4*(n  3) a)/n; a = b; b = c, {n, 1, 40}]] (* Vladimir Joseph Stephan Orlovsky, Jul 11 2011 *)
nn=8;
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<tz<x<t<y];
stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===wQ[r, w]Q[w, r]], Q]]]];
Table[Length[stableSets[Subsets[Range[n], {2}], croXQ[{#1, #2}]&]], {n, 0, nn}] (* Gus Wiseman, Feb 19 2019 *)


PROG

(PARI) z='z+O('z^66); Vec( 1+3/2*zz^2z/2*sqrt(112*z+4*z^2) ) \\ Joerg Arndt, Mar 01 2014


CROSSREFS

Cf. A006013, A001003.
Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.
Cf. A000108 (noncrossing set partitions), A000124, A006125, A007297 (connected case), A194560, A306438, A324167, A324169 (covering case), A324173, A326210.
Sequence in context: A171455 A136722 A085615 * A003576 A225042 A326887
Adjacent sequences: A054723 A054724 A054725 * A054727 A054728 A054729


KEYWORD

nonn


AUTHOR

Philippe Flajolet, Apr 20 2000


EXTENSIONS

Offset changed to 0 by Lee A. Newberg, Aug 03 2011


STATUS

approved



