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

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}]

A136653 G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 4, 39, 748, 27162, 1880872, 252273611, 66358216668, 34506398937158, 35644762692112792, 73356520492898454022, 301274559225693420690360, 2471654510727312089903896948, 40527708183358718551543295827536, 1328579216048284168977214446788083699

Offset: 0

Paul D. Hanna, Jan 15 2008

nonn

a(n) is the number of graphs on vertices 1,...,n such that, when these vertices are arranged counterclockwise around a circle and edges are drawn as straight line segments, the resulting diagram is connected. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

In this interpretation, both intersecting (set theoretically) and crossing (topologically) edges are considered connected. - Gus Wiseman, Feb 23 2019

			G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 39*x^4 + 748*x^5 + 27162*x^6 +...
Let F(x) = 1 + x + 2*x^2 + 8*x^3 + 64*x^4 + 1024*x^5 +...+ 2^(n*(n-1)/2)*x^n +..
then A(x) = F(x/A(x)), A(x*F(x)) = F(x).
Coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2),
as can be seen by the main diagonal in the array of
coefficients in the initial powers of A(x):
A^1: [(1), 1, 1, 4, 39, 748, 27162, 1880872, 252273611,...;
A^2: [1, (2), 3, 10, 87, 1582, 55914, 3817876, 508370795,...;
A^3: [1, 3, (6), 19, 147, 2517, 86398, 5813550, 768378627,...;
A^4: [1, 4, 10, (32), 223, 3572, 118778, 7870640, 1032387787,...;
A^5: [1, 5, 15, 50, (320), 4771, 153245, 9992130, 1300492845,...;
A^6: [1, 6, 21, 74, 444, (6144), 190023, 12181278, 1572792585,...;
A^7: [1, 7, 28, 105, 602, 7728, (229376), 14441659, 1849390375,...;
A^8: [1, 8, 36, 144, 802, 9568, 271616, (16777216), 2130394591,...;
A^9: [1, 9, 45, 192, 1053, 11718, 317112, 19192320, (2415919104),...;
dividing each diagonal term in row n by (n+1) gives 2^(n*(n-1)/2).
The diagonal above the main diagonal gives coefficients of l.g.f.:
log(F(x)) = x + 3*x^2/2 + 19*x^3/3 + 223*x^4/4 + 4771*x^5/5 +...

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 39 graphs connected by overlaps or crossings.

Cf. A136652 (log(A(x))), A136654.
Cf. A000699, A002662, A006125, A007297, A016098, A054726, A099947, A306438.
Cf. A324166, A324169, A324172, A324173, A324327, A324328.

max = 15; s = x*Sum[2^(k*(k-1)/2)*x^k, {k, 0, max}] + O[x]^(max+2); x/InverseSeries[s] + O[x]^(max+1) // CoefficientList[#, x]& (* Jean-François Alcover, Sep 03 2017 *)
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
bicmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],Intersection@@#!={}&],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[bicmpts[#]]<=1]&]],{n,0,5}] (* Gus Wiseman, Feb 23 2019 *)

a(n)=polcoeff(x/serreverse(x*sum(k=0,n,2^(k*(k-1)/2)*x^k +x*O(x^n))),n)

G.f.: A(x) = x/Series_Reversion( x*Sum_{k=0..n} 2^(k(k-1)/2)*x^k ).

Equals the free cumulant sequence corresponding to A006125. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

Name changed and part of prior name moved to formula section by Paul D. Hanna, Sep 19 2013

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

A324167 Number of non-crossing antichain covers of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 9, 67, 633, 6763, 77766, 938957, 11739033, 150649945, 1973059212, 26265513030, 354344889798, 4833929879517, 66568517557803, 924166526830701, 12920482325488761, 181750521972603049, 2570566932237176232, 36532394627404815308, 521439507533582646156

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(3) = 9 antichains:
  {{1,2,3}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}

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

Cf. A000108, A000124, A000372 (antichains), A001006, A006126 (antichain covers), A014466, A048143, A054726 (non-crossing graphs), A099947, A261005, A283877, A306438.

Cf. A324166, A324168, A324169, A324170, A324171, A324173, A359984 (no singletons).

nn=6;
croXQ[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-x))/x) } \\ Andrew Howroyd, Jan 20 2023

Inverse binomial transform of A324168.

Binomial transform of A359984. - Andrew Howroyd, Jan 20 2023

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

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.

A324328 Number of topologically connected chord graphs on a subset of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 4, 8, 27, 354

Offset: 0

Gus Wiseman, Feb 22 2019

			The a(0) = 1 through a(5) = 27 graphs:
  {}  {}  {}      {}      {}          {}
          {{12}}  {{12}}  {{12}}      {{12}}
                  {{13}}  {{13}}      {{13}}
                  {{23}}  {{14}}      {{14}}
                          {{23}}      {{15}}
                          {{24}}      {{23}}
                          {{34}}      {{24}}
                          {{13}{24}}  {{25}}
                                      {{34}}
                                      {{35}}
                                      {{45}}
                                      {{13}{24}}
                                      {{13}{25}}
                                      {{14}{25}}
                                      {{14}{35}}
                                      {{24}{35}}
                                      {{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}}

Cf. A000108, A000699, A001764, A002061, A007297, A016098, A054726 (non-crossing chord graphs), A099947, A136653, A268814.

Cf. A324168, A324169, A324172, A324173, A324323, A324327 (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}]],Length[crosscmpts[#]]<=1&]],{n,0,5}]

Binomial transform of A324327.

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

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

A136653 G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A324167 Number of non-crossing antichain covers of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links