|
%I #102 Aug 24 2020 06:35:15
%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
%C From _Gus Wiseman_, Jun 22 2019: (Start)
%C 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:
%C {} {} {} {}
%C {12} {12}
%C {13}
%C {23}
%C {12,13}
%C {12,23}
%C {13,23}
%C {12,13,23}
%C Cf. A001519, A117662, A326244, A326256, A326257, A326279.
%C (End)
%H Vincenzo Librandi, <a href="/A054726/b054726.txt">Table of n, a(n) for n = 0..200</a>
%H Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry3/barry422.html">Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles</a>, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
%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 Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, <a href="https://arxiv.org/abs/2003.00524">New production matrices for geometric graphs</a>, arXiv:2003.00524 [math.CO], 2020.
%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="https://arxiv.org/abs/1709.08416">Combalgebraic structures on decorated cliques</a>, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 10, arXiv:1709.08416 [math.CO], 2017.
%H Marco Kuhlmann, <a href="http://arxiv.org/abs/1504.04993">Tabulation of Noncrossing Acyclic Digraphs</a>, arXiv preprint arXiv:1504.04993 [cs.DS], 2015.
%H Gus Wiseman, <a href="/A054726/a054726.png">The a(4) = 48 non-crossing graphs.</a>
%H Gus Wiseman, <a href="/A054726/a054726_1.png">The a(5) = 352 non-crossing graphs.</a>
%H Gus Wiseman, <a href="/A054726/a054726_2.png">The a(4) = 48 non-nesting simple graphs.</a>
%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 D-finite with recurrence: 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 *)
%t nn=8;
%t croXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<y<t||z<x<t<y];
%t 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]]]];
%t Table[Length[stableSets[Subsets[Range[n],{2}],croXQ[{#1,#2}]&]],{n,0,nn}] (* _Gus Wiseman_, Feb 19 2019 *)
%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.
%Y Cf. A000108 (non-crossing set partitions), A000124, A006125, A007297 (connected case), A194560, A306438, A324167, A324169 (covering case), A324173, A326210.
%K nonn
%O 0,3
%A _Philippe Flajolet_, Apr 20 2000
%E Offset changed to 0 by _Lee A. Newberg_, Aug 03 2011
|
