A277072 -id:A277072 - cp's OEIS frontend

A327369 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

1, 1, 0, 1, 0, 1, 2, 0, 6, 0, 15, 12, 30, 4, 3, 314, 320, 260, 80, 50, 0, 13757, 10890, 5445, 1860, 735, 66, 15, 1142968, 640836, 228564, 64680, 16800, 2772, 532, 0, 178281041, 68362504, 17288852, 3666600, 702030, 115416, 17892, 1016, 105

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
      1
      1     0
      1     0     1
      2     0     6     0
     15    12    30     4     3
    314   320   260    80    50     0
  13757 10890  5445  1860   735    66    15

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

Row sums are A006125.
Row sums without the first column are A245797.
Column k = 0 is A059167.
Column k = 1 is A277072.
Column k = 2 is A277073.
Column k = 3 is A277074.
Column k = n is A123023.
Column k = n - 1 is A327370.
The unlabeled version is A327371.
The covering version is A327377.
Cf. A004110, A055302, A055314, A059166, A059167, A100743, A327227, A327228, A327362, A327364.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Count[Length/@Split[Sort[Join@@#]],1]==k&]],{n,0,5},{k,0,n}]

Row(n)={ \\ R, U, B are e.g.f. of A055302, A055314, A059167.
  my(R=sum(n=1, n, x^n*sum(k=1, n, stirling(n-1, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(U=sum(n=2, n, x^n*sum(k=1, n, stirling(n-2, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(B=x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!)));
  my(A=exp(x + U + subst(B-x, x, x*(1-y) + R)));
  Vecrev(n!*polcoef(A, n), n + 1);
}
{ for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Oct 05 2019

Column-wise binomial transform of A327377.

E.g.f.: exp(x + U(x,y) + B(x*(1-y) + R(x,y))), where R(x,y) is the e.g.f. of A055302, U(x,y) is the e.g.f. of A055314 and B(x) + x is the e.g.f. of A059167. - Andrew Howroyd, Oct 05 2019

Terms a(28) and beyond from Andrew Howroyd, Sep 09 2019

A277073 Number of n-node labeled graphs with two endpoints.

Original entry on oeis.org

0, 1, 6, 30, 260, 5445, 228564, 17288852, 2327095296, 562985438805, 248555982382840, 203515251722217402, 313711170518065772088, 922107609498513821505577, 5221584862895700871908309960, 57411615463478726571189869693160, 1232855219250913685154581533108294112

Offset: 1

Marko Riedel, Sep 27 2016

nonn

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31, problem 1.16(a).

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marko R. Riedel, Geoffrey Critzer, Math.Stackexchange.com, Proof of the closed form of the e.g.f. by combinatorial species.

Column k=2 of A327369.

Cf. A059167, A277072, A277074.

MX := 16:
XGF := exp(z^2/2)*add((z/exp(z))^n*2^binomial(n,2)/n!, n=0..MX+5):
K1 := 1/2*z^2/(1-z)*XGF:
K2 := 1/2*z^4/(1-z)^2*(diff(XGF, z$2)-2*diff(XGF,z)+XGF):
K3 := 1/2*z^3/(1-z)^3*(diff(XGF, z)-XGF):
XS := series(K1+K2+K3, z=0, MX+1):
seq(n!*coeff(XS, z, n), n=1..MX);

m = 16;
A[z_] := Exp[1/2*z^2]*Sum[2^Binomial[n, 2]*(z/Exp[z])^n/n!, {n, 0, m}];
egf = (1/2)*(z^2/(1 - z))*A[z] + (1/2)*(z^4/(1 - z)^2)*(A''[z] - 2*A'[z] + A[z]) + (1/2)*(z^3/(1 - z)^3)*(A'[z] - A[z]);
a[n_] := SeriesCoefficient[egf, {z, 0, n}]*n!;
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)

E.g.f.: (1/2)*(z^2/(1-z))*A(z) + (1/2)*(z^4/(1-z)^2)*(A''(z)-2*A'(z)+A(z)) + (1/2)*(z^3/(1-z)^3)*(A'(z)-A(z)) where A(z) = exp(1/2*z^2)*Sum_{n>=0} (2^binomial(n, 2)*(z/exp(z))^n/n!).

A277074 Number of n-node labeled graphs with three endpoints.

Original entry on oeis.org

0, 0, 0, 4, 80, 1860, 64680, 3666600, 354093264, 59372032440, 17572209206640, 9347625940951980, 9099961952914672840, 16480899322963497105684, 56311549004017312945310280, 367105988116570172056739960080

Offset: 1

Marko Riedel, Sep 27 2016

nonn

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31, problem 1.16(a).

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marko R. Riedel, Geoffrey Critzer, Math.Stackexchange.com, Proof of the closed form of the e.g.f. by combinatorial species.

Column k=3 of A327369.

Cf. A059167, A277072, A277073.

MX := 16:
XGF := exp(z^2/2)*add((z/exp(z))^n*2^binomial(n,2)/n!, n=0..MX+5):
K1 := 1/6*z^4/(1-z)^3*XGF:
K2 := 1/2*z^4/(1-z)^2*(diff(XGF,z)-XGF):
K3 := 1/6*z^6/(1-z)^3*(diff(XGF, z$3)-3*diff(XGF, z$2)+3*diff(XGF,z)-XGF):
K4 := 1/2*z^5/(1-z)^4*(diff(XGF, z$2)-2*diff(XGF,z)+XGF):
K5 := 1/6*z^4/(1-z)^4*(diff(XGF,z)-XGF):
K6 := 1/2*z^5/(1-z)^5*(diff(XGF,z)-XGF):
XS := series(K1+K2+K3+K4+K5+K6, z=0, MX+1):
seq(n!*coeff(XS, z, n), n=1..MX);

m = 16;
A[z_] := Exp[1/2*z^2]*Sum[2^Binomial[n, 2]*(z/Exp[z])^n/n!, {n, 0, m+1}];
egf = (1/6)*(z^4/(1-z)^3)*A[z] + (1/2)*(z^4/(1-z)^2)*(A'[z] - A[z]) + (1/6)*(z^6/(1-z)^3)*(A'''[z] - 3*A''[z] + 3*A'[z] - A[z]) + (1/2)*(z^5/(1 - z)^4)*(A''[z] - 2*A'[z] + A[z]) + (1/6)*(z^4/(1-z)^4)*(A'[z] - A[z]) + (1/2)*(z^5/(1-z)^5)*(A'[z] - A[z]); s = egf + O[z]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)

E.g.f.: (1/6)*(z^4/(1-z)^3)*A(z) + (1/2)*(z^4/(1-z)^2)*(A'(z)-A(z)) + (1/6)*(z^6/(1-z)^3)*(A'''(z)-3*A''(z)+3*A'(z)-A(z)) + (1/2)*(z^5/(1-z)^4)*(A''(z)-2*A'(z)+A(z)) + (1/6)*(z^4/(1-z)^4)*(A'(z)-A(z)) + (1/2)*(z^5/(1-z)^5)*(A'(z)-A(z)) where A(z) = exp(1/2*z^2) * Sum_{n>=0} 2^binomial(n, 2)*(z/exp(z))^n/n!.

A325115 Number of simple graphs on n unlabeled nodes with exactly 1 endpoint (node of degree 1).

Original entry on oeis.org

0, 0, 0, 1, 6, 35, 260, 2934, 53768, 1707627, 96648020, 9886429142, 1842161884708, 629505254017556, 397043155634566696, 464930596621838689900, 1016021072554513545893264, 4162479064042009639168386134, 32096876145378032622994745784856

Offset: 1

Andrew Howroyd, Sep 04 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50

Column k=1 of A327371.

Cf. A277072 (labeled case), A325125.

Terms a(11) and beyond from Andrew Howroyd, Feb 02 2021

cp's OEIS Frontend

A327369 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A277073 Number of n-node labeled graphs with two endpoints.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A277074 Number of n-node labeled graphs with three endpoints.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A325115 Number of simple graphs on n unlabeled nodes with exactly 1 endpoint (node of degree 1).

Views

Author

Keywords

Links

Crossrefs

Extensions