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!)
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^(n-2) / (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(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

MATHEMATICA

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

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

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 February 26 12:43 EST 2020. Contains 332280 sequences. (Running on oeis4.)