A331437 Triangle read by rows: T(n,k) = number of homeomorphically irreducible connected labeled graphs with n edges and k vertices, n >= 0, 1 <= k <= n+1.

1, 0, 1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 96, 0, 0, 0, 1, 0, 120, 427, 0, 0, 0, 0, 20, 180, 1260, 6448, 0, 0, 0, 0, 15, 420, 3780, 23520, 56961, 0, 0, 0, 0, 10, 700, 10850, 79800, 347760, 892720, 0, 0, 0, 0, 1, 837, 24045, 269360, 1655640, 6400800, 11905091

Offset

0,10

Comments

Homeomorphically irreducible graphs are graphs without vertices of degree 2. - Andrew Howroyd, Jan 24 2020

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows n = 0..50)

D. M. Jackson and J. W. Reilly, The enumeration of homeomorphically irreducible labeled graphs, J. Combin. Theory, B 19 (1975), 272-286. See Table III.

Example

Triangle begins:
  1;
  0, 1;
  0, 0, 0;
  0, 0, 0, 4;
  0, 0, 0, 0,  5;
  0, 0, 0, 0,  0,  96;
  0, 0, 0, 1,  0, 120,  427;
  0, 0, 0, 0, 20, 180, 1260,  6448;
  0, 0, 0, 0, 15, 420, 3780, 23520, 56961;
...

Prog

(PARI) \\ See Jackson & Reilly for e.g.f.
H(n, y) = {my(A=O(x*x^n)); (exp(y*x/2 - (y*x)^2/4 + A)/sqrt(1 + y*x + A))*sum(k=0, n, ((1 + y)*exp(-y^2*x/(1+y*x) + A))^binomial(k, 2) * (x*exp((y^3*x^2 + A)/(2*(1 + y*x))))^k / k!)}
T(n) = {Mat([Col(p, -n) | p<-Vec(serlaplace(log(H(n, y + O(y^n)))))])}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 24 2020

Crossrefs

Column sums are A003515.

Row sums are A331584.

Right diagonal is A005512(n+1).

Cf. A060514, A331438 (transpose).

Sequence in context: A323519 A333979 A276580 * A351572 A108708 A290322

Adjacent sequences: A331434 A331435 A331436 * A331438 A331439 A331440

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jan 19 2020

Extensions

Terms a(44) and beyond from Andrew Howroyd, Jan 24 2020

Status

approved