A099947 -id:A099947 - cp's OEIS frontend

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

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.

A326248 Number of crossing, nesting set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 28, 252, 1890, 13020, 86564, 571944, 3826230, 26233662, 185746860, 1364083084, 10410773076, 82609104802, 681130756224, 5829231836494, 51711093240518, 474821049202852, 4506533206814480, 44151320870760216, 445956292457725714

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

A set partition is crossing if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < y < t or z < x < t < y, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t.

			The a(5) = 2 set partitions:
  {{1,4},{2,3,5}}
  {{1,3,4},{2,5}}

Christian Sievers, Table of n, a(n) for n = 0..576

Crossing and nesting set partitions are (both) A016098.
Crossing, capturing set partitions are A326246.
Nesting, non-crossing set partitions are A122880.
Cf. A000108, A000110, A001519, A058681, A099947, A117662, A324170.
Cf. A326209, A326211, A326243, A326245, A326256, A326258.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;x_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;x

a(n) = A000110(n) - 2*A000108(n) + A001519(n). - Christian Sievers, Oct 16 2024

a(11) and beyond from Christian Sievers, Oct 16 2024

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

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.

			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.

A122880 Catalan numbers minus odd-indexed Fibonacci numbers.

Original entry on oeis.org

0, 0, 0, 1, 8, 43, 196, 820, 3265, 12615, 47840, 179355, 667875, 2478022, 9180616, 34011401, 126120212, 468411235, 1743105373, 6500874434, 24300686879, 91049069203, 341924710480, 1286932932251, 4854167659403, 18346988061078

Offset: 1

Gary W. Adamson, Sep 16 2006

nonn

From Emeric Deutsch, Aug 21 2008: (Start)
Number of Dyck paths of height at least 4 and of semilength n. Example: a(5)=8 because we have UUUUUDDDDD, UUUUDUDDDD, UUUDUUDDDD, UUDUUUDDDD, UDUUUUDDDD and the reflection of the last three in a vertical axis.
Number of ordered trees of height at least 4 and having n edges. (End)
From Gus Wiseman, Jun 22 2019: (Start)
Also the number of non-crossing, capturing set partitions of {1..n}. A set partition is crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y, and capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z and y > t or x > z and y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(4) = 1 and a(5) = 8 non-crossing, capturing set partitions are:
  {{1,4},{2,3}}  {{1,2,5},{3,4}}
                 {{1,4,5},{2,3}}
                 {{1,5},{2,3,4}}
                 {{1},{2,5},{3,4}}
                 {{1,4},{2,3},{5}}
                 {{1,5},{2},{3,4}}
                 {{1,5},{2,3},{4}}
                 {{1,5},{2,4},{3}}
(End)

			a(5) = 8 = A000108(5) - A001519(5) = 42 - 34.

E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325. [_Emeric Deutsch_, Aug 21 2008]

Cf. A000108, A001519, A122881.
Non-crossing set partitions are A000108.
Capturing set partitions are A326243.
Crossing, not capturing set partitions are A326245.
Crossing, capturing set partitions are A326246.
Cf. A000110, A054391, A099947, A326255, A326259.

with(combinat): seq(binomial(2*n,n)/(n+1)-fibonacci(2*n-1), n=1..27); # Emeric Deutsch, Aug 21 2008

With[{nn=30},#[[1]]-#[[2]]&/@Thread[{CatalanNumber[Range[nn]], Fibonacci[ Range[ 1,2nn,2]]}]] (* Harvey P. Dale, Nov 07 2016 *)

A000108(n) - A001519(n), n > 0; A000108 = Catalan numbers, A001519 = odd-indexed Fibonacci numbers.

More terms from Emeric Deutsch, Aug 21 2008

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

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

A326246 Number of crossing, capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 37, 307, 2173, 14344, 92402, 596688

Offset: 0

Gus Wiseman, Jun 20 2019

A set partition is crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y, and capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The a(5) = 3 set partitions:
  {{1,3,4},{2,5}}
  {{1,3,5},{2,4}}
  {{1,4},{2,3,5}}

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

MM-numbers of crossing, capturing multiset partitions are A326259.
Crossing set partitions are A016098.
Capturing set partitions are A326243.
Crossing, nesting set partitions are A326248.
Crossing, non-capturing set partitions are A326245.
Non-crossing, capturing set partitions are A122880 (conjecture).
Cf. A000108, A000110, A058681, A099947, A324170, A326211, A326249, A054391, A326255.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A326249 Number of capturing set partitions of {1..n} that are not nesting.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 9, 55, 283, 1324, 5838, 24744

Offset: 0

Gus Wiseman, Jun 20 2019

Capturing is a weaker condition than nesting. A set partition is capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t. For example, {{1,3,5},{2,4}} is capturing but not nesting, so is counted under a(5).

			The a(6) = 9 set partitions:
  {{1},{2,4,6},{3,5}}
  {{1,3,5},{2,4},{6}}
  {{1,3,6},{2,4},{5}}
  {{1,3,6},{2,5},{4}}
  {{1,4,6},{2},{3,5}}
  {{1,4,6},{2,5},{3}}
  {{1,3,5},{2,4,6}}
  {{1,2,4,6},{3,5}}
  {{1,3,5,6},{2,4}}

MM-numbers of capturing, non-nesting multiset partitions are A326260.
Nesting set partitions are A016098.
Capturing set partitions are A326243.
Non-crossing, nesting set partitions are A122880 (conjectured).
Cf. A000110, A054391, A058681, A095661, A099947.
Cf. A326212, A326237, A326245, A326246, A054391, A326255, A326256.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;x

A326330 Number of simple graphs with vertices {1..n} whose nesting edges are connected.

Original entry on oeis.org

1, 1, 2, 4, 8, 30, 654

Offset: 0

Gus Wiseman, Jun 27 2019

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

Gus Wiseman, The a(5) = 30 nesting-connected simple graphs.

The covering case is the inverse binomial transform A326331.
Graphs whose crossing edges are connected are A324328.
Cf. A006125, A007297, A054726, A099947, A117662, A136653, A324328.
Cf. A326210, A326293, A326335, A326336, A326337, A326338, A326339.

nesXQ[stn_]:=MatchQ[stn,{_,{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}]],Length[nestcmpts[#]]<=1&]],{n,0,5}]

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326248 Number of crossing, nesting set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A122880 Catalan numbers minus odd-indexed Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A326246 Number of crossing, capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326249 Number of capturing set partitions of {1..n} that are not nesting.