|
%I #53 Nov 11 2022 08:08:30
%S 1,1,1,2,4,9,22,59,165,496,1540,4960,16390,55408,190572,665699,
%T 2354932,8424025,30424768,110823984,406734060,1502876903,5586976572,
%U 20884546416,78460794158,296124542120,1122346648913,4270387848473
%N Number of connected graphs on n unlabeled nodes where every block is a complete graph.
%C Equivalently, this is the number of "hypertrees" on n unlabeled nodes, i.e., connected hypergraphs that have no cycles, assuming that each edge contains at least two vertices. - _Don Knuth_, Jan 26 2008. See A134955 for hyperforests.
%C Graphs where every block is a complete graph are also called block graphs or clique tree. They can be characterized as induced-diamond-free chordal graphs. - _Falk Hüffner_, Jul 25 2019
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 71, (3.4.14).
%H Alois P. Heinz, <a href="/A035053/b035053.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from T. D. Noe)
%H Maryam Bahrani and Jérémie Lumbroso, <a href="http://arxiv.org/abs/1608.01465">Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition</a>, arXiv:1608.01465 [math.CO], 2016.
%H Robert Hellmann and Eckard Bich, <a href="http://dx.doi.org/10.1063/1.3626524">A systematic formulation of the virial expansion for nonadditive interaction potentials</a>, J. Chem. Phys. 135, 084117 (2011); doi:10.1063/1.3626524 (7 pages).
%H R. Bacher, <a href="https://arxiv.org/abs/1102.2708">On the enumeration of labelled hypertrees and of labelled bipartite trees</a>, arXiv:1102.2708 [math.CO].
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BlockGraph.html">Block Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Block_graph">Block graph</a>.
%F G.f.: A(x)=1+(C(x)-1)*(1-B(x)). B: G.f. for A007563. C: G.f. for A035052.
%F a(n) ~ c * d^n / n^(5/2), where d = 4.189610958393826965527036454524... (see A245566), c = 0.245899549044224207821149415964395... . - _Vaclav Kotesovec_, Jul 26 2014
%F a(n) = A304937(n) - A304937(n-1) for n>1, a(n) = 1 for n<2. - _Gus Wiseman_, May 22 2018
%e From _Gus Wiseman_, May 20 2018: (Start)
%e Non-isomorphic representatives of the a(5) = 9 hypertrees are the following:
%e {{1,2,3,4,5}}
%e {{1,5},{2,3,4,5}}
%e {{1,2,5},{3,4,5}}
%e {{1,2},{2,5},{3,4,5}}
%e {{1,4},{2,5},{3,4,5}}
%e {{1,5},{2,5},{3,4,5}}
%e {{1,3},{2,4},{3,5},{4,5}}
%e {{1,4},{2,5},{3,5},{4,5}}
%e {{1,5},{2,5},{3,5},{4,5}}
%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): a:= n-> B(n)+C(n) -add(B(k)*C(n-k), k=0..n): seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 09 2008
%t ClearAll[etr, b, a]; etr[p_] := 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[0]=0; b[n_] := b[n] = etr[etr[b]][n-1]; a[n_] := b[n] + etr[b][n] - Sum[b[k]*etr[b][n-k], {k, 0, n}]; Table[ a[n], {n, 0, 27}] (* _Jean-François Alcover_, Oct 09 2012, after _Alois P. Heinz_ *)
%o (PARI) \\ here b(n) 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)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u)))} \\ _Andrew Howroyd_, May 22 2018
%Y Cf. A007549, A007563, A007716, A030019, A035051, A035052, A054921, A134957, A134959, A245566, A304867, A304887, A304937.
%K nonn,easy,nice
%O 0,4
%A _Christian G. Bower_, Oct 15 1998
|
