A304717 -id:A304717 - cp's OEIS frontend

A134954 Number of "hyperforests" on n labeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

1, 1, 2, 8, 55, 562, 7739, 134808, 2846764, 70720278, 2021462055, 65365925308, 2359387012261, 94042995460130, 4102781803365418, 194459091322828280, 9950303194613104995, 546698973373090998382, 32101070021048906407183, 2006125858248695722280564

Offset: 0

Don Knuth, Jan 26 2008

nonn

The part of the name "assuming that each edge contains at least two vertices" is ambiguous. It may mean that not all n vertices have to be covered by some edge of the hypergraph, i.e., it is not necessarily a spanning hyperforest. However it is common to represent uncovered vertices as singleton edges, as in my example. - Gus Wiseman, May 20 2018

			From _Gus Wiseman_, May 20 2018: (Start)
The a(3) = 8 labeled spanning hyperforests are the following:
{{1,2,3}}
{{1,3},{2,3}}
{{1,2},{2,3}}
{{1,2},{1,3}}
{{3},{1,2}}
{{2},{1,3}}
{{1},{2,3}}
{{1},{2},{3}}
(End)

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H. - Washington Bomfim, Sep 25 2008

Alois P. Heinz, Table of n, a(n) for n = 0..370
N. J. A. Sloane, Transforms

Cf. A030019, A035053, A048143, A054921, A134955, A134956, A134957, A144959, A242817, A304716, A304717, A304867, A304911, A304912.

b:= proc(n) option remember; add(Stirling2(n-1,i) *n^(i-1), i=0..n-1) end: B:= proc(n) x-> add(b(k) *x^k/k!, k=0..n) end: a:= n-> coeff(series(exp(B(n)(x)), x, n+1), x,n) *n!: seq(a(n), n=0..30);  # Alois P. Heinz, Sep 09 2008

b[n_] := b[n] = Sum[StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; B[n_][x_] := Sum[b[k] *x^k/k!, {k, 0, n}]; a[0]=1; a[n_] := SeriesCoefficient[ Exp[B[n][x]], {x, 0, n}] *n!; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Exponential transform of A030019. - N. J. A. Sloane, Jan 30 2008
Binomial transform of A304911. - Gus Wiseman, May 20 2018
a(n) = Sum of n!*Product_{k=1..n} (A030019(k)/k!)^c_k / (c_k)! over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. - Washington Bomfim, Sep 25 2008
a(n) ~ exp((n+1)/LambertW(1)) * n^(n-2) / (sqrt(1+LambertW(1)) * exp(2*n+2) * (LambertW(1))^n). - Vaclav Kotesovec, Jul 26 2014

A134955 Number of "hyperforests" on n unlabeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 50, 128, 351, 1009, 3035, 9464, 30479, 100712, 340072, 1169296, 4082243, 14438577, 51643698, 186530851, 679530937, 2494433346, 9219028889, 34280914106, 128179985474, 481694091291, 1818516190252, 6894350122452

Offset: 0

Don Knuth, Jan 26 2008

nonn

A hyperforest is an antichain of finite nonempty sets (edges) whose connected components are hypertrees. It is spanning if all vertices are covered by some edge. However, it is common to represent uncovered vertices as singleton edges. For example, {{1,2},{1,4}} and {{3},{1,2},{1,4}} may represent the same hyperforest, the former being free of singletons (see example 2) and the latter being spanning (see example 1). This is different from a hyperforest with singleton edges allowed, which is one whose non-singleton edges only are required to form an antichain. For example, {{1},{2},{1,3},{2,3}} is a hyperforest with singleton edges allowed. - Gus Wiseman, May 22 2018

Equivalently, number of block graphs on n nodes, that is, graphs where every block is a complete graph. These graphs can be characterized as induced-diamond-free chordal graphs. - Falk Hüffner, Jul 25 2019

			From _Gus Wiseman_, May 20 2018: (Start)
Non-isomorphic representatives of the a(4) = 9 spanning hyperforests are the following:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{1,2},{3,4}}
  {{1,4},{2,3,4}}
  {{1},{2},{3,4}}
  {{1},{2,4},{3,4}}
  {{1,3},{2,4},{3,4}}
  {{1,4},{2,4},{3,4}}
  {{1},{2},{3},{4}}
Non-isomorphic representatives of the a(4) = 9 hyperforests spanning up to 4 vertices without singleton edges are the following:
  {}
  {{1,2}}
  {{1,2,3}}
  {{1,2,3,4}}
  {{1,2},{3,4}}
  {{1,3},{2,3}}
  {{1,4},{2,3,4}}
  {{1,3},{2,4},{3,4}}
  {{1,4},{2,4},{3,4}}
