A007549 -id:A007549 - 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

A007563 Number of rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

0, 1, 1, 3, 8, 25, 77, 258, 871, 3049, 10834, 39207, 143609, 532193, 1990163, 7503471, 28486071, 108809503, 417862340, 1612440612, 6248778642, 24309992576, 94905791606, 371691137827, 1459935388202, 5749666477454

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 71, (3.4.13).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1600 (first 200 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.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 167
N. J. A. Sloane, Transforms

Cf. A007549, A030019, A035051, A035052, A035053.
Column k=2 of A144042.
Cf. A245566.

with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; if n=0 then 1 else (add(d*p(d), d=divisors(n)) +add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n-1))/n fi end end: b:= etr(a): c:= etr(b): a:= n-> if n=0 then 0 else c(n-1) fi: seq(a(n), n=0..25); # Alois P. Heinz, Sep 06 2008

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[0] = 0; a[n_] := etr[etr[a]][n-1]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 28 2013, after Alois P. Heinz *)

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(v)))); concat([0], v)} \\ Andrew Howroyd, May 20 2018

Shifts left when Euler transform is applied twice.

a(n) ~ c * d^n / n^(3/2), where d = 4.189610958393826965527036454524044275... (see A245566), c = 0.1977574301782950818433893126632477845870281049591883888... . - Vaclav Kotesovec, Jul 26 2014

New description from Christian G. Bower, Oct 15 1998

A035051 Number of labeled rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

0, 1, 2, 12, 116, 1555, 26682, 558215, 13781448, 392209380, 12641850510, 455198725025, 18109373455164, 788854833679549, 37343190699472322, 1908871649888004240, 104789417805394595600, 6148562290130009617619

Offset: 0

Christian G. Bower, Oct 15 1998

Equivalently, rooted labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).

Warren D. Smith and David Warme, Paper in preparation, 2002.

T. D. Noe, Table of n, a(n) for n=0..100
Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465, 2016.
I. M. Gessel and L. H. Kalikow, Hypergraphs and a functional equation...
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 864
D. M. Warme, Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, University of Virginia, 1998.

Cf. A007549, A007563, A030019, A038052, A038053, A030438. A052888, A210586.

f[n_] := Sum[ n^i*StirlingS2[n - 1, i], {i, 0, n - 1}]; Array[f, 18, 0] (* Robert G. Wilson v, Apr 05 2012 *)
Table[If[n == 0, 0, BellB[n - 1, n]], {n, 0, 100}] (* Emanuele Munarini, May 23 2014 *)

a(n):=if n=0 then 0 else sum(stirling2(n-1,k)*n^k,k,0,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, May 23 2014 */

for(n=0,30, print1(sum(k=0,n-1, stirling(n-1,k,2)*n^k), ", ")) \\ G. C. Greubel, Nov 17 2017

Recurrence: a(1) = 1, a(n) = Sum_{k=1}^{n-1} Bell(k) / k! Sum_{a_j > 0, Sum_{j=1}^k a_j = n-1} {{n-1} choose {a_1, a_2, ..., a_k }} \prod_{j=1}^k a(a_j) for n > 1, where Bell(k) = A000110(k). - Warren D. Smith, Feb 23 1998
a(n) = Sum_{i=0...n-1} S(n-1, i) n^i, where S(N, M) are Stirling numbers of the second kind - David Warme, Mar 25 1998
E.g.f. satisfies A(x)=x*exp(exp(A(x))-1).
Let X_{mu} be a Poisson random variable with mean mu: P(X_{mu} = K) = e^{-mu} mu^K / K!. The n-th moment of X_{mu} is E[X_{mu}^n] = sum_{i=0}^n S(n, i) mu^i. Therefore a(n) = E[X_n^{n-1}]. - Langworth Withers, May 25 2000
Dobinski-type formula: a(n) = 1/e^n*sum {k = 0..inf} n^k*k^(n-1)/k!. Cf. A030019 and A052888. For a refinement of this sequence see A210586. - Peter Bala, Apr 05 2012
a(n) ~ exp((1/LambertW(1)-2)*n) * n^(n-1) / (sqrt(1+LambertW(1)) * LambertW(1)^(n-1)). - Vaclav Kotesovec, Jan 22 2014

A035052 Number of sets of rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 134, 444, 1518, 5318, 18989, 68856, 252901, 938847, 3517082, 13278844, 50475876, 193014868, 741963015, 2865552848, 11113696421, 43266626430, 169019868095, 662337418989, 2602923589451, 10256100717875

Offset: 0

Christian G. Bower, Oct 15 1998

nonn

T. D. Noe, Table of n, a(n) for n=0..200
Loic Foissy, The Hopf algebra of Fliess operators and its dual pre-Lie algebra, 2013.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 862
N. J. A. Sloane, Transforms

Cf. A007549, A007563, A030019, A035051, A035053.

Cf. A245566.

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(aa): c:= etr(b): aa:= n-> if n=0 then 0 else c(n-1) fi: a:= etr(aa): seq(a(n), n=0..25); # Alois P. Heinz, Sep 09 2008

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[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 05 2015, after Alois P. Heinz *)

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(v)))); concat([1], EulerT(v))} \\ Andrew Howroyd, May 20 2018

