cp's OEIS Frontend

A134955 Number of "hyperforests" on n unlabeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

%I A134955 #40 Oct 01 2019 07:16:47
%S A134955 1,1,2,4,9,20,50,128,351,1009,3035,9464,30479,100712,340072,1169296,
%T A134955 4082243,14438577,51643698,186530851,679530937,2494433346,9219028889,
%U A134955 34280914106,128179985474,481694091291,1818516190252,6894350122452
%N A134955 Number of "hyperforests" on n unlabeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.
%C A134955 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
%C A134955 Equivalently, number of block graphs on n nodes, that is, graphs where every block is a complete graph. These graphs can be characterized as induced-diamond-free chordal graphs. - _Falk Hüffner_, Jul 25 2019
%D A134955 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 A134955 Alois P. Heinz, <a href="/A134955/b134955.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from T. D. Noe)
%H A134955 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A134955 Wikipedia, <a href="http://en.wikipedia.org/wiki/Block_graph">Block graph</a>
%F A134955 Euler transform of A035053. - _N. J. A. Sloane_, Jan 30 2008
%F A134955 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
%F A134955 a(n) ~ c * d^n / n^(5/2), where d = 4.189610958393826965527036454524... (see A245566), c = 0.36483930544... . - _Vaclav Kotesovec_, Jul 26 2014
%e A134955 From _Gus Wiseman_, May 20 2018: (Start)
%e A134955 Non-isomorphic representatives of the a(4) = 9 spanning hyperforests are the following:
%e A134955   {{1,2,3,4}}
%e A134955   {{1},{2,3,4}}
%e A134955   {{1,2},{3,4}}
%e A134955   {{1,4},{2,3,4}}
%e A134955   {{1},{2},{3,4}}
%e A134955   {{1},{2,4},{3,4}}
%e A134955   {{1,3},{2,4},{3,4}}
%e A134955   {{1,4},{2,4},{3,4}}
%e A134955   {{1},{2},{3},{4}}
%e A134955 Non-isomorphic representatives of the a(4) = 9 hyperforests spanning up to 4 vertices without singleton edges are the following:
%e A134955   {}
%e A134955   {{1,2}}
%e A134955   {{1,2,3}}
%e A134955   {{1,2,3,4}}
%e A134955   {{1,2},{3,4}}
%e A134955   {{1,3},{2,3}}
%e A134955   {{1,4},{2,3,4}}
%e A134955   {{1,3},{2,4},{3,4}}
%e A134955   {{1,4},{2,4},{3,4}}
%e A134955 (End)
%p A134955 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
%t A134955 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_*)
%o A134955 (PARI) \\ here b is A007563 as vector
%o A134955 EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o A134955 b(n)={my(v=[1]);for(i=2, n, v=concat([1], EulerT(EulerT(v)))); v}
%o A134955 seq(n)={my(u=b(n)); concat([1], EulerT(Vec(x*Ser(EulerT(u))*(1-x*Ser(u)))))} \\ _Andrew Howroyd_, May 22 2018
%Y A134955 Cf. A030019, A035053 (hypertrees), A048143, A054921, A134954 (labeled case), A134955, A134957, A144959, A245566, A304716, A304717, A304867, A304911.
%K A134955 nonn
%O A134955 0,3
%A A134955 _Don Knuth_, Jan 26 2008