(End)

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H. - Washington Bomfim, Sep 25 2008

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
N. J. A. Sloane, Transforms
Wikipedia, Block graph

Cf. A030019, A035053 (hypertrees), A048143, A054921, A134954 (labeled case), A134955, A134957, A144959, A245566, A304716, A304717, A304867, A304911.

with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; `if`(n=0,1, add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n) end end: b:= etr(B): c:= etr(b): B:= n-> if n=0 then 0 else c(n-1) fi: C:= etr(B): aa:= proc(n) option remember; B(n)+C(n) -add(B(k)*C(n-k), k=0..n) end: a:= etr(aa): seq(a(n), n=0..27); # Alois P. Heinz, Sep 09 2008

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[B]; c = etr[b]; B[n_] := If[n == 0, 0, c[n-1]]; CC = etr[B]; aa[n_] := aa[n] = B[n]+CC[n]-Sum[B[k]*CC[n-k], {k, 0, n}]; a = etr[aa]; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz*)

\\ here b is A007563 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n)={my(v=[1]);for(i=2, n, v=concat([1], EulerT(EulerT(v)))); v}
seq(n)={my(u=b(n)); concat([1], EulerT(Vec(x*Ser(EulerT(u))*(1-x*Ser(u)))))} \\ Andrew Howroyd, May 22 2018

Euler transform of A035053. - N. J. A. Sloane, Jan 30 2008
a(n) = Sum of prod_{k=1}^n\,{A035053(k) + c_k -1 /choose c_k} over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. - Washington Bomfim, Sep 25 2008
a(n) ~ c * d^n / n^(5/2), where d = 4.189610958393826965527036454524... (see A245566), c = 0.36483930544... . - Vaclav Kotesovec, Jul 26 2014

A144959 A134955(n) - A134955(n-1). Number of hyperforests spanning n unlabeled nodes without isolated vertices.

Original entry on oeis.org

1, 0, 1, 2, 5, 11, 30, 78, 223, 658, 2026, 6429, 21015, 70233, 239360, 829224, 2912947, 10356334, 37205121, 134887153, 493000086, 1814902409, 6724595543, 25061885217, 93899071368, 353514105817, 1336822098961, 5075833932200

Offset: 0

Washington Bomfim, Sep 27 2008

nonn

a(n) is the number of hyperforests with n unlabeled nodes without isolated vertices. This follows from the fact that for n>0 A134955(n-1) counts the hyperforests of order n with one or more isolated nodes.

			From _Gus Wiseman_, May 21 2018: (Start)
Non-isomorphic representatives of the a(5) = 11 hyperforests are the following:
  {{1,2,3,4,5}}
  {{1,2},{3,4,5}}
  {{1,5},{2,3,4,5}}
  {{1,2,5},{3,4,5}}
  {{1,2},{2,5},{3,4,5}}
  {{1,2},{3,5},{4,5}}
  {{1,4},{2,5},{3,4,5}}
  {{1,5},{2,5},{3,4,5}}
  {{1,3},{2,4},{3,5},{4,5}}
  {{1,4},{2,5},{3,5},{4,5}}
  {{1,5},{2,5},{3,5},{4,5}}
(End)

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A144958 (unlabeled forests without isolated vertices), A144959, A304716, A304717, A304867, A304911.

etr[p_] := etr[p] = Module[{b}, b[n_] := b[n] = If[n==0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; b];
b[0] = 0; b[n_] := b[n] = etr[etr[b]][n-1];
c[1] = 0; c[n_] := b[n] + etr[b][n] - Sum[b[k]*etr[b][n-k], {k, 0, n}];
a = etr[c];
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jul 12 2018, after Alois P. Heinz's code for A035053 *)

\\ here b is A007563 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n)={my(v=[1]);for(i=2, n, v=concat([1], EulerT(EulerT(v)))); v}
seq(n)={my(u=b(n)); concat([1], EulerT(concat([0], Vec(Ser(EulerT(u))*(1-x*Ser(u))-1))))} \\ Andrew Howroyd, May 22 2018

Euler transform of b(1) = 0, b(n > 1) = A035053(n). - Gus Wiseman, May 21 2018

A304911 Number of labeled hyperforests spanning n vertices without singleton edges.

Original entry on oeis.org

1, 0, 1, 4, 32, 351, 5057, 90756, 1956971, 49366904, 1427680932, 46590895869, 1694163054597, 67938488277050, 2978980898086377, 141801848209013050, 7282651452378019772, 401410357608479625207, 23635996827115264290005

Offset: 0

Gus Wiseman, May 20 2018

nonn

			The a(3) = 4 hyperforests are {{1,2,3}}, {{1,3},{2,3}}, {{1,2},{2,3}}, {{1,2},{1,3}}.

Cf. A006126, A030019, A035053, A048143, A054921, A134954, A134955, A134957, A144959, A293993, A293994, A304716, A304717, A304867.

E.g.f.: exp(A030019(x) - x - 1) where A030019(x) is the e.g.f. of A030019.

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Original entry on oeis.org

1, 2, 8, 64, 880, 17984, 495296, 17255424, 728771584, 36208782336, 2069977144320, 133869415030784, 9664049202221056, 770400218809384960, 67219977066339008512, 6372035504466437079040, 652103070162164448952320, 71656927837957783339925504

Offset: 0

Don Knuth, Jan 26 2008

nonn

			From _Gus Wiseman_, May 21 2018: (Start)
The a(2) = 8 hyperforests are the following:
  {{1},{2},{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1,2}}
  {{1},{2}}
  {{1}}
  {{2}}
  {}
(End)

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H. - Washington Bomfim, Sep 25 2008

Alois P. Heinz, Table of n, a(n) for n = 0..335

Cf. A134958. - Washington Bomfim, Sep 25 2008

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A144959, A304716, A304717, A304867, A304911.

with(combinat): p:= proc(n) option remember; add(stirling2(n-1, i) *n^(i-1), i=0..n-1) end: g:= proc(n) option remember; p(n) +add(binomial(n-1, k-1) *p(k) *g(n-k), k=1..n-1) end: a:= n-> `if`(n=0, 1, 2^n * g(n)): seq(a(n), n=0..30); # Alois P. Heinz, Oct 07 2008

p[n_] := p[n] = Sum[ StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; g[n_] := g[n] = p[n] + Sum[Binomial[n-1, k-1]*p[k]*g[n-k], {k, 1, n-1}]; a[n_] := If[n == 0, 1, 2^n* g[n]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Equals 2^n*A134954(n).

a(n) = Sum of n!prod_{k=1}^n\{ frac{ A134958(k)^{c_k} }{ k!^{c_k} c_k! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. - Washington Bomfim, Sep 25 2008

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.

A317632 Number of connected induced nonempty non-singleton subgraphs of labeled connected graphs with n vertices.

Original entry on oeis.org

0, 0, 1, 13, 294, 12198, 946712, 140168924, 40223263760, 22598607583376, 24999757695984960, 54630901092648916704, 236304498092496715916416, 2026201628540583716863002880, 34482826679730591694177065948928, 1166004710785628820717860509317415168

Offset: 0

Gus Wiseman, Aug 02 2018

nonn

The edges of an induced subgraph G|S are those edges of G with both ends contained in S, where S is a subset of the vertices.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, All 294 connected induced subgraphs of labeled connected graphs with 4 vertices.

Cf. A001187, A006125, A048143, A293510, A304717, A317631, A317634, A317635.

seq(n)={
  my(p=sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n)));
  my(g=Vec(serlaplace(log(p))));
  my(q=sum(k=0, n, sum(j=2, k, binomial(k,j)*g[j]*2^(binomial(k-j, 2) + j*(k-j)))*x^k/k!, O(x*x^n)));
  Vec(serlaplace(q/p), -n-1)
} \\ Andrew Howroyd, Dec 10 2018

a(6) from Gus Wiseman, Dec 10 2018

Terms a(7) and beyond from Andrew Howroyd, Dec 10 2018

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

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Original entry on oeis.org

1, 2, 5, 15, 50, 200, 907, 4607, 25077, 144337, 863678, 5329994, 33697112, 217317986, 1424880997, 9474795661, 63769947778, 433751273356, 2977769238994, 20611559781972, 143720352656500, 1008765712435162, 7122806053951140, 50566532826530292, 360761703055959592

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(3) = 15 hypertrees are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{1,3},{2,3}}
  {{3},{1,2,3}}
  {{1},{2},{1,2}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{2},{3},{1,2},{1,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A134959, A144959, A304386, A304717, A304867, A304911, A304912, A304968, A304970.

\\ here b(n) is A318494 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(2*v)))); v}
seq(n)={my(u=2*b(n)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of b(1) = 1, b(n) = A134959(n) otherwise.

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

cp's OEIS Frontend

A134954 Number of "hyperforests" on n labeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A134955 Number of "hyperforests" on n unlabeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A144959 A134955(n) - A134955(n-1). Number of hyperforests spanning n unlabeled nodes without isolated vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A304911 Number of labeled hyperforests spanning n vertices without singleton edges.

Views

Author

Keywords

Examples

Crossrefs

Formula

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A317632 Number of connected induced nonempty non-singleton subgraphs of labeled connected graphs with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs