A003515 -id:A003515 - cp's OEIS frontend

A003514 Number of series-reduced labeled graphs with n nodes.

1, 1, 2, 4, 15, 102, 4166, 402631, 76374899, 27231987762, 18177070202320, 22801993267433275, 54212469444212172845, 246812697326518127351384, 2173787304796735262709419350, 37373588848096468764431235680525, 1263513534110606141026676778422031561

Offset: 0

N. J. A. Sloane

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..80
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 A060514 and A307806.
The unlabeled version is A005637.
Cf. A003515 (connected).

max = 15; f[x_] := (1 + x)^(-1/2)*Exp[x/2-x^2/4]*Sum[(2*Exp[-x/(1+x)])^Binomial[k, 2]*Exp[x^2/2/(1+x)]^k*x^k/k!, {k, 0, max}]; CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]!(* Jean-François Alcover, Nov 25 2011, after Vladeta Jovovic *)

seq(n)={my(x='x+O('x^(n+1))); Vec(serlaplace((1 + x)^( - 1/2) * exp(x/2 - x^2/4) * sum(k=0, n, (2 * exp(-x/(1 + x)))^binomial(k, 2) * (exp(x^2/2/(1 + x)))^k * x^k/k!)))} \\ Andrew Howroyd, Feb 23 2024

E.g.f.: (1 + x)^( - 1/2) * exp(x/2 - x^2/4) * Sum_{k=0..inf} (2 * exp( - x/(1 + x)))^binomial(k, 2) * (exp(x^2/2/(1 + x)))^k * x^k/k!. - Vladeta Jovovic, Mar 23 2001

More terms from Vladeta Jovovic, Mar 23 2001

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

A331438 Irregular triangle read by rows: T(n,k) = number of homeomorphically irreducible connected labeled graphs with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0, 5, 0, 0, 20, 15, 10, 1, 0, 0, 0, 0, 0, 96, 120, 180, 420, 700, 837, 765, 395, 105, 15, 1, 0, 0, 0, 0, 0, 0, 427, 1260, 3780, 10850, 24045, 44814, 68040, 80955, 70500, 43232, 18774, 5880, 1330, 210, 21, 1, 0, 0, 0, 0, 0, 0, 0, 6448, 23520, 79800, 269360, 782880, 1956136, 4203360, 7610340, 11365676

Offset: 1

N. J. A. Sloane, Jan 19 2020

			Triangle begins:
1,
0,1,
0,0,0,0,
0,0,0,4,0,0,1,
0,0,0,0,5,0,0,20,15,10,1,
0,0,0,0,0,96,120,180,420,700,837,765,395,105,15,1,
0,0,0,0,0,0,427,1260,3780,10850,24045,44814,68040,80955,70500,43232,18774,5880,1330,210,21,1,
0,0,0,0,0,0,0,6448,23520,79800,269360,782880,1956136,4203360,7610340,11365676,...,
...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (first 20 rows)
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.

Row sums are A003515.

Cf. A060514, A331437 (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!)}
Row(n)={Vecrev(n!*polcoef(log(H(n,y)), n), binomial(n,2)+1)}
{ for(n=1, 6, print(Row(n))) } \\ Andrew Howroyd, Jan 24 2020

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

A307806 Triangle T(n,k) read by rows: number of series-reduced labeled graphs on n nodes with k components.

Original entry on oeis.org

1, 1, 1, 0, 3, 1, 5, 3, 6, 1, 51, 25, 15, 10, 1, 3634, 381, 90, 45, 15, 1, 374119, 26509, 1596, 280, 105, 21, 1, 73161880, 3095579, 111370, 5061, 770, 210, 28, 1, 26545249985, 671957334, 14411205, 353262, 13671, 1890, 378, 36, 1

Offset: 1

R. J. Mathar, Apr 29 2019

			The triangle starts
1;
1,1;
0,3,1;
5,3,6,1;
51,25,15,10,1;
3634,381,90,45,15,1;
374119,26509,1596,280,105,21,1;
73161880,3095579,111370,5061,770,210,28,1;
26545249985,671957334,14411205,353262,13671,1890,378,36,1;

Cf. A003515 (column k=1), A003514 (row sums).

T(n,1) = A003515(n).

T(n,k) = Sum_{Compositions n=n_1+n_2+...n_k, n_i>=1} multinomial(n; n_1,n_2,..,n_k) * T(n_1,1) * T(n_2,1) *... T(n_k,1)/ k!.

cp's OEIS Frontend

A003514 Number of series-reduced labeled graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

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

A331438 Irregular triangle read by rows: T(n,k) = number of homeomorphically irreducible connected labeled graphs with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A307806 Triangle T(n,k) read by rows: number of series-reduced labeled graphs on n nodes with k components.

Views

Author

Keywords

Examples

Crossrefs

Formula