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