The OEIS is supported by the many generous donors to the OEIS Foundation.

 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. 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

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

Last modified August 9 00:15 EDT 2022. Contains 356016 sequences. (Running on oeis4.)