A324169 -id:A324169 - cp's OEIS frontend

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

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

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).

A326351 Number of non-nesting connected simple graphs on a subset of {1..n}.

Original entry on oeis.org

1, 1, 2, 8, 46, 323, 2565

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.

The binomial transform is the covering case A326350.
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}]],Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326351 Number of non-nesting connected simple graphs on a subset of {1..n}.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica