

A134955


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


20



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 nonsingleton 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 induceddiamondfree chordal graphs.  Falk Hüffner, Jul 25 2019


REFERENCES

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


LINKS

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


FORMULA

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


EXAMPLE

From Gus Wiseman, May 20 2018: (Start)
Nonisomorphic 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}}
Nonisomorphic 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)


MAPLE

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(nj), j=1..n)/n) end end: b:= etr(B): c:= etr(b): B:= n> if n=0 then 0 else c(n1) fi: C:= etr(B): aa:= proc(n) option remember; B(n)+C(n) add(B(k)*C(nk), k=0..n) end: a:= etr(aa): seq(a(n), n=0..27); # Alois P. Heinz, Sep 09 2008


MATHEMATICA

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


PROG

(PARI) \\ 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))*(1x*Ser(u)))))} \\ Andrew Howroyd, May 22 2018


CROSSREFS

Cf. A030019, A035053 (hypertrees), A048143, A054921, A134954 (labeled case), A134955, A134957, A144959, A245566, A304716, A304717, A304867, A304911.
Sequence in context: A032289 A006648 A128496 * A171887 A027881 A002861
Adjacent sequences: A134952 A134953 A134954 * A134956 A134957 A134958


KEYWORD

nonn


AUTHOR

Don Knuth, Jan 26 2008


STATUS

approved



