A317632 -id:A317632 - cp's OEIS frontend

A317672 Regular triangle where T(n,k) is the number of clutters (connected antichains) on n + 1 vertices with k maximal blobs (2-connected components).

1, 2, 3, 44, 24, 16, 4983, 940, 300, 125, 7565342, 154770, 18000, 4320, 1296, 2414249587694, 318926314, 3927105, 363580, 72030, 16807, 56130437054842366160898, 135200580256336, 10244647168, 99187200, 8028160, 1376256, 262144

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        2       3
       44      24      16
     4983     940     300     125
  7565342  154770   18000    4320    1296

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Row sums are A048143. First column is A275307. Last column is A030019.

Cf. A000272, A001187, A002218, A013922, A134954, A293510, A317631, A317632, A317634, A317635, A317671.

blg={0,1,2,44,4983,7565342,2414249587694,56130437054842366160898} (* A275307 *);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[n^(k-1)*Product[blg[[Length[s]+1]],{s,spn}],{spn,Select[sps[Range[n-1]],Length[#]==k&]}],{n,Length[blg]},{k,n-1}]

A317631 Number of connected set partitions of the vertices of labeled graphs with n vertices.

Original entry on oeis.org

1, 1, 1, 8, 200, 15901

Offset: 0

Gus Wiseman, Aug 02 2018

Gus Wiseman, All 200 connected set partitions of labeled graphs with 4 vertices.

Cf. A000110, A001187, A006125, A048143, A293510, A304717, A317632, A317634, A317635.

A317634 Number of caps (also clutter partitions) of clutters (connected antichains) spanning n vertices.

Original entry on oeis.org

1, 0, 1, 9, 315, 64880

Offset: 0

Gus Wiseman, Aug 02 2018

A kernel of a clutter is the restriction of the edge set to all edges contained within some connected vertex set. A clutter partition is a set partition of the edge set using kernels.

			The a(3) = 9 clutter partitions:
  {{{1,2,3}}}
  {{{1,3},{2,3}}}
  {{{1,2},{2,3}}}
  {{{1,2},{1,3}}}
  {{{1,3}},{{2,3}}}
  {{{1,2}},{{2,3}}}
  {{{1,2}},{{1,3}}}
  {{{1,2},{1,3},{2,3}}}
  {{{1,2}},{{1,3}},{{2,3}}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.
Gus Wiseman, All clutter partitions of non-isomorphic clutters on 4 vertices.

Cf. A001187, A030019, A048143, A275307, A286520,, A293510, A304717, A317631, A317632, A317635.

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Original entry on oeis.org

1, 1, 2, 6, 20, 103, 759

Offset: 1

Gus Wiseman, Nov 21 2018

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions p of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).

			The a(4) = 6 connected chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                    m(1111)
           m(211) + m(1111)
          2m(211) + m(1111)
  m(22) + 2m(211) + m(1111)
  m(22) + 3m(211) + m(1111)
  m(31) + 3m(211) + m(1111)

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Gus Wiseman, A partition of connected graphs, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].

First differs from A079457 at a(7) = 759, A079457(7) = 706.

Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[chromSF/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,6}]

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

Original entry on oeis.org

1, 0, 1, 14, 486, 71428

Offset: 0

Gus Wiseman, Aug 02 2018

A connected vertex set in a clutter is any union of a connected subset of the edges.

			There are four connected vertex sets of {{1,2},{1,3},{2,3}}, namely {1,2,3}, {1,2}, {1,3}, {2,3}; there are three connected vertex sets of {{1,2},{1,3}}, {{1,2},{2,3}}, and {{1,3},{2,3}} each; and there is one connected vertex set of {{1,2,3}}. So we have a total of a(3) = 4 + 3 * 3 + 1 = 14 connected vertex sets.

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A001187, A006126, A030019, A048143, A134954, A275307, A286520, A293510, A304717, A317631, A317632, A317634.

nn=5;
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],multijoin@@s[[c[[1]]]]]]]]];
clutQ[eds_]:=And[UnsameQ@@eds,!Apply[Or,Outer[#1=!=#2&&Complement[#1,#2]=={}&,eds,eds,1],{0,1}],Length[csm[eds]]==1];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
swell[c_]:=Union@@FixedPointList[Union[ReplaceList[#1,{_,a:{_,x_,_},_,b:{_,x_,_},_}:>Union[a,b]]]&,c]
Table[Sum[Length[swell[c]],{c,Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Complement[#1,#2]=={}&],And[Union@@#==Range[n],clutQ[#]]&]}],{n,nn}]

A318697 Number of ways to partition a hypertree spanning n vertices into hypertrees.

Original entry on oeis.org

1, 1, 7, 93, 1856, 49753, 1679441, 68463769, 3273695758, 179710285011, 11141016392749, 769939840667473, 58695964339179805, 4893452980658819151, 442915168219228586581, 43255083632741702266097, 4533695508041747494704359, 507638249638364368312476913

Offset: 1

Gus Wiseman, Aug 31 2018

nonn

			The a(3) = 7 hypertree partitions:
  {{{1,2,3}}}
  {{{1,2},{1,3}}}
  {{{1,2},{2,3}}}
  {{{1,3},{2,3}}}
  {{{1,2}},{{1,3}}}
  {{{1,2}},{{2,3}}}
  {{{1,3}},{{2,3}}}

Cf. A000272, A030019, A048143, A134954, A275307, A317631, A317632, A317634, A317635, A317677.

trct[n_]:=Sum[StirlingS2[n-1,i]*n^(i-1),{i,0,n-1}];
numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
Table[Sum[n^(Length[ptn]-1)*Product[trct[s+1],{s,ptn}]*numSetPtnsOfType[ptn],{ptn,IntegerPartitions[n-1]}],{n,20}]

A125702 Number of connected categories with n objects and 2n-1 morphisms.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 22, 42, 94, 203, 470, 1082, 2602, 6270, 15482, 38525, 97258, 247448, 635910, 1645411, 4289010, 11245670, 29656148, 78595028, 209273780, 559574414, 1502130920, 4046853091, 10939133170, 29661655793

Offset: 1

Franklin T. Adams-Watters and Christian G. Bower, Jan 05 2007

nonn

Also number of connected antitransitive relations on n objects (antitransitive meaning a R b and b R c implies not a R c); equivalently, number of free oriented bipartite trees, with all arrows going from one part to the other part.

Also the number of non-isomorphic multi-hypertrees of weight n - 1 with singletons allowed. A multi-hypertree with singletons allowed is a connected set multipartition (multiset of sets) with density -1, where the density of a set multipartition is the weight (sum of sizes of the parts) minus the number of parts minus the number of vertices. - Gus Wiseman, Oct 30 2018

			From _Gus Wiseman_, Oct 30 2018: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(6) = 10 multi-hypertrees of weight n - 1 with singletons allowed:
  {}  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
             {{1}{1}}  {{2}{12}}    {{13}{23}}      {{14}{234}}
                       {{1}{1}{1}}  {{3}{123}}      {{4}{1234}}
                                    {{1}{2}{12}}    {{2}{13}{23}}
                                    {{2}{2}{12}}    {{2}{3}{123}}
                                    {{1}{1}{1}{1}}  {{3}{13}{23}}
                                                    {{3}{3}{123}}
                                                    {{1}{2}{2}{12}}
                                                    {{2}{2}{2}{12}}
                                                    {{1}{1}{1}{1}{1}}
(End)

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

Same as A122086 except for n = 1; see there for formulas. Cf. A125699.

Cf. A000081, A000272, A007716, A007717, A030019, A052888, A134954, A317631, A317632, A318697, A320921, A321155.

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={Vec(2*TreeGf(n) - TreeGf(n)^2 - x)} \\ Andrew Howroyd, Nov 02 2019

a(n) = A122086(n) for n > 1.

G.f.: 2*f(x) - f(x)^2 - x where f(x) is the g.f. of A000081. - Andrew Howroyd, Nov 02 2019

A317677 Fixed point of a shifted hypertree transform.

Original entry on oeis.org

1, 1, 4, 32, 402, 7038, 160114, 4522578, 153640590, 6132546770, 282517271694, 14812447505646, 873934551644074, 57486823088667270, 4183353479821220130, 334572221351085006242, 29242220614539638127294, 2779426070382982579163202, 286058737295150226682469518

Offset: 1

Gus Wiseman, Aug 04 2018

The hypertree transform H(a) of a sequence a is given by H(a)(n) = Sum_p n^(k-1) Prod_i a(|p_i|+1), where the sum is over all set partitions U(p_1, ..., p_k) = {1, ..., n-1}.

Alois P. Heinz, Table of n, a(n) for n = 1..305

Cf. A000272, A030019, A048143, A134954, A275307, A293510, A317631, A317632, A317634, A317635, A317671.

b:= proc(n, k) option remember; `if`(n=0, 1/k, add(
      a(j)*b(n-j, k)*binomial(n-1, j-1)*k, j=1..n))
    end:
a:= n-> b(n-1, n):
seq(a(n), n=1..20);  # Alois P. Heinz, Aug 21 2019

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
a[n_]:=a[n]=Sum[n^(Length[ptn]-1)*numSetPtnsOfType[ptn]*Product[a[s],{s,ptn}],{ptn,IntegerPartitions[n-1]}];
Array[a,20]
(* Second program: *)
b[n_, k_] := b[n, k] = If[n == 0, 1/k, Sum[
     a[j]*b[n - j, k]*Binomial[n - 1, j - 1]*k, {j, 1, n}]];
a[n_] := b[n - 1, n];
Array[a, 20] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A317671 Regular triangle where T(n,k) is the number of labeled connected graphs on n + 1 vertices with k maximal blobs (2-connected components).

Original entry on oeis.org

1, 1, 3, 10, 12, 16, 238, 215, 150, 125, 11368, 7740, 4140, 2160, 1296, 1014888, 509446, 205065, 84035, 36015, 16807, 166537616, 59409952, 17393152, 5393920, 1863680, 688128, 262144, 50680432112, 12321597708, 2516756508, 563570217, 148803480, 45467730

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        1       3
       10      12      16
      238     215     150     125
    11368    7740    4140    2160    1296
  1014888  509446  205065   84035   36015   16807

Row sums are A001187. First column is A013922. Last column is A000272.

Cf. A002218, A030019, A048143, A134954, A275307, A293510, A317631, A317632, A317634, A317635, A317672, A317677.

blg={0,1,1,10,238,11368,1014888,166537616,50680432112,29107809374336} (*A013922*);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[n^(k-1)*Product[blg[[Length[s]+1]],{s,spn}],{spn,Select[sps[Range[n-1]],Length[#]==k&]}],{n,Length[blg]},{k,n-1}]

cp's OEIS Frontend

A317672 Regular triangle where T(n,k) is the number of clutters (connected antichains) on n + 1 vertices with k maximal blobs (2-connected components).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A317631 Number of connected set partitions of the vertices of labeled graphs with n vertices.

Views

Author

Keywords

Links

Crossrefs

A317634 Number of caps (also clutter partitions) of clutters (connected antichains) spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A318697 Number of ways to partition a hypertree spanning n vertices into hypertrees.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A125702 Number of connected categories with n objects and 2n-1 morphisms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A317677 Fixed point of a shifted hypertree transform.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A317671 Regular triangle where T(n,k) is the number of labeled connected graphs on n + 1 vertices with k maximal blobs (2-connected components).

Views

Author

Keywords

Examples

Crossrefs

Programs