A134959 -id:A134959 - cp's OEIS frontend

A035053 Number of connected graphs on n unlabeled nodes where every block is a complete graph.

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

Offset: 0

Christian G. Bower, Oct 15 1998

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.

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

			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)

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

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).
Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.
Eric Weisstein's World of Mathematics, Block Graph
Eric Weisstein's World of Mathematics, Connected Graph
Wikipedia, Block graph.

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

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

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

\\ 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

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

A134957 Number of hyperforests with n unlabeled vertices: analog of A134955 when edges of size 1 are allowed (with no two equal edges).

Original entry on oeis.org

1, 2, 6, 20, 75, 310, 1422, 7094, 37877, 213610, 1256422, 7641700, 47735075, 304766742, 1981348605, 13079643892, 87480944764, 591771554768, 4042991170169, 27864757592632, 193549452132550, 1353816898675732, 9529263306483357, 67457934248821368, 480019516988969011

Offset: 0

Don Knuth, Jan 26 2008

nonn

			From _Gus Wiseman_, May 20 2018: (Start)
Non-isomorphic representatives of the a(3) = 20 hyperforests are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{1},{2}}
  {{1},{2,3}}
  {{2},{1,2}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{1},{2},{1,2}}
  {{1},{3},{2,3}}
  {{2},{3},{1,2,3}}
  {{2},{1,3},{2,3}}
  {{3},{1,3},{2,3}}
  {{1,2},{1,3},{2,3}}
  {{1},{2},{3},{2,3}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,3},{2,3}}
  {{2},{3},{1,3},{2,3}}
  {{3},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}
  {{2},{3},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3}}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A054921, A134955, A134957, A134959, A144959, A304867, A304911.

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];
EulerT[v_List] := With[{q = etr[v[[#]]&]}, q /@ Range[Length[v]]];
ser[v_] := Sum[v[[i]] x^(i - 1), {i, 1, Length[v]}] + O[x]^Length[v];
b[n_] := Module[{v = {1}}, For[i = 2, i <= n, i++, v = Join[{1}, EulerT[EulerT[2 v]]]]; v];
seq[n_] := Module[{u = 2 b[n]}, Join[{1}, EulerT[ser[EulerT[u]]*(1 - x*ser[u]) + O[x]^n // CoefficientList[#, x]&]]];
seq[24] (* Jean-François Alcover, Feb 10 2020, after Andrew Howroyd *)

\\ here b(n) is A318494 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(2*v)))); v}
seq(n)={my(u=2*b(n)); concat([1], EulerT(Vec(Ser(EulerT(u))*(1-x*Ser(u)))))} \\ Andrew Howroyd, Aug 27 2018

Euler transform of A134959. - Gus Wiseman, May 20 2018

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Original entry on oeis.org

1, 2, 5, 15, 50, 200, 907, 4607, 25077, 144337, 863678, 5329994, 33697112, 217317986, 1424880997, 9474795661, 63769947778, 433751273356, 2977769238994, 20611559781972, 143720352656500, 1008765712435162, 7122806053951140, 50566532826530292, 360761703055959592

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(3) = 15 hypertrees are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{1,3},{2,3}}
  {{3},{1,2,3}}
  {{1},{2},{1,2}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{2},{3},{1,2},{1,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A134959, A144959, A304386, A304717, A304867, A304911, A304912, A304968, A304970.

\\ here b(n) is A318494 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(2*v)))); v}
seq(n)={my(u=2*b(n)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of b(1) = 1, b(n) = A134959(n) otherwise.

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

A304918 Number of labeled antichain hyperforests spanning a subset of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 18, 104, 943, 12133, 203038, 4177755, 101922814, 2874725600, 92009680557, 3294276613933, 130446181101044, 5660055256165565, 267044522107706072, 13611243187516647324, 745329728016955480687, 43636132793651444511809, 2719977663069107176768790

Offset: 0

Gus Wiseman, May 21 2018

nonn

			The a(3) = 18 hyperforests are the following:
{{1,2,3}}      {{2,3}}    {{1,3}}    {{1,2}}    {{3}}   {{2}}   {{1}}   {}
{{1,3},{2,3}}  {{2},{3}}  {{1},{3}}  {{1},{2}}
{{1,2},{2,3}}
{{1,2},{1,3}}
{{3},{1,2}}
{{2},{1,3}}
{{1},{2,3}}
{{1},{2},{3}}

Cf. A030019, A035053, A048143, A134954, A134955, A134957, A134956, A134957, A134959, A144959, A303838, A304716, A304717, A304867, A304911, A304912.

Binomial transform of A134954.

A318494 Number of rooted simple connected graphs on n unlabeled nodes where every block is a complete graph with nonroot nodes of two colors.

Original entry on oeis.org

1, 2, 10, 50, 285, 1696, 10647, 68842, 456922, 3091546, 21252396, 147992264, 1041779912, 7401119718, 52996414666, 382095695324, 2771458821772, 20209364313202, 148064910503435, 1089415620952020, 8046283404651000, 59635009544475814, 443380411766040664

Offset: 1

Andrew Howroyd, Aug 27 2018

nonn

Number of rooted spanning hypertrees on n unlabeled nodes with edges of size 1 allowed.

Shifts left when Euler transform is applied twice to double this sequence.

			a(3) = 10 because there are three possible rooted graphs which are illustrated below and these can be colored up to isomorphism in 3, 3 and 4 ways respectively.
  o---o   o   o   o---o
   \ /     \ /     \
    *       *       *

Alois P. Heinz, Table of n, a(n) for n = 1..1116 (first 200 terms from Andrew Howroyd)

Cf. A007563, A134959.

b:= ((proc(p) local b; b:= proc(n) option remember; `if`(n=0, 1,
        add(add(d*p(d), d=numtheory[divisors](j))*b(n-j), j=1..n)/n)
      end end)@@2)(2*a):
a:= n-> b(n-1):
seq(a(n), n=1..25);  # Alois P. Heinz, Aug 27 2018

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];
a[n_] := b[n-1];
b = etr@etr@(2a[#]&);
Array[a, 25] (* Jean-François Alcover, Nov 01 2020 *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(2*v)))); v}

A304968 Number of labeled hypertrees spanning some subset of {1,...,n}, with singleton edges allowed.

Original entry on oeis.org

1, 2, 7, 48, 621, 12638, 351987, 12426060, 531225945, 26674100154, 1538781595999, 100292956964456, 7288903575373509, 584454485844541718, 51256293341752583499, 4880654469385955209092, 501471626403154217825457, 55300894427785157597436786

Offset: 0

Gus Wiseman, May 22 2018

nonn

			The a(2) = 7 hypertrees are the following:
{}
{{1}}
{{2}}
{{1,2}}
{{1},{1,2}}
{{2},{1,2}}
{{1},{2},{1,2}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304386, A304867, A304911, A304912, A304918, A304968, A304970.

\\ here b(n) is A134958 with b(1)=1.
b(n)=if(n<2, n>=0, 2^n*sum(i=0, n, stirling(n-1, i, 2)*n^(i-1)));
a(n)=sum(k=0, n, binomial(n, k)*b(k)); \\ Andrew Howroyd, Aug 27 2018

Binomial transform of b(1) = 1, b(n) = A134958(n) otherwise.

A304970 Number of unlabeled hypertrees with up to n vertices and without singleton edges.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 39, 98, 263, 759, 2299, 7259, 23649, 79057, 269629, 935328, 3290260, 11714285, 42139053, 152963037, 559697097, 2062574000, 7649550572, 28534096988, 106994891146, 403119433266, 1525466082179, 5795853930652, 22102635416716, 84579153865570

Offset: 0

Gus Wiseman, May 22 2018

nonn

			Non-isomorphic representatives of the a(4) = 8 hypertrees are the following:
{}
{{1,2}}
{{1,2,3}}
{{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}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304386, A304867, A304911, A304912, A304918, A304968, A304970.

\\ 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)))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of A035053 if we assume A035053(1) = 0.

