A134954 - OEIS

%I #42 May 22 2018 20:35:56

%S 1,1,2,8,55,562,7739,134808,2846764,70720278,2021462055,65365925308,

%T 2359387012261,94042995460130,4102781803365418,194459091322828280,

%U 9950303194613104995,546698973373090998382,32101070021048906407183,2006125858248695722280564

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

%C 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

%D 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

%H Alois P. Heinz, <a href="/A134954/b134954.txt">Table of n, a(n) for n = 0..370</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%F Exponential transform of A030019. - _N. J. A. Sloane_, Jan 30 2008

%F Binomial transform of A304911. - _Gus Wiseman_, May 20 2018

%F 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

%F 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

%e From _Gus Wiseman_, May 20 2018: (Start)

%e The a(3) = 8 labeled spanning hyperforests are the following:

%e {{1,2,3}}

%e {{1,3},{2,3}}

%e {{1,2},{2,3}}

%e {{1,2},{1,3}}

%e {{3},{1,2}}

%e {{2},{1,3}}

%e {{1},{2,3}}

%e {{1},{2},{3}}

%e (End)

%p 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

%t 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_ *)

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

%K nonn

%O 0,3

%A _Don Knuth_, Jan 26 2008