

A134954


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


40



1, 1, 2, 8, 55, 562, 7739, 134808, 2846764, 70720278, 2021462055, 65365925308, 2359387012261, 94042995460130, 4102781803365418, 194459091322828280, 9950303194613104995, 546698973373090998382, 32101070021048906407183, 2006125858248695722280564
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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


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..370
N. J. A. Sloane, Transforms


FORMULA

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^(n2) / (sqrt(1+LambertW(1)) * exp(2*n+2) * (LambertW(1))^n).  Vaclav Kotesovec, Jul 26 2014


EXAMPLE

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)


MAPLE

b:= proc(n) option remember; add(Stirling2(n1, i) *n^(i1), i=0..n1) 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


MATHEMATICA

b[n_] := b[n] = Sum[StirlingS2[n1, i]*n^(i1), {i, 0, n1}]; 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}] (* JeanFrançois Alcover, Feb 13 2015, after Alois P. Heinz *)


CROSSREFS

Cf. A030019, A035053, A048143, A054921, A134955, A134956, A134957, A144959, A242817, A304716, A304717, A304867, A304911, A304912.
Sequence in context: A005440 A183282 A139016 * A087422 A081667 A117496
Adjacent sequences: A134951 A134952 A134953 * A134955 A134956 A134957


KEYWORD

nonn


AUTHOR

Don Knuth, Jan 26 2008


STATUS

approved