a(n) = A304937(n) + 1 for n > 0.

A304937 Number of unlabeled nonempty hypertrees with up to n vertices and no singleton edges.

Original entry on oeis.org

1, 0, 1, 3, 7, 16, 38, 97, 262, 758, 2298, 7258, 23648, 79056, 269628, 935327, 3290259, 11714284, 42139052, 152963036, 559697096, 2062573999, 7649550571, 28534096987, 106994891145, 403119433265, 1525466082178, 5795853930651, 22102635416715, 84579153865569

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(5) = 16 hypertrees are the following:
{{1,2}}
{{1,2,3}}
{{1,2,3,4}}
{{1,2,3,4,5}}
{{1,3},{2,3}}
{{1,4},{2,3,4}}
{{1,5},{2,3,4,5}}
{{1,2,5},{3,4,5}}
{{1,2},{2,5},{3,4,5}}
{{1,3},{2,4},{3,4}}
{{1,4},{2,4},{3,4}}
{{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}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A134954, A134955, A134956, A134957, A134959, A144959, A303838, A304867, A304911, A304912, A304918.

\\ 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)) - x)/(1-x))} \\ Andrew Howroyd, Aug 27 2018

a(n) = a(n-1) + A035053(n) for n > 1, a(n) = 1 - n for n < 2.

A304939 Number of labeled nonempty hypertrees (connected antichains with no cycles) spanning some subset of {1,...,n} without singleton edges.

Original entry on oeis.org

1, 0, 1, 7, 51, 506, 6843, 118581, 2504855, 62370529, 1788082153, 57997339632, 2099638691439, 83922479506503, 3670657248913385, 174387350448735877, 8942472292255441103, 492294103555090048458, 28958704109012732921523

Offset: 0

Gus Wiseman, May 21 2018

nonn

			The a(3) = 7 hypertrees are the following:
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A134954, A134955, A134956, A134957, A134959, A144959, A303838, A304867, A304911, A304912, A304918, A305004.

\\ here b(n) is A030019 with b(1)=0.
b(n)=if(n<2, n==0, sum(i=0, n, stirling(n-1, i, 2)*n^(i-1)));
a(n)=if(n<1, n==0, sum(k=1, n, binomial(n, k)*b(k))); \\ Andrew Howroyd, Aug 27 2018

a(n) = A305004(n) - 1 for n > 0. - Andrew Howroyd, Aug 27 2018

A305004 Number of labeled hypertrees (connected acyclic antichains) spanning some subset of {1,...,n} without singleton edges.

Original entry on oeis.org

1, 1, 2, 8, 52, 507, 6844, 118582, 2504856, 62370530, 1788082154, 57997339633, 2099638691440, 83922479506504, 3670657248913386, 174387350448735878, 8942472292255441104, 492294103555090048459, 28958704109012732921524

Offset: 0

Gus Wiseman, May 23 2018

nonn

			The a(3) = 8 hypertrees:
{}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A134958, A134959, A304386, A304939, A304968, A304970.

\\ here b(n) is A030019 with b(1)=0.
b(n)=if(n<2, n==0, sum(i=0, n, stirling(n-1, i, 2)*n^(i-1)));
a(n)=sum(k=0, n, binomial(n, k)*b(k)); \\ Andrew Howroyd, Aug 27 2018

a(n > 0) = A304939(n) + 1.

Binomial transform of A030019 if we assume A030019(1) = 0.

cp's OEIS Frontend

A035053 Number of connected graphs on n unlabeled nodes where every block is a complete graph.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A134957 Number of hyperforests with n unlabeled vertices: analog of A134955 when edges of size 1 are allowed (with no two equal edges).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A304918 Number of labeled antichain hyperforests spanning a subset of {1,...,n}.

Views

Author

Keywords

Examples

Crossrefs

Formula

A318494 Number of rooted simple connected graphs on n unlabeled nodes where every block is a complete graph with nonroot nodes of two colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A304968 Number of labeled hypertrees spanning some subset of {1,...,n}, with singleton edges allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A304970 Number of unlabeled hypertrees with up to n vertices and without singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A304937 Number of unlabeled nonempty hypertrees with up to n vertices and no singleton edges.

Views

Author