A324167 -id:A324167 - 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

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

Original entry on oeis.org

1, 1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, 49826712, 448771622, 4092553752, 37714212564, 350658882768, 3285490743987, 30989950019532, 294031964658430, 2804331954047160, 26870823304476690, 258548658860327880

Offset: 1

N. J. A. Sloane, Mira Bernstein

Apart from the initial 1, reversion of g.f. for A162395 (squares with signs): see A263843.

			G.f. = x*(1 + x + 4*x^2 + 23*x^3 + 156*x^4 + 1162*x^5 + 9192*x^6 + 75819*x^7 + ...).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..999 (first 101 terms from T. D. Noe)
M. Aguiar and J.-L. Loday, Quadri-algebras, J. Pure Appl. Algebra, 191 (2004), 205-221.
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).
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.
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144.
P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486.
Loïc Foissy, Free quadri-algebras and dual quadri-algebras, arXiv:1504.06056 [math.CO], 2015.
I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656 [math.CO], 2014.
Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv:1504.04993 [cs.DS], 2015.
M. Kuhlmann, P. Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.
Sara Madariaga, Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras, arXiv:1304.5184 [math.RA], 2013.
B. Vallette, Manin products, Koszul duality, Loday algebras and Deligne conjecture, arXiv:math/0609002 [math.QA], 2006-2007; J. Reine Angew. Math. 620 (2008), 105-164.
Gus Wiseman, The a(5) = 156 connected non-crossing graphs.
Gus Wiseman, Constructive Mathematica program for A007297.
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.
Index entries for reversions of series

Cf. A162395, A000290. 4th row of A107111. Row sums of A089434.
See A263843 for a variant.
Cf. A000108 (non-crossing set partitions), A001006, A001187, A054726 (non-crossing graphs), A054921, A099947, A194560, A293510, A323818, A324167, A324169, A324173.

A007297:=proc(n) if n = 1 then 1 else add(binomial(3*n - 3, n + j)*binomial(j - 1, j - n + 1), j = n - 1 .. 2*n - 3)/(n - 1); fi; end;

CoefficientList[ InverseSeries[ Series[(x-x^2)/(1+x)^3, {x, 0, 20}], x], x] // Rest (* From Jean-François Alcover, May 19 2011, after PARI prog. *)
Table[Binomial[3n, 2n+1] Hypergeometric2F1[1-n, n, 2n+2, -1]/n, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

a(n)=if(n<0,0,polcoeff(serreverse((x-x^2)/(1+x)^3+O(x^(n+2))),n+1)) /* Ralf Stephan */

Apart from initial term, g.f. is the series reversion of (x-x^2)/(1+x)^3 (A162395). See A263843. - Vladimir Kruchinin, Feb 08 2013
G.f.: (g-z)/z, where g=-1/3+(2/3)*sqrt(1+9z)*sin((1/3)*arcsin((2+27z+54z^2)/2/(1+9*z)^(3/2))). - Emeric Deutsch, Dec 02 2002
a(n) = (1/n)*Sum_{k=0..n} binomial(3n, n-k-1)*binomial(n+k-1, k). - Paul Barry, May 11 2005
a(n) = 4^(n-1)*(Gamma(3*n/2-1)/Gamma(n/2+1)/Gamma(n) -Gamma((3*n-1)/2)/ Gamma( (n+1)/2)/Gamma(n+1)). - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = 4^n * binomial(3*n/2, n/2) / (9*n-6) - 4^(n-1) * binomial(3*(n-1)/2, (n-1)/2 ) / n. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
D-finite with recurrence: n*(n-1)*(3*n-4)*a(n) +36*(n-1)*a(n-1) -12*(3*n-8)*(3*n-1)*(3*n-7)*a(n-2)=0. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = (1/n)*Sum_{k=0..n} C(3n, k)*C(2n-k-2, n-1). - Paul Barry, Sep 27 2005
a(n) ~ (2-sqrt(3)) * 6^n * 3^(n/2) / (sqrt(2*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 17 2014
a(n) = binomial(3*n,2*n+1)*hypergeom([1-n,n], [2*n+2], -1)/n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = 2*A078531(n) - A085614(n+1). - Vladimir Reshetnikov, Apr 24 2016

Better description from Philippe Flajolet, Apr 20 2000
More terms from James Sellers, Aug 21 2000
Definition revised and initial a(1)=1 added by N. J. A. Sloane, Nov 05 2015 at the suggestion of Axel Boldt. Some of the formulas may now need to be adjusted slightly.

A324170 Numbers whose multiset multisystem (A302242) is crossing.

Original entry on oeis.org

2117, 3973, 4234, 4843, 5183, 5249, 5891, 6351, 6757, 7181, 7801, 7946, 8249, 8468, 8903, 9193, 9686, 9727, 10019, 10063, 10366, 10498, 10585, 11051, 11513, 11567, 11782, 11857, 11919, 12557, 12629, 12702, 12851, 13021, 13193, 13459, 13514, 13631, 14123, 14362

Offset: 1

Gus Wiseman, Feb 17 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem of n is obtained by taking the multiset of prime indices of each prime index of n.

A multiset of multisets is crossing if it contains a 2-element submultiset of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The sequence of terms together with their multiset multisystems begins:
  2117: {{1,3},{2,4}}
  3973: {{1,3},{2,5}}
  4234: {{},{1,3},{2,4}}
  4843: {{1,3},{2,6}}
  5183: {{1,1,3},{2,4}}
  5249: {{1,3},{1,2,4}}
  5891: {{1,4},{2,5}}
  6351: {{1},{1,3},{2,4}}
  6757: {{1,3},{2,7}}
  7181: {{1,4},{2,6}}
  7801: {{1,3},{2,8}}
  7946: {{},{1,3},{2,5}}
  8249: {{2,4},{1,2,3}}
  8468: {{},{},{1,3},{2,4}}
  8903: {{1,3},{2,2,4}}
  9193: {{1,3},{1,2,5}}
  9686: {{},{1,3},{2,6}}
  9727: {{1,1,3},{2,5}}

Cf. A000108, A001055, A001263, A002662, A016098, A054726, A056239, A099947, A112798, A302242.

Cf. A324166, A324167, A324168, A324169, A324171, A324173.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A324169 Number of labeled graphs covering the vertex set {1,...,n} with no crossing edges.

Original entry on oeis.org

1, 0, 1, 4, 25, 176, 1353, 11012, 93329, 815104, 7285489, 66324644, 612863337, 5733381616, 54195878137, 516852285668, 4966883732129, 48049936644736, 467566946973537, 4573486005681092, 44942852084894777, 443484037981300144, 4392621673072766505

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

Two edges {x,y}, {z,t} are crossing if either x < z < y < t or z < x < t < y. If the vertices are arranged in a circle, this is equivalent to crossing of chords.

Covering means there are no isolated vertices.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, The a(4) = 25 graphs covering {1,2,3,4} with no crossing edges.
Gus Wiseman, The a(5) = 176 graphs covering 5 vertices with no crossing edges, radial embedding.

Cf. A000108, A000124, A001006, A001764, A003465, A007297 (connected case), A016098, A054726 (non-crossing graphs), A099947, A306438.

Cf. A324167, A324171, A324173.

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

seq(n)=Vec((2 + 7*x + 3*x^2 - x*sqrt(1 - 10*x - 7*x^2 + O(x^n)))/(2*(1 + x)^3)) \\ Andrew Howroyd, Jan 20 2023

Inverse binomial transform of A054726.

G.f.: (2 + 7*x + 3*x^2 - x*sqrt(1 - 10*x - 7*x^2))/(2*(1 + x)^3). - Andrew Howroyd, Jan 20 2023

A324173 Regular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with k topologically connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 2, 6, 6, 1, 0, 6, 15, 20, 10, 1, 0, 21, 51, 65, 50, 15, 1, 0, 85, 203, 252, 210, 105, 21, 1, 0, 385, 912, 1120, 938, 560, 196, 28, 1, 0, 1907, 4527, 5520, 4620, 2898, 1302, 336, 36, 1, 0, 10205, 24370, 29700, 24780, 15792, 7812, 2730, 540, 45, 1

Offset: 0

Gus Wiseman, Feb 17 2019

A set partition is crossing if it contains a pair of blocks of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

The topologically connected components of a set partition correspond to the blocks of its minimal non-crossing coarsening.

			Triangle begins:
     1
     0     1
     0     1     1
     0     1     3     1
     0     2     6     6     1
     0     6    15    20    10     1
     0    21    51    65    50    15     1
     0    85   203   252   210   105    21     1
     0   385   912  1120   938   560   196    28     1
     0  1907  4527  5520  4620  2898  1302   336    36     1
     0 10205 24370 29700 24780 15792  7812  2730   540    45     1
Row n = 4 counts the following set partitions:
  {{1234}}    {{1}{234}}  {{1}{2}{34}}  {{1}{2}{3}{4}}
  {{13}{24}}  {{12}{34}}  {{1}{23}{4}}
              {{123}{4}}  {{12}{3}{4}}
              {{124}{3}}  {{1}{24}{3}}
              {{134}{2}}  {{13}{2}{4}}
              {{14}{23}}  {{14}{2}{3}}

FindStat, The number of topologically connected components of a set partition.

Row sums are A000110. Column k = 1 is A099947.
Cf. A000108, A001263, A002061, A002662, A007297, A016098, A048993, A054726, A293510, A305078, A305079, A323818.
Cf. A324166, A324167, A324169, A324170, A324171, A324172.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[crosscmpts[#]]==k&]],{n,0,8},{k,0,n}]

A324172 Number of subsets of {1,...,n} that cross their complement.

Original entry on oeis.org

0, 0, 0, 0, 2, 10, 32, 84, 198, 438, 932, 1936, 3962, 8034, 16200, 32556, 65294, 130798, 261836, 523944, 1048194, 2096730, 4193840, 8388100, 16776662, 33553830, 67108212, 134217024, 268434698, 536870098, 1073740952, 2147482716, 4294966302, 8589933534, 17179868060

Offset: 0

Gus Wiseman, Feb 17 2019

Two sets cross each other if they are of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

Also the number of verex cuts in the wheel graph on n nodes. - Eric W. Weisstein, Apr 22 2023

			The a(5) = 10 subsets are {1,3}, {1,4}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,3,4}, {1,3,5}, {2,3,5}, {2,4,5}.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).
Eric Weisstein's World of Mathematics, Vertex Cut
Eric Weisstein's World of Mathematics, Wheel Graph

Cf. A000108, A000110, A000124, A001263, A002061, A002662, A016098, A306438.

Cf. A324166, A324167, A324168, A324169, A324173.

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

concat([0,0,0,0], Vec(2*x^4 / ((1 - x)^3*(1 - 2*x)) + O(x^40))) \\ Colin Barker, Feb 19 2019

a(0) = 0; a(n) = 2^n - n^2 + n - 2.
a(n) = 2*A002662(n-1) for n > 0.
G.f.: 2*x^4/((1-2*x)*(1-x)^3).
a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n>4. - Colin Barker, Feb 18 2019

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

Original entry on oeis.org

1, 1, 4, 16, 75, 378, 2042, 11489, 66697

Offset: 0

Gus Wiseman, Feb 17 2019

A multiset is normal if its union is an initial interval of positive integers.

A multiset partition is crossing if it has a 2-element submultiset of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The A255906(5) - a(5) = 22 crossing multiset partitions:
  {{13}{124}}  {{1}{13}{24}}
  {{13}{224}}  {{1}{24}{35}}
  {{13}{234}}  {{2}{13}{24}}
  {{13}{244}}  {{2}{14}{35}}
  {{13}{245}}  {{3}{13}{24}}
  {{14}{235}}  {{3}{14}{25}}
  {{24}{113}}  {{4}{13}{24}}
  {{24}{123}}  {{4}{13}{25}}
  {{24}{133}}  {{5}{13}{24}}
  {{24}{134}}
  {{24}{135}}
  {{25}{134}}
  {{35}{124}}

Cf. A000108 (non-crossing set partitions), A000124, A001006, A001055, A001263, A007297, A054726 (non-crossing graphs), A099947, A194560, A255906 (multiset partitions of normal multisets), A306438.

Cf. A324166, A324167, A324168, A324169, A324170, A324173.

nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Select[mps[m],nonXQ]],{m,allnorm[n]}],{n,0,8}]

A324327 Number of topologically connected chord graphs covering {1,...,n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 11, 257

Offset: 0

Gus Wiseman, Feb 22 2019

A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected, where two edges cross each other if they are of the form {{x,y},{z,t}} with x < z < y < t or z < x < t < y.

Covering means there are no isolated vertices.

			The a(0) = 1 through a(5) = 11 graphs:
  {}  {{12}}  {{13}{24}}  {{13}{14}{25}}
                          {{13}{24}{25}}
                          {{13}{24}{35}}
                          {{14}{24}{35}}
                          {{14}{25}{35}}
                          {{13}{14}{24}{25}}
                          {{13}{14}{24}{35}}
                          {{13}{14}{25}{35}}
                          {{13}{24}{25}{35}}
                          {{14}{24}{25}{35}}
                          {{13}{14}{24}{25}{35}}

Gus Wiseman, The a(5) = 11 topologically connected chord graphs.
Gus Wiseman, The a(6) = 257 topologically connected chord graphs.

Cf. A000108, A000699 (the case with disjoint edges), A001764, A002061, A007297, A016098, A054726, A099947, A136653 (the case with set-theoretical connectedness also), A268814.

Cf. A324167, A324169 (non-crossing covers), A324172, A324173, A324323, A324328 (non-covering case).

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[crosscmpts[#]]<=1]&]],{n,0,5}]

Inverse binomial transform of A324328.

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 19, 120, 1084, 11783, 141110, 1791156, 23646352, 321220257, 4459886776, 63000867229, 902528825332, 13080523942476, 191445447535373, 2825542818304080, 42005234042942228, 628422035415996065, 9454076958795999908, 142933849346150225253, 2170556938059142024688

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(3) = 19 non-crossing antichains:
  {}  {}     {}        {}
      {{1}}  {{1}}     {{1}}
             {{2}}     {{2}}
             {{12}}    {{3}}
             {{1}{2}}  {{12}}
                       {{13}}
                       {{23}}
                       {{123}}
                       {{1}{2}}
                       {{1}{3}}
                       {{2}{3}}
                       {{1}{23}}
                       {{2}{13}}
                       {{3}{12}}
                       {{12}{13}}
                       {{12}{23}}
                       {{13}{23}}
                       {{1}{2}{3}}
                       {{12}{13}{23}}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000108 (non-crossing set partitions), A000124, A000372 (antichains), A001006, A001263, A006126 (antichain covers), A014466 (nonempty antichains), A054726 (non-crossing graphs), A099947, A261005, A306438.

Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

nn=6;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-2*x))/x) } \\ Andrew Howroyd, Jan 20 2023

Binomial transform of A324167.

G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - Andrew Howroyd, Jan 20 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

A304999 Number of labeled antichains of finite sets spanning n vertices with singleton edges allowed.

Original entry on oeis.org

1, 1, 5, 53, 1577, 212137, 496946349, 309068823607069, 14369391923126237496803793, 146629927766168786109802623629262590838145873

Offset: 0

Gus Wiseman, May 23 2018

Only the non-singleton edges are required to form an antichain.

			The a(2) = 5 antichains:
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See p. 4.
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Cf. A006126, A014466, A261005, A304996, A304997, A304998, A304999, A305000, A305001.

Cf. A000372, A003182, A304985, A305844, A306505, A319721, A321679, A324167.

Exponential transform of A304985.

Inverse binomial transform of A305000. - Aniruddha Biswas, May 12 2024

a(5)-a(8) from Gus Wiseman, May 31 2018

a(9) from Aniruddha Biswas, May 12 2024

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

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A324170 Numbers whose multiset multisystem (A302242) is crossing.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324169 Number of labeled graphs covering the vertex set {1,...,n} with no crossing edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A324173 Regular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with k topologically connected components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A324172 Number of subsets of {1,...,n} that cross their complement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica