A324169 -id:A324169 - cp's OEIS frontend

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

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

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

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Original entry on oeis.org

1, 0, 1, 3, 29, 595, 23437

Offset: 0

Gus Wiseman, Jun 28 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. A graph has its weakly nesting edges connected if the graph whose vertices are the edges and whose edges are weakly nesting pairs of edges is connected.

Gus Wiseman, The a(4) = 29 covering simple graphs whose weakly nesting edges are connected.

The binomial transform is the non-covering case A326338.
The non-weak case is A326331.
Simple graphs whose nesting edges are connected are A326330.
Cf. A006125, A007297, A054726, A099947, A136653.
Cf. A324169, A324327, A326293, A326294, A326329, A326335, A326336.

wknXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;(x<=z&&y>=t)||(x>=z&&y<=t)];
wknestcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],wknXQ]]];
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[wknestcmpts[#]]<=1&]],{n,0,5}]

A306386 Number of chord diagrams with n chords all having arc length at least 3.

Original entry on oeis.org

1, 0, 0, 1, 7, 68, 837, 11863, 189503, 3377341, 66564396, 1439304777, 33902511983, 864514417843, 23735220814661, 698226455579492, 21914096529153695, 731009183350476805, 25829581529376423945, 963786767538027630275, 37871891147795243899204, 1563295398737378236910447

Offset: 0

Gus Wiseman, Feb 26 2019

nonn

A cyclical form of A190823.

Also the number of 2-uniform set partitions of {1...2n} such that, when the vertices are arranged uniformly around a circle, no block has its two vertices separated by an arc length of less than 3.

			The a(8) = 7 2-uniform set partitions with all arc lengths at least 3:
  {{1,4},{2,6},{3,7},{5,8}}
  {{1,4},{2,7},{3,6},{5,8}}
  {{1,5},{2,6},{3,7},{4,8}}
  {{1,5},{2,6},{3,8},{4,7}}
  {{1,5},{2,7},{3,6},{4,8}}
  {{1,6},{2,5},{3,7},{4,8}}
  {{1,6},{2,5},{3,8},{4,7}}

Alois P. Heinz, Table of n, a(n) for n = 0..404
Gus Wiseman, The a(5) = 68 chord diagrams with all arc lengths at least 3.

Cf. A000296, A000699, A001006, A001147, A001610, A003436, A038041, A054726, A135042, A170941, A190823, A278990, A306419, A322402, A324011, A324169.

Column k=3 of A324428.

a:= proc(n) option remember; `if`(n<8, [1, 0$2, 1, 7, 68, 837, 11863][n+1],
      ((8*n^4-64*n^3+142*n^2-66*n+109)    *a(n-1)
      -(24*n^4-248*n^3+870*n^2-1106*n+241)*a(n-2)
      +(24*n^4-264*n^3+982*n^2-1270*n+145)*a(n-3)
      -(8*n^4-96*n^3+374*n^2-486*n+33)    *a(n-4)
      -(4*n^3-24*n^2+39*n-2)              *a(n-5))/(4*n^3-36*n^2+99*n-69))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 27 2019

dtui[{},]:={{}};dtui[set:{i,___},n_]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s],n]]/@Table[{i,j},{j,Switch[i,1,Select[set,3<#i+2&]]}];
Table[Length[dtui[Range[n],n]],{n,0,12,2}]

a(n) is even <=> n in { A135042 }. - Alois P. Heinz, Feb 27 2019

a(10)-a(16) from Alois P. Heinz, Feb 26 2019

a(17)-a(21) from Alois P. Heinz, Feb 27 2019

A324324 MM-numbers of crossing set partitions.

Original entry on oeis.org

2117, 3973, 4843, 5891, 6757, 7181, 7801, 10019, 10063, 11051, 11567, 13021, 13193, 13459, 14123, 14921, 17603, 18407, 18761, 18877, 19307, 19633, 20941, 21083, 21251, 21457, 22849, 23519, 23533, 24727, 26101, 27133, 27169, 27173, 27413, 29111, 30479, 31261

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

A multiset multisystem is a finite multiset of finite multisets. 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 with MM-number n is formed by taking the multiset of prime indices of each part in the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset multisystem with MM-number 78 is {{},{1},{1,2}}.

A multiset multisystem is crossing if it contains two parts of the form {{...x...y...},{...z...t...}} with x < z < y < t or z < x < t < y.

Cf. A000108 (non-crossing set partitions), A001055, A001222, A003963, A005117, A016098 (crossing set partitions), A054726, A056239, A112798, A302242, A302243, A302505, A302521 (MM-numbers of set partitions).

Cf. A324166, A324167, A324169, A324170, A324171, A324326.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xTable[PrimePi[p],{k}]]]];
setptnQ[bks_]:=UnsameQ@@Join@@bks&&!MemberQ[bks,{}];
Select[Range[10000],And[croXQ[primeMS/@primeMS[#]],setptnQ[primeMS/@primeMS[#]]]&]

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

Original entry on oeis.org

1, 0, 1, 4, 12, 36, 108, 324

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.

Appears to be essentially the same as A003946.

			The a(2) = 1 through a(4) = 36 edge-sets:
  {12}  {12,13}     {12,13,14}
        {12,23}     {12,13,34}
        {13,23}     {12,14,34}
        {12,13,23}  {12,23,24}
                    {12,23,34}
                    {12,24,34}
                    {13,23,34}
                    {14,24,34}
                    {12,13,14,34}
                    {12,13,23,34}
                    {12,14,24,34}
                    {12,23,24,34}

Gus Wiseman, The a(5) = 36 connected graphs with no crossing or nesting edges.
Gus Wiseman, The a(6) = 108 connected graphs with no crossing or nesting edges.

Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
The case with only crossing edges forbidden is A007297.
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}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&!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

A324326 Number of crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 10, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 36, 0, 14, 0, 0, 0, 25, 0, 0, 0, 71, 0, 0, 0, 0, 0, 0, 0, 103, 0, 0, 0, 0, 0, 0, 0, 75

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...}} with x < z < y < t or z < x < t < y.

			The a(36) = 10 crossing multiset partitions of {1,1,2,2,3,4}:
  {{1,3},{1,2,2,4}}
  {{2,4},{1,1,2,3}}
  {{1,1,3},{2,2,4}}
  {{1,2,3},{1,2,4}}
  {{1},{1,3},{2,2,4}}
  {{1},{2,4},{1,2,3}}
  {{2},{1,3},{1,2,4}}
  {{2},{1,1,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1},{2},{1,3},{2,4}}

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

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

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]]}]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

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

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

Original entry on oeis.org

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A306386 Number of chord diagrams with n chords all having arc length at least 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A324324 MM-numbers of crossing set partitions.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

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

A324326 Number of crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs