login
This site is supported by donations to The OEIS 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. 14

%I

%S 1,1,2,8,48,352,2880,25216,231168,2190848,21292032,211044352,

%T 2125246464,21681954816,223623069696,2327818174464,24424842461184,

%U 258054752698368,2742964283768832,29312424612462592,314739971287154688,3393951437605044224,36739207546043105280

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

%C Related to Schröder's second problem.

%C 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

%C 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

%C The nodes on the circle are distinguished by their positions but are otherwise unlabeled. - _Lee A. Newberg_, Aug 09 2011

%H Vincenzo Librandi, <a href="/A054726/b054726.txt">Table of n, a(n) for n = 0..200</a>

%H F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/NCC-html/NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies in Automatic Combinatorics, Volume II (1997).

%H Michael Drmota, Anna de Mier, Marc Noy, <a href="http://www.dmg.tuwien.ac.at/drmota/noncrossingFinal4.pdf">Extremal statistics on non-crossing configurations</a>, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - _N. J. A. Sloane_, May 18 2014

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic Combinatorics of Noncrossing Configurations</a>, Discr. Math. 204 (1999), 203-229

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 486

%H Samuele Giraudo, <a href="http://igm.univ-mlv.fr/~giraudo/Articles/CliqueFPSAC.pdf">Combalgebraic structures on decorated cliques</a>, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 10.

%H Marco Kuhlmann, <a href="http://arxiv.org/abs/1504.04993">Tabulation of Noncrossing Acyclic Digraphs</a>, arXiv preprint, 2015.

%H Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, <a href="https://arxiv.org/abs/1706.03357">Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing</a>, arXiv:1706.03357 [cs.CL], 2017.

%H <a href="/index/Ch#CHORD">Sequences related to chord diagrams</a>

%F a(n) = 2^n*A001003(n-2) for n>2.

%F From _Lee A. Newberg_, Aug 09 2011: (Start)

%F G.f.: 1 + (3/2)*z - z^2 - (z/2)*sqrt(1 - 12*z + 4*z^2);

%F a(n) = ((12*n-30)*a(n-1) - (4*n-16)*a(n-2)) / (n-1) for n>1. (End)

%F 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

%p 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)];

%t 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 *)

%o (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

%Y Cf. A006013, A001003.

%Y Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.

%K nonn

%O 0,3

%A _Philippe Flajolet_, Apr 20 2000

%E Offset changed to 0 by _Lee A. Newberg_, Aug 03 2011

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 04:12 EDT 2018. Contains 316405 sequences. (Running on oeis4.)