Euler transform of A007563.

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

A035081 Number of increasing asymmetric rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

1, 1, 1, 7, 27, 167, 1451, 12672, 133356, 1573608, 20731512, 299642958, 4732486932, 81201040470, 1500094187292, 29730606352920, 628968809015766, 14147458062941100, 337143091156288002, 8485143902146640124

Offset: 1

Christian G. Bower, Nov 15 1998

In an increasing rooted graph nodes are numbered and numbers increase as you move away from root.

Andrew Howroyd, Table of n, a(n) for n = 1..100
C. G. Bower, Transforms (2)

Cf. A007549, A007561, A035079, A035080.

EGJ(v)={Vec(serlaplace(prod(k=1, #v, (1 + x^k/k! + O(x*x^#v))^v[k]))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, v=concat([1], EGJ(EGJ(v)))); v} \\ Andrew Howroyd, Sep 11 2018

Shifts left when EGJ transform applied twice.

A078341 Triangle read by rows: T(n,k) = nT(n-1,k-1) + kT(n-1,k) starting with T(0,0)=1.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 7, 6, 0, 1, 18, 46, 24, 0, 1, 41, 228, 326, 120, 0, 1, 88, 930, 2672, 2556, 720, 0, 1, 183, 3406, 17198, 31484, 22212, 5040, 0, 1, 374, 11682, 96040, 295004, 385144, 212976, 40320, 0, 1, 757, 38412, 489298, 2339380, 4965900

Offset: 1

F. Chapoton, Nov 22 2002

Triangle of coefficients of polynomials P[n]. Let F(t) satisfy dF/dt = exp(x*(exp(F)-1)) and F(0)=0. Then F(t) = Sum_{n>=0} P[n]/n! t^n, where P[n] is a polynomial in x of degree n-1. The constant term of the polynomial is zero for n >= 2. The coefficient of x is 1 for n >= 2. The coefficient of x^n in P[n+1] is n!. The value at 1 is given by sequence A007549.

			P[1]=1, P[2]=x, P[3]=x+2*x^2, P[4]=x+7*x^2+6*x^3, P[5]=x+18*x^2+46*x^3+24*x^4, P[6]=x+41*x^2+228*x^3+326*x^4+120*x^5.
Rows start 1; 0,1; 0,1,2; 0,1,7,6; 0,1,18,46,24; 0,1,41,228,326,120; ...

Cf. A007549, A000142.

Columns include A000007, A057427, A095151, A103768. Diagonals include A000142, A067318. Row sums are A007549.

P[1] := 1; for n from 1 to 10 do P[n+1] := expand(x*diff(P[n],x)+x*n*P[n]) od;

p[1][x_] = 1; p[n_][x_] := x*p[n-1]'[x] + x*(n-1)*p[n-1][x]; Table[ CoefficientList[ p[n][x], x], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 29 2013 *)

P[1]=1; P[n+1] = x*(d/dx)P[n] + x*n*P[n].

Additional comments from Henry Bottomley, Feb 15 2005

A264436 Triangle read by rows, inverse Bell transform of the complementary Bell numbers (A000587); T(n,k) for n>=0 and 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 3, 1, 0, 14, 15, 6, 1, 0, 89, 100, 45, 10, 1, 0, 716, 834, 405, 105, 15, 1, 0, 6967, 8351, 4284, 1225, 210, 21, 1, 0, 79524, 97596, 52220, 16009, 3080, 378, 28, 1, 0, 1041541, 1303956, 721674, 233268, 48699, 6804, 630, 36, 1

Offset: 0

Peter Luschny, Dec 01 2015

			Triangle starts:
1,
0,     1,
0,     1,     1,
0,     3,     3,     1,
0,    14,    15,     6,     1,
0,    89,   100,    45,    10,    1,
0,   716,   834,   405,   105,   15,   1,
0,  6967,  8351,  4284,  1225,  210,  21,  1,
0, 79524, 97596, 52220, 16009, 3080, 378, 28, 1

Peter Luschny, The Bell transform

Cf. A000587, A007549, A029768, A264428, A264429.

# uses[bell_transform from A264428, inverse_bell_transform from A264429]
def A264436_matrix(dim):
    uno = [1]*dim
    complementary_bell_numbers = [sum((-1)^n*b for (n, b) in enumerate (bell_transform(n, uno))) for n in (0..dim)]
    return inverse_bell_transform(dim, complementary_bell_numbers)
A264436_matrix(9)

Row sums are A029768(n-1) for n>=1.

T(n,1) = A007549(n) for n>=1.

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

A007563 Number of rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A035051 Number of labeled rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A035052 Number of sets of rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A035081 Number of increasing asymmetric rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A078341 Triangle read by rows: T(n,k) = n*T(n-1,k-1) + k*T(n-1,k) starting with T(0,0)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A264436 Triangle read by rows, inverse Bell transform of the complementary Bell numbers (A000587); T(n,k) for n>=0 and 0<=k<=n.

Views

Author

Keywords

Examples

Links

A078341 Triangle read by rows: T(n,k) = nT(n-1,k-1) + kT(n-1,k) starting with T(0,0)=1.