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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A035053 Number of connected graphs on n unlabeled nodes where every block is a complete graph. 29
1, 1, 1, 2, 4, 9, 22, 59, 165, 496, 1540, 4960, 16390, 55408, 190572, 665699, 2354932, 8424025, 30424768, 110823984, 406734060, 1502876903, 5586976572, 20884546416, 78460794158, 296124542120, 1122346648913, 4270387848473 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 71, (3.4.14).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)

Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.

Robert Hellmann and Eckard Bich, A systematic formulation of the virial expansion for nonadditive interaction potentials, J. Chem. Phys. 135, 084117 (2011); doi:10.1063/1.3626524 (7 pages).

R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO].

FORMULA

G.f.: A(x)=1+(C(x)-1)*(1-B(x)). B: G.f. for A007563. C: G.f. for A035052.

a(n) ~ c * d^n / n^(5/2), where d = 4.189610958393826965527036454524... (see A245566), c = 0.245899549044224207821149415964395... . - Vaclav Kotesovec, Jul 26 2014

a(n) = A304937(n) - A304937(n-1) for n>1, a(n) = 1 for n<2. - Gus Wiseman, May 22 2018

EXAMPLE

From Gus Wiseman, May 20 2018: (Start)

Non-isomorphic representatives of the a(5) = 9 hypertrees are the following:

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

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

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

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

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

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

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

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

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

(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): 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

MATHEMATICA

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 *)

PROG

(PARI) \\ here b(n) 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)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u)))} \\ Andrew Howroyd, May 22 2018

CROSSREFS

Cf. A007549, A007563, A007716, A030019, A035051, A035052, A054921, A134957, A134959, A245566, A304867, A304887, A304937.

Sequence in context: A171367 A092920 A177377 * A000571 A077003 A210726

Adjacent sequences:  A035050 A035051 A035052 * A035054 A035055 A035056

KEYWORD

nonn,easy,nice

AUTHOR

Christian G. Bower, Oct 15 1998

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 25 10:59 EDT 2018. Contains 311897 sequences. (Running on oeis4.)