A331438 -id:A331438 - cp's OEIS frontend

A003515 Number of series-reduced connected labeled graphs with n nodes.

0, 1, 1, 0, 5, 51, 3634, 374119, 73161880, 26545249985, 17904840957826, 22602069719494379, 53938857227326533032, 246107945479472758874483, 2170331943503938546383205218, 37340982087637629911717846092591, 1262915556964772342158139988356979872

Offset: 0

N. J. A. Sloane

nonn

Jackson and Reilly paper has typographical error in value for a(12). - Sean A. Irvine, Jun 17 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..34 from Sean A. Irvine)
D. M. Jackson and J. W. Reilly, The enumeration of homeomorphically irreducible labeled graphs, J. Combin. Theory, B 19 (1975), 272-286.

Row sums of A331438.
Column sums of A331437.
Cf. A003514, A331584.

\\ See Jackson & Reilly for e.g.f.
seq(n)={my(A=O(x*x^n)); Vec(serlaplace(log((exp(x/2 - x^2/4 + A)/sqrt(1 + x + A))*sum(k=0, n, (2*exp(-x/(1+x) + A))^binomial(k,2) * (x*exp((x^2 + A)/(2*(1 + x))))^k / k!))), -(n+1))} \\ Andrew Howroyd, Jan 24 2020

E.g.f.: log(B(x)) where B(x) is the e.g.f. for A003514. - Sean A. Irvine, Jun 17 2015

More terms and a(12) corrected by Sean A. Irvine, Jun 17 2015

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.

Original entry on oeis.org

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

N. J. A. Sloane, Jan 19 2020

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

			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;
...

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.

Column sums are A003515.
Row sums are A331584.
Right diagonal is A005512(n+1).
Cf. A060514, A331438 (transpose).

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

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

A060514 Triangle T(n,k) of series-reduced (or homeomorphically irreducible) labeled graphs with n nodes and k edges, k=0..binomial(n,2).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 0, 0, 1, 6, 3, 4, 0, 0, 1, 1, 10, 15, 20, 5, 0, 5, 20, 15, 10, 1, 1, 15, 45, 75, 90, 96, 135, 315, 510, 760, 843, 765, 395, 105, 15, 1, 1, 21, 105, 245, 525, 777, 1302, 3045, 7455, 16275, 30135, 50190, 70805, 81690, 70605, 43239, 18774, 5880, 1330

Offset: 0

Vladeta Jovovic, Mar 23 2001

			Triangle begins:
[1],
[1],
[1, 1],
[1, 3, 0, 0],
[1, 6, 3, 4, 0, 0, 1],
[1, 10, 15, 20, 5, 0, 5, 20, 15, 10, 1],
[1, 15, 45, 75, 90, 96, 135, 315, 510, 760, 843, 765, 395, 105, 15, 1],
[1, 21, 105, 245, 525, 777, 1302, 3045, 7455, 16275, 30135, 50190, 70805, 81690, 70605, 43239, 18774, 5880, 1330, 210, 21, 1],
...

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

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

Row sums: A003514.

For connected graphs see A331437, A331438.

E.g.f. : (1+x*y)^(-1/2)*exp(x*y/2-x^2*y^2/4)*Sum_{k=0..inf}((1+x)*exp(-x^2*y/(1+x*y)))^binomial(k, 2)*(exp(1/2*x^3*y^2/(1+x*y)))^k*x^k/k!

A331584 Number of series-reduced connected labeled graphs with n edges.

Original entry on oeis.org

1, 1, 0, 4, 5, 96, 548, 7908, 84696, 1331840, 20255774, 372819387, 7170089146, 154824436840, 3558826861734, 88938133663711, 2367074592366594, 67402755251544804, 2034875403034891874, 65102692993820702700, 2196725886835707259041, 78036983096041464230268

Offset: 0

Andrew Howroyd, Jan 24 2020

nonn

Series-reduced graphs are also called homeomorphically irreducible graphs and are the graphs without vertices of degree 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
D. M. Jackson and J. W. Reilly, The enumeration of homeomorphically irreducible labeled graphs, J. Combin. Theory, B 19 (1975), 272-286.

Row sums of A331437.
Column sums of A331438.
Cf. A003515.

\\ See Jackson & Reilly link 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!)}
seq(n)={Vec(subst(Pol(serlaplace(log(H(n, y+O(y^n))))), x, 1))}

cp's OEIS Frontend

A003515 Number of series-reduced connected labeled graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A060514 Triangle T(n,k) of series-reduced (or homeomorphically irreducible) labeled graphs with n nodes and k edges, k=0..binomial(n,2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A331584 Number of series-reduced connected labeled graphs with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI