A134956 - OEIS

%I #19 May 22 2018 20:35:29

%S 1,2,8,64,880,17984,495296,17255424,728771584,36208782336,

%T 2069977144320,133869415030784,9664049202221056,770400218809384960,

%U 67219977066339008512,6372035504466437079040,652103070162164448952320,71656927837957783339925504

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

%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="/A134956/b134956.txt">Table of n, a(n) for n = 0..335</a>

%F Equals 2^n*A134954(n).

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

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

%e The a(2) = 8 hyperforests are the following:

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

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

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

%e   {{1,2}}

%e   {{1},{2}}

%e   {{1}}

%e   {{2}}

%e   {}

%e (End)

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

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

%Y Cf. A134958. - _Washington Bomfim_, Sep 25 2008

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

%K nonn

%O 0,2

%A _Don Knuth_, Jan 26 2008