login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (n-1,n-1) 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 non-nesting edge-sets 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 Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - N. J. A. Sloane, May 18 2014

Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, New production matrices for geometric graphs, arXiv:2003.00524 [math.CO], 2020.

P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229

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, arXiv:1709.08416 [math.CO], 2017.

Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv preprint arXiv:1504.04993 [cs.DS], 2015.

Gus Wiseman, The a(4) = 48 non-crossing graphs.

Gus Wiseman, The a(5) = 352 non-crossing graphs.

Gus Wiseman, The a(4) = 48 non-nesting simple graphs.

Anssi Yli-Jyrä and Carlos Gómez-Rodrí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(n-2) 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);

D-finite with recurrence: a(n) = ((12*n-30)*a(n-1) - (4*n-16)*a(n-2)) / (n-1) for n>1. (End)

a(n) ~ 2^(n - 7/4) * (1 + sqrt(2))^(2*n-3) / (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<t||z<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===w||Q[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*z-z^2-z/2*sqrt(1-12*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 (non-crossing 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 25 04:05 EDT 2020. Contains 338011 sequences. (Running on oeis4.)