login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges). 12
1, 2, 8, 64, 880, 17984, 495296, 17255424, 728771584, 36208782336, 2069977144320, 133869415030784, 9664049202221056, 770400218809384960, 67219977066339008512, 6372035504466437079040, 652103070162164448952320, 71656927837957783339925504 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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..335

FORMULA

Equals 2^n*A134954(n).

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

EXAMPLE

From Gus Wiseman, May 21 2018: (Start)

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

  {{1},{2},{1,2}}

  {{1},{1,2}}

  {{2},{1,2}}

  {{1,2}}

  {{1},{2}}

  {{1}}

  {{2}}

  {}

(End)

MAPLE

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

MATHEMATICA

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 *)

CROSSREFS

Cf. A134958. - Washington Bomfim, Sep 25 2008

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

Sequence in context: A153531 A153560 A321059 * A011803 A007625 A085658

Adjacent sequences:  A134953 A134954 A134955 * A134957 A134958 A134959

KEYWORD

nonn

AUTHOR

Don Knuth, Jan 26 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 29 08:04 EST 2020. Contains 331337 sequences. (Running on oeis4.)