|
| |
|
|
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
|
|
|
|
FORMULA
|
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
|
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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
