A331437 -id:A331437 - cp's OEIS frontend

A343088 Triangle read by rows: T(n,k) is the number of connected labeled graphs with n edges and k vertices, 1 <= k <= n+1.

1, 0, 1, 0, 0, 3, 0, 0, 1, 16, 0, 0, 0, 15, 125, 0, 0, 0, 6, 222, 1296, 0, 0, 0, 1, 205, 3660, 16807, 0, 0, 0, 0, 120, 5700, 68295, 262144, 0, 0, 0, 0, 45, 6165, 156555, 1436568, 4782969, 0, 0, 0, 0, 10, 4945, 258125, 4483360, 33779340, 100000000

Offset: 0

Andrew Howroyd, Apr 14 2021

			Triangle begins:
  1;
  0, 1;
  0, 0, 3;
  0, 0, 1, 16;
  0, 0, 0, 15, 125;
  0, 0, 0,  6, 222, 1296;
  0, 0, 0,  1, 205, 3660,  16807;
  0, 0, 0,  0, 120, 5700,  68295,  262144;
  0, 0, 0,  0,  45, 6165, 156555, 1436568, 4782969;
  ...

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

Main diagonal is A000272.
Subsequent diagonals give the number of connected labeled graphs with n nodes and n+k edges for k=0..11: A057500, A061540, A061541, A061542, A061543, A096117, A061544 A096150, A096224, A182294, A182295, A182371.
Row sums are A322137.
Column sums are A001187.
Cf. A054923 (unlabeled), A062734 (transpose), A290776 (multigraphs), A322147 (loops allowed), A331437 (series-reduced).

row[n_] := (SeriesCoefficient[#, {y, 0, n}]& /@ CoefficientList[ Log[Sum[x^k*(1+y)^Binomial[k, 2]/k!, {k, 0, n+1}]] + O[x]^(n+2), x]* Range[0, n+1]!) // Rest;
Table[row[n], {n, 0, 9}] // Flatten (* Jean-François Alcover, Aug 03 2022, after Andrew Howroyd *)

Row(n)={Vec(serlaplace(polcoef(log(O(x^2*x^n)+sum(k=0, n+1, x^k*(1 + y + O(y*y^n))^binomial(k, 2)/k!)), n, y)), -(n+1))}
{ for(n=0, 8, print(Row(n))) }

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

Original entry on oeis.org

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

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

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

A343088 Triangle read by rows: T(n,k) is the number of connected labeled graphs with n edges and k vertices, 1 <= k <= n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

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

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