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.

%I A134954 #42 May 22 2018 20:35:56
%S A134954 1,1,2,8,55,562,7739,134808,2846764,70720278,2021462055,65365925308,
%T A134954 2359387012261,94042995460130,4102781803365418,194459091322828280,
%U A134954 9950303194613104995,546698973373090998382,32101070021048906407183,2006125858248695722280564
%N A134954 Number of "hyperforests" on n labeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.
%C A134954 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 A134954 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 A134954 Alois P. Heinz, <a href="/A134954/b134954.txt">Table of n, a(n) for n = 0..370</a>
%H A134954 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F A134954 Exponential transform of A030019. - _N. J. A. Sloane_, Jan 30 2008
%F A134954 Binomial transform of A304911. - _Gus Wiseman_, May 20 2018
%F A134954 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 A134954 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 A134954 From _Gus Wiseman_, May 20 2018: (Start)
%e A134954 The a(3) = 8 labeled spanning hyperforests are the following:
%e A134954 {{1,2,3}}
%e A134954 {{1,3},{2,3}}
%e A134954 {{1,2},{2,3}}
%e A134954 {{1,2},{1,3}}
%e A134954 {{3},{1,2}}
%e A134954 {{2},{1,3}}
%e A134954 {{1},{2,3}}
%e A134954 {{1},{2},{3}}
%e A134954 (End)
%p A134954 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 A134954 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 A134954 Cf. A030019, A035053, A048143, A054921, A134955, A134956, A134957, A144959, A242817, A304716, A304717, A304867, A304911, A304912.
%K A134954 nonn
%O A134954 0,3
%A A134954 _Don Knuth_, Jan 26 2008