A136653 -id:A136653 - cp's OEIS frontend

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 5, 0, 0, 0, 0, 1, 16, 4, 0, 0, 0, 0, 1, 42, 42, 0, 0, 0, 0, 0, 1, 99, 258, 27, 0, 0, 0, 0, 0, 1, 219, 1222, 465, 0, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 22 2019

A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y.

			Triangle begins:
    1
    0    1
    0    1    0
    0    1    0    0
    0    1    1    0    0
    0    1    5    0    0    0
    0    1   16    4    0    0    0
    0    1   42   42    0    0    0    0
    0    1   99  258   27    0    0    0    0
    0    1  219 1222  465    0    0    0    0    0
Row n = 6 counts the following set partitions:
  {{123456}}  {{1235}{46}}  {{13}{25}{46}}
              {{124}{356}}  {{14}{25}{36}}
              {{1245}{36}}  {{14}{26}{35}}
              {{1246}{35}}  {{15}{24}{36}}
              {{125}{346}}
              {{13}{2456}}
              {{134}{256}}
              {{1345}{26}}
              {{1346}{25}}
              {{135}{246}}
              {{1356}{24}}
              {{136}{245}}
              {{14}{2356}}
              {{145}{236}}
              {{146}{235}}
              {{15}{2346}}

Row sums are A099947. Row k = 2 is A002662.
Cf. A000108, A000110, A001263, A016098, A136653, A268814, A268815, A306438, A324011.
Cf. A324166, A324172, A324173, A324327, A324328.

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[#]]<=1&&Length[#]==k&]],{n,0,6},{k,0,n}]

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

Original entry on oeis.org

1, 1, 2, 7, 48, 781, 27518

Offset: 0

Gus Wiseman, Jun 29 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) = 48 weakly nesting-connected graphs.

The inverse binomial transform is the covering case A326337.
The non-weak case is A326330.
Cf. A006125, A099947, A136653, A324328, A326289, A326293, A326331, A326335, A326336, A326341.

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

A136652 L.g.f.: A(x) = log( Sum_{n>=0} 2^[n(n-1)/2]*x^n ).

Original entry on oeis.org

1, 3, 19, 223, 4771, 190023, 14441659, 2130394591, 616038609331, 351153716973303, 395928966997611499, 885010943452285951183, 3928049212346654960720611, 34658088824057172975437120103, 608435145369338712372672919898779, 21266998855813018955669706360248449471

Offset: 1

Paul D. Hanna, Jan 15 2008

nonn

			L.g.f.: A(x) = x + 3*x^2/2 + 19*x^3/3 + 223*x^4/4 + 4771*x^5/5 +...
A(x) = log(1 + x + 2x^2 + 8x^3 + 64x^4 + 1024x^5 +...+ 2^(n(n-1)/2)*x^n +...).

Vincenzo Librandi, Table of n, a(n) for n = 1..80

Cf. A136653, A136654.

max = 14; s = Log[Sum[2^(k*(k-1)/2)*x^k, {k, 0, max}]] + O[x]^(max+1); CoefficientList[s, x]*Range[0, max] // Rest (* Jean-François Alcover, Sep 03 2017 *)

a(n)=n*polcoeff(log(sum(k=0,n,2^(k*(k-1)/2)*x^k +x*O(x^n))),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}]

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

Original entry on oeis.org

1, 1, 3, 15, 117, 1565, 41663, 2378147, 286991465, 71261033273, 35889915535835, 36421251158141399, 74222529448186797341, 303194457634544530959125, 2480120130065258782050157847, 40601998283406419045206334661611

Offset: 0

Paul D. Hanna, Jan 15 2008

nonn

			G.f.: A(x) = 1 + x + 3*x^2 + 15*x^3 + 117*x^4 + 1565*x^5 + 41663*x^6 +...
Let F(x) = 1 + x + 2x^2 + 8x^3 + 64x^4 + 1024x^5 +...+ 2^(n(n-1)/2)*x^n +..
then A(x) = F(x*A(x)), A(x/F(x)) = F(x).
a(n) = coefficient of x^n in F(x)^(n+1)/(n+1),
as can be seen by the main diagonal in the array of
coefficients in the initial powers of F(x):
F^1: [(1), 1, 2, 8, 64, 1024, 32768, 2097152, 268435456,...;
F^2: [1, (2), 5, 20, 148, 2208, 67904, 4264960, 541216768,...;
F^3: [1, 3, (9), 37, 258, 3588, 105704, 6507552, 818458752,...;
F^4: [1, 4, 14, (60), 401, 5208, 146520, 8829536, 1100282640,...;
F^5: [1, 5, 20, 90, (585), 7121, 190770, 11236080, 1386816800,...;
F^6: [1, 6, 27, 128, 819, (9390), 238949, 13733004, 1678197564,...;
F^7: [1, 7, 35, 175, 1113, 12089, (291641), 16326885, 1974570178,...;
F^8: [1, 8, 44, 232, 1478, 15304, 349532, (19025176), 2276089889,...;
F^9: [1, 9, 54, 300, 1926, 19134, 413424, 21836340, (2582923185),...;
dividing each diagonal term in row n by (n+1) gives a(n) for n>=0.
The diagonal above the main diagonal gives coefficients of l.g.f.:
log(A(x)) = x + 5*x^2/2 + 37*x^3/3 + 401*x^4/4 + 7121*x^5/5 +...

Cf. A136653.

max = 15; s = x/Sum[2^(k*(k-1)/2)*x^k, {k, 0, max}] + O[x]^(max+2);(1/x)*InverseSeries[s] + O[x]^(max+1) // CoefficientList[#, x]& (* Jean-François Alcover, Sep 03 2017 *)

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

a(n) = coefficient of x^n in [Sum_{k=0..n} 2^(k(k-1)/2)*x^k]^(n+1)/(n+1).

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

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

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A136652 L.g.f.: A(x) = log( Sum_{n>=0} 2^[n(n-1)/2]*x^n ).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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