A326279 -id:A326279 - cp's OEIS frontend

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

1, 1, 2, 8, 48, 352, 2880, 25216, 231168, 2190848, 21292032, 211044352, 2125246464, 21681954816, 223623069696, 2327818174464, 24424842461184, 258054752698368, 2742964283768832, 29312424612462592, 314739971287154688, 3393951437605044224, 36739207546043105280

Offset: 0

Philippe Flajolet, Apr 20 2000

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)

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, and 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, and 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

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.

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

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_,_},_}/;xGus Wiseman, Feb 19 2019 *)

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

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
a(n) = 2^(n-2) * (Legendre_P(n-1, 3) - Legendre_P(n-3, 3))/(2*n - 3) = 2^n * (Legendre_P(n-1, 3) - 3*Legendre_P(n-2, 3))/(4*n - 8), both for n >= 3. - Peter Bala, May 06 2024

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

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Original entry on oeis.org

1, 1, 2, 8, 36, 160, 704, 3088, 13536, 59328, 260032, 1139712

Offset: 0

Gus Wiseman, Jun 20 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(4) = 36 non-crossing, non-nesting simple labeled graphs.

The case for set partitions is A001519.
Simple graphs with crossing or nesting edges are A326279.
Cf. A000088, A000108, A006125, A016098, A054726, A095661, A117662.
Cf. A326209, A326210, A326250, A326255, A326256.

croXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x

A006125(n) = a(n) + A326279(n).
Conjectures from Colin Barker, Jun 28 2019: (Start)
G.f.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).
a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.
(End)

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Original entry on oeis.org

0, 0, 0, 3, 50, 982, 32636, 2096723

Offset: 0

Gus Wiseman, Jun 21 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d.

Gus Wiseman, The a(4) = 50 weakly nesting simple graphs.

Non-nesting set partitions are A000108.
Non-crossing graphs are A054726.
Nesting digraphs are A326209.
Crossing graphs are A326210.
MM-numbers of nesting multiset partitions are A326256.
Cf. A000088, A000332, A006125, A117662.
Cf. A326211, A326243, A326244, A326248, A326257, A326279.

wnsXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x<=z

Conjecture: A006125(n) = a(n) + A000108(n).

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Original entry on oeis.org

1, 0, 1, 4, 13, 44, 149, 504, 1705, 5768, 19513, 66012

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(5) = 44 covering simple graphs with no crossing or nesting edges.

The case for set partitions is A001519.
Covering simple graphs are A006129.
The case with just nesting or just crossing edges forbidden is A324169.
The binomial transform is the non-covering case A326244.
Cf. A000108, A006125, A007297, A054726, A099947, A324327, A326279, A326293.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A326340 Number of maximal simple graphs with vertices {1..n} and no crossing or nesting edges.

Original entry on oeis.org

1, 1, 1, 1, 4, 9, 19, 42

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Gus Wiseman, The a(6) = 19 maximal non-crossing non-nesting graphs.

Covering graphs with no crossing or nesting edges are A326329.
The case with only crossing edges forbidden is A000108 shifted right twice.
Simple graphs without crossing or nesting edges are A326244.
Connected graphs with no crossing or nesting edges are A326339.
Cf. A006125, A007297, A054726, A117662, A136653.
Cf. A324169, A324327, A324328, A326279, A326293.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Subsets[Range[n],{2}]],!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Original entry on oeis.org

0, 0, 0, 4, 56, 1008, 32736, 2097088, 268435328, 68719476480, 35184372088320, 36028797018962944, 73786976294838204416, 302231454903657293672448, 2475880078570760549798240256, 40564819207303340847894502555648, 1329227995784915872903807060280311808

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

Number of simple graphs with vertices {1..n} containing two edges {a,b}, {c,d} that are weakly crossing, meaning a <= c < b <= d or c <= a < d <= b.

			The a(4) = 56 weakly crossing edge-sets:
  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}  {12,13,14,23,24,34}
  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {12,34}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {13,14}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
  {13,23}  {12,14,34}  {12,14,23,24}
  {13,24}  {12,23,24}  {12,14,23,34}
  {13,34}  {12,23,34}  {12,14,24,34}
  {14,24}  {12,24,34}  {12,23,24,34}
  {14,34}  {13,14,23}  {13,14,23,24}
  {23,24}  {13,14,24}  {13,14,23,34}
  {23,34}  {13,14,34}  {13,14,24,34}
  {24,34}  {13,23,24}  {13,23,24,34}
           {13,23,34}  {14,23,24,34}
           {13,24,34}
           {14,23,24}
           {14,23,34}
           {14,24,34}
           {23,24,34}

Cf. A000088, A000108, A002662, A006125, A016098, A054726, A324170.

Cf. A326210, A326244, A326248, A326250, A326257, A326279, A326290.

Table[If[n==0,0,2^Binomial[n,2]-2^(n-1)],{n,0,5}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326340 Number of maximal simple graphs with vertices {1..n} and no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica