login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A134955 Number of "hyperforests" on n unlabeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices. 20
1, 1, 2, 4, 9, 20, 50, 128, 351, 1009, 3035, 9464, 30479, 100712, 340072, 1169296, 4082243, 14438577, 51643698, 186530851, 679530937, 2494433346, 9219028889, 34280914106, 128179985474, 481694091291, 1818516190252, 6894350122452 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A hyperforest is an antichain of finite nonempty sets (edges) whose connected components are hypertrees. It is spanning if all vertices are covered by some edge. However, it is common to represent uncovered vertices as singleton edges. For example, {{1,2},{1,4}} and {{3},{1,2},{1,4}} may represent the same hyperforest, the former being free of singletons (see example 2) and the latter being spanning (see example 1). This is different from a hyperforest with singleton edges allowed, which is one whose non-singleton edges only are required to form an antichain. For example, {{1},{2},{1,3},{2,3}} is a hyperforest with singleton edges allowed. - Gus Wiseman, May 22 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..1000 (first 201 terms from T. D. Noe)

N. J. A. Sloane, Transforms

FORMULA

Euler transform of A035053. - N. J. A. Sloane, Jan 30 2008

a(n) = Sum of prod_{k=1}^n\,{A035053(k) + c_k -1 /choose 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) ~ c * d^n / n^(5/2), where d = 4.189610958393826965527036454524... (see A245566), c = 0.36483930544... . - Vaclav Kotesovec, Jul 26 2014

EXAMPLE

From Gus Wiseman, May 20 2018: (Start)

Non-isomorphic representatives of the a(4) = 9 spanning hyperforests are the following:

  {{1,2,3,4}}

  {{1},{2,3,4}}

  {{1,2},{3,4}}

  {{1,4},{2,3,4}}

  {{1},{2},{3,4}}

  {{1},{2,4},{3,4}}

  {{1,3},{2,4},{3,4}}

  {{1,4},{2,4},{3,4}}

  {{1},{2},{3},{4}}

Non-isomorphic representatives of the a(4) = 9 hyperforests spanning up to 4 vertices without singleton edges are the following:

  {}

  {{1,2}}

  {{1,2,3}}

  {{1,2,3,4}}

  {{1,2},{3,4}}

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

  {{1,4},{2,3,4}}

  {{1,3},{2,4},{3,4}}

  {{1,4},{2,4},{3,4}}

(End)

MAPLE

with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; `if`(n=0, 1, add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n) end end: b:= etr(B): c:= etr(b): B:= n-> if n=0 then 0 else c(n-1) fi: C:= etr(B): aa:= proc(n) option remember; B(n)+C(n) -add(B(k)*C(n-k), k=0..n) end: a:= etr(aa): seq(a(n), n=0..27); # Alois P. Heinz, Sep 09 2008

MATHEMATICA

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[B]; c = etr[b]; B[n_] := If[n == 0, 0, c[n-1]]; CC = etr[B]; aa[n_] := aa[n] = B[n]+CC[n]-Sum[B[k]*CC[n-k], {k, 0, n}]; a = etr[aa]; Table[a[n], {n, 0, 27}] (* Jean-Fran├žois Alcover, Feb 13 2015, after Alois P. Heinz*)

PROG

(PARI) \\ here b is A007563 as vector

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(v)))); v}

seq(n)={my(u=b(n)); concat([1], EulerT(Vec(x*Ser(EulerT(u))*(1-x*Ser(u)))))} \\ Andrew Howroyd, May 22 2018

CROSSREFS

Cf. A030019, A035053 (hypertrees), A048143, A054921, A134954 (labeled case), A134955, A134957, A144959, A245566, A304716, A304717, A304867, A304911.

Sequence in context: A032289 A006648 A128496 * A171887 A027881 A002861

Adjacent sequences:  A134952 A134953 A134954 * A134956 A134957 A134958

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 April 20 08:32 EDT 2019. Contains 322306 sequences. (Running on oeis4.)