A054726 -id:A054726 - cp's OEIS frontend

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

1, 1, 2, 8, 35, 147, 600, 2418

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.

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

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

The inverse binomial transform is the covering case A326339.
Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
Graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

Conjecture: a(n) = A052161(n - 2) + 1.

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 22, 119

Offset: 0

Gus Wiseman, Jun 29 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. A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

			The a(4) = 1 through a(6) = 22 edge-sets:
  {13,24}  {13,14,25}  {13,25,46}
           {13,24,25}  {14,25,36}
           {13,24,35}  {14,26,35}
           {14,24,35}  {15,24,36}
           {14,25,35}  {13,14,15,26}
                       {13,14,25,26}
                       {13,15,24,26}
                       {13,15,26,46}
                       {13,24,25,26}
                       {13,24,25,36}
                       {13,24,26,35}
                       {13,24,35,36}
                       {13,24,35,46}
                       {14,15,26,36}
                       {14,24,35,36}
                       {14,24,35,46}
                       {14,25,35,46}
                       {15,24,35,46}
                       {15,25,35,46}
                       {15,25,36,46}
                       {15,26,35,46}
                       {15,26,36,46}

The non-minimal case is A324327.
Minimal covers are A053530.
Topologically connected graphs are A324327 (covering) or A324328 (all).
Cf. A000108, A006125, A007297, A054726, A136653, A324169, A326210, A326293.

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[fasmin[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[crosscmpts[#]]<=1]&]]],{n,0,5}]

A359984 Number of non-crossing antichain covers of {1,...,n} without singletons.

Original entry on oeis.org

1, 0, 1, 5, 40, 372, 3815, 41652, 474980, 5591912, 67454545, 829438722, 10358083621, 131013535954, 1674940506728, 21608978465341, 280976960703472, 3678460005228692, 48446069275681169, 641429612434785006, 8532711384899213885, 113988520118626013998

Offset: 0

Andrew Howroyd, Jan 20 2023

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.

All sets in the antichain include at least two vertices.

			The a(3) = 5 antichains:
  {{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1,2},{1,3},{2,3}}
The last 4 of these correspond to the graphs of A324169.

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

Cf. A054726, A324167, A324168, A324169.

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(1 + x^2*f^2 - 3*x^3*f^3) } \\ Andrew Howroyd, Jan 20 2023

Inverse binomial transform of A324167.
G.f.: 1 + x^2*F(x)^2 - 3*x^3*F(x)^3 where F(x) satisfies F(x) = 1 + (4*x + x^2)*F(x)^2 - 3*x^2*(1 + x)*F(x)^3 = 1 +4*x +30*x^2 +273*x^3 +2770*x^4 +30059*x^5+....
a(n) >= A324169(n).
Conjecture D-finite with recurrence 8*n*(n-1)*a(n) -4*(n-1)*(56*n-145)*a(n-1) +4*(101*n^2-682*n+996)*a(n-2) +2*(6200*n^2-47903*n+88131)*a(n-3) +2*(26985*n^2-234056*n+491978)*a(n-4) +2*(62749*n^2-628865*n+1584314)*a(n-5) +(n-5)*(121577*n-667756)*a(n-6) +38285*(n-5)*(n-6)*a(n-7)=0. - R. J. Mathar, Mar 10 2023

A054730 Odd n such that genus of modular curve X_0(N) is never equal to n.

Original entry on oeis.org

49267, 74135, 94091, 96463, 102727, 107643, 118639, 138483, 145125, 181703, 182675, 208523, 221943, 237387, 240735, 245263, 255783, 267765, 269627, 272583, 277943, 280647, 283887, 286815, 309663, 313447, 322435, 326355, 336675, 347823, 352719

Offset: 1

Janos A. Csirik, Apr 21 2000

nonn

There are 4329 odd integers in the sequence less than 10^7. - Gheorghe Coserea, May 23 2016

J. A. Csirik, The genus of X_0(N) is not 150, preprint, 2000.

Gheorghe Coserea, Table of n, a(n) for n = 1..4329
J. A. Csirik, M. Zieve, and J. Wetherell, On the genera of X0(N), arXiv:math/0006096 [math.NT], 2000.

Cf. A054726, A054727, A054729.

A000089(n) = {
  if (n%4 == 0 || n%4 == 3, return(0));
  if (n%2 == 0, n \= 2);
  my(f = factor(n), fsz = matsize(f)[1]);
  prod(k = 1, fsz, if (f[k, 1] % 4 == 3, 0, 2));
};
A000086(n) = {
  if (n%9 == 0 || n%3 == 2, return(0));
  if (n%3 == 0, n \= 3);
  my(f = factor(n), fsz = matsize(f)[1]);
  prod(k = 1, fsz, if (f[k, 1] % 3 == 2, 0, 2));
};
A001615(n) = {
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, (f[k, 1]+1)),
     h = prod(k=1, fsz, f[k, 1]));
  return((n*g)\h);
};
A001616(n) = {
  my(f = factor(n), fsz = matsize(f)[1]);
  prod(k = 1, fsz, f[k, 1]^(f[k, 2]\2) + f[k, 1]^((f[k, 2]-1)\2));
};
A001617(n) = 1 + A001615(n)/12 - A000089(n)/4 - A000086(n)/3 - A001616(n)/2;
scan(n) = {
  my(inv = vector(n+1, g, -1), bnd = 12*n + 18*sqrtint(n) + 100, g);
  for (k = 1, bnd, g = A001617(k);
       if (g <= n && inv[g+1] == -1, inv[g+1] = k));
  select(x->(x%2==1), apply(x->(x-1), Vec(select(x->x==-1, inv, 1))));
};
scan(400*1000)

More terms from Gheorghe Coserea, May 23 2016

Offset corrected by Gheorghe Coserea, May 23 2016

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Original entry on oeis.org

0, 0, 1, 9, 32, 80, 165, 301, 504, 792, 1185, 1705, 2376, 3224, 4277, 5565, 7120, 8976, 11169, 13737, 16720, 20160, 24101, 28589, 33672, 39400, 45825, 53001, 60984, 69832, 79605, 90365, 102176, 115104, 129217, 144585, 161280, 179376, 198949, 220077, 242840

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

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.

			The a(3) = 9 pairs of edges:
  {12,12}
  {12,13}
  {12,23}
  {13,12}
  {13,13}
  {13,23}
  {23,12}
  {23,13}
  {23,23}

Gus Wiseman, The a(4) = 32 pairs of edges that are neither crossing nor nesting.

The case for simple graphs (rather than multigraphs) is A095661.
Simple graphs that are neither crossing nor nesting are A326244.
The case for set partitions is A001519.
Non-crossing and non-nesting simple graphs are (both) A054726.
Cf. A000108, A002061, A006125, A117662, A324170, A326250, A326256.

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

Conjectures from Colin Barker, Jun 21 2019: (Start)
G.f.: x^2*(1 + 4*x - 3*x^2) / (1 - x)^5.
a(n) = (n*(12 - 19*n + 6*n^2 + n^3)) / 12.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
(End)

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

A326290 Number of non-crossing n-vertex graphs with loops.

Original entry on oeis.org

1, 2, 8, 64, 768, 11264, 184320, 3227648, 59179008, 1121714176, 21803040768, 432218832896, 8705009516544, 177618573852672, 3663840373899264, 76277945940836352, 1600706475536154624, 33823752545680490496, 719051629204296695808, 15368152475218787434496

Offset: 0

Gus Wiseman, Sep 12 2019

nonn

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

			The a(0) = 1 through a(2) = 8 non-crossing edge sets with loops:
  {}  {}    {}
      {11}  {11}
            {12}
            {22}
            {11,12}
            {11,22}
            {12,22}
            {11,12,22}

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

Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.

Cf. A000108, A002061, A002662, A054726, A324172, A326252.

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

seq(n)=Vec(1+3*x-4*x^2 -x*sqrt(1-24*x+16*x^2 + O(x^n))) \\ Andrew Howroyd, Sep 14 2019

From Andrew Howroyd, Sep 14 2019: (Start)
a(n) = 2^n * A054726(n).
G.f.: 1 + 3*x - 4*x^2 - x*sqrt(1 - 24*x + 16*x^2). (End)

Terms a(6) and beyond from Andrew Howroyd, Sep 14 2019

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 11, 95, 797

Offset: 0

Gus Wiseman, Jun 30 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. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

			The a(5) = 11 edge-sets:
  {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(6) = 95 non-nesting, topologically connected, covering simple graphs.

The binomial transform is the non-covering case A326293.
Topologically connected, covering simple graphs are A324327.
Non-crossing, covering simple graphs are A324169.
Cf. A000108, A000699, A006125, A054726, A099947, A117662.
Cf. A324323, A324328, A326329, A326330, A326339, A326341.

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

A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

Original entry on oeis.org

1, 0, 1, 4, 23, 157, 1182

Offset: 0

Gus Wiseman, Jun 30 2019

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

Gus Wiseman, The a(4) = 23 non-nesting connected simple graphs.
Gus Wiseman, The a(5) = 157 non-nesting connected simple graphs.

The inverse binomial transform is the non-covering case A326351.
Connected simple graphs are A001349.
Connected simple graphs with no crossing or nesting edges are A326294.
Simple graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326329, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 5, 9, 7, 7, 11, 11, 12, 16, 14, 15, 26, 22, 21, 29, 19, 30, 33, 31, 30, 66, 38, 42, 52, 56, 42, 47, 45, 57, 82, 77, 67, 77, 67, 101, 98, 135, 64, 137, 97, 176, 104, 109, 109, 118, 105, 231, 213, 97, 127, 181, 139, 297, 173, 385, 195, 269

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

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

			The a(16) = 14 non-crossing multiset partitions of the multiset {1,2,3,4}:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{2},{1,3,4}}
  {{3},{1,2,4}}
  {{4},{1,2,3}}
  {{1,2},{3,4}}
  {{1,4},{2,3}}
  {{1},{2},{3,4}}
  {{1},{3},{2,4}}
  {{1},{4},{2,3}}
  {{2},{3},{1,4}}
  {{2},{4},{1,3}}
  {{3},{1,2},{4}}
  {{1},{2},{3},{4}}
Missing from this list is {{1,3},{2,4}}.

Cf. A000108, A001055, A001970, A016098, A054726, A099947, A181821, A305936, A306438, A318284, A318285.

Cf. A324167, A324168, A324169, A324170, A324171, A324324, A324326.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

a(n) + A324326(n) = A318284(n).

cp's OEIS Frontend

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A359984 Number of non-crossing antichain covers of {1,...,n} without singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A054730 Odd n such that genus of modular curve X_0(N) is never equal to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326290 Number of non-crossing n-vertex graphs with loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

Views

Author

Keywords