A294217 -id:A294217 - cp's OEIS frontend

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

1, 1, 0, 1, 0, 1, 2, 0, 2, 0, 5, 1, 3, 1, 1, 16, 6, 7, 2, 3, 0, 78, 35, 25, 8, 7, 2, 1, 588, 260, 126, 40, 20, 6, 4, 0, 8047, 2934, 968, 263, 92, 25, 13, 3, 1, 205914, 53768, 11752, 2434, 596, 140, 47, 12, 5, 0, 10014882, 1707627, 240615, 34756, 5864, 1084, 256, 58, 21, 4, 1

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
     1;
     1,    0;
     1,    0,   1;
     2,    0,   2,   0;
     5,    1,   3,   1,  1;
    16,    6,   7,   2,  3,  0;
    78,   35,  25,   8,  7,  2,  1;
   588,  260, 126,  40, 20,  6,  4, 0;
  8047, 2934, 968, 263, 92, 25, 13, 3, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Gus Wiseman, The graphs counted in row 5 (isolated vertices not shown).

Row sums are A000088.
Row sums without the first column are A141580.
Columns k = 0..2 are A004110, A325115, A325125.
Column k = n is A059841.
Column k = n - 1 is A028242.
The labeled version is A327369.
The covering case is A327372.
Cf. A055540, A059167, A245797, A294217, A327227, A327370.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)*(1-x^2*y)/(1-x^2*y^2)}
T(n)={my(v=Vec(G(n))); vector(#v, n, Vecrev(v[n], n))}
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 22 2021

Column-wise partial sums of A327372.

Terms a(21) and beyond from Andrew Howroyd, Sep 05 2019

A263293 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and maximum vertex degree k, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 4, 4, 1, 2, 8, 12, 11, 1, 3, 15, 43, 60, 34, 1, 3, 25, 121, 360, 378, 156, 1, 4, 41, 378, 2166, 4869, 3843, 1044, 1, 4, 65, 1095, 14306, 68774, 113622, 64455, 12346, 1, 5, 100, 3441, 104829, 1141597, 3953162, 4605833, 1921532, 274668

Offset: 1

Christian Stump, Oct 13 2015

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A327366. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 10 2020

			Triangle begins:
1,
1,    1,
1,    1,    2,
1,    2,    4,    4,
1,    2,    8,   12,   11,
1,    3,   15,   43,   60,   34,
1,    3,   25,  121,  360,  378,  156,
1,    4,   41,  378, 2166, 4869, 3843, 1044,
...

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)
FindStat - Combinatorial Statistic Finder, The degree of a graph
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A000088 (simple graphs on n nodes).
Column k=2 is A324740.
Diagonals include A000088(n-1), A324693, A324670.
Cf. A294217 (triangle of n-node minimum vertex degree counts).
Cf. A327366.

From Geoffrey Critzer, Sep 10 2016: (Start)
G.f. for column k=0: A(x)=1/(1-x).
G.f. for column k=1: B(x)=x^2/((1-x^2)(1-x)).
G.f. for column k=2: 1/((1-x)(1-x^2))*Product_{i>=3} 1/(1-x^i)^2 - B(x) - A(x).
(End)
T(n, 0) = 1.
T(n, n - 1) = A000088(n - 1).
T(n, k) = A294217(n, n - 1 - k). - Andrew Howroyd, Sep 03 2019

Rows n=9 and 10 added by Eric W. Weisstein, Oct 24 2017

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

Original entry on oeis.org

0, 1, 0, 6, 4, 50, 66, 532, 1016, 6876, 16750, 104456, 303612, 1821976, 6067166, 35857200, 133160176, 785514512, 3192117966, 18948962656, 83099447300, 498931946016, 2336474411062, 14234346694976, 70598633745576, 437304764440000, 2282139344678726, 14390600621415552

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

Graphs consist of zero or more paths on two nodes each and either a single isolated node or a star with two or more peripheral nodes. - Andrew Howroyd, Sep 05 2019

			The a(4) = 4 edge-sets:
  {12,13,14}
  {12,23,24}
  {13,23,34}
  {14,24,34}

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

Column k = n - 1 of A327369.
The unlabeled version is A028242.
Cf. A006125, A059167, A100743, A245797, A294217, A327227, A327377.

f:= gfun:-rectoproc({(n-1)*(n-2)*a(n)-n*(n-3)*(n-2)*a(n-1)-n*(n-1)^2*a(n-2)+(2*n-7)*n*(n-1)*(n-2)*a(n-3)-n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5)=0, a(0)=0, a(1)=1, a(2)=0, a(3)=6, a(4)=4},a(n),remember):
map(f, [$0..40]); # Robert Israel, Sep 06 2019

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Count[Length/@Split[Sort[Join@@#]],1]==n-1&]],{n,0,5}]
With[{nn=30},CoefficientList[Series[x Exp[x^2/2](Exp[x]-x),{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Apr 28 2022 *)

seq(n)={Vec(serlaplace(x*exp(x^2/2 + O(x^n))*(exp(x + O(x^n))-x)), -(n+1))} \\ Andrew Howroyd, Sep 05 2019

E.g.f.: x*exp(x^2/2)*(exp(x) - x). - Andrew Howroyd, Sep 05 2019

(n-1)*(n-2)*a(n) - n*(n-3)*(n-2)*a(n-1) - n*(n-1)^2*a(n-2) + (2*n-7)*n*(n-1)*(n-2)*a(n-3) - n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5) = 0. - Robert Israel, Sep 06 2019

Terms a(8) and beyond from Andrew Howroyd, Sep 05 2019

A327366 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 23, 31, 9, 1, 0, 256, 515, 227, 25, 1, 0, 5319, 15381, 10210, 1782, 75, 1, 0, 209868, 834491, 815867, 221130, 15564, 231, 1, 0, 15912975, 83016613, 116035801, 47818683, 5499165, 151455, 763, 1, 0, 2343052576, 15330074139, 29550173053, 18044889597, 3291232419, 158416629, 1635703, 2619, 1, 0

Offset: 0

Gus Wiseman, Sep 04 2019

The minimum vertex-degree of the empty graph is infinity. It has been included here under k = 0. - Andrew Howroyd, Mar 09 2020

			Triangle begins:
     1
     1     0
     1     1     0
     4     3     1     0
    23    31     9     1     0
   256   515   227    25     1     0
  5319 15381 10210  1782    75     1     0

Andrew Howroyd, Table of n, a(n) for n = 0..230 (rows n = 0..20)
Gus Wiseman, The graphs with 4 vertices and minimum vertex-degree k (row n = 4).

Row sums are A006125.
Row sums without the first column are A006129.
Row sums without the first two columns are A100743.
Column k = 0 is A327367(n > 0).
Column k = 1 is A327227.
The unlabeled version is A294217.
Cf. A059167, A245797, A327069, A327103, A327334, A327369.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],k==If[#=={}||Union@@#!=Range[n],0,Min@@Length/@Split[Sort[Join@@#]]]&]],{n,0,5},{k,0,n}]

GraphsByMaxDegree(n)={
  local(M=Map(Mat([x^0, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(merge(r, p, v)=acc(p + sum(i=1, poldegree(p)-r-1, polcoef(p, i)*(1-x^i)), v));
  my(recurse(r, p, i, q, v, e)=if(i<0, merge(r, x^e+q, v), my(t=polcoef(p, i)); for(k=0, t, self()(r, p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+k))));
  for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(n-k, p, poldegree(p), 0, src[i, 2], 0)));
  Mat(M);
}
Row(n)={if(n==0, [1], my(M=GraphsByMaxDegree(n), u=vector(n+1)); for(i=1, matsize(M)[1], u[n-poldegree(M[i,1])]+=M[i,2]); u)}
{ for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Mar 09 2020

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

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

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 1, 11, 5, 4, 1, 2, 0, 62, 29, 18, 6, 4, 2, 1, 510, 225, 101, 32, 13, 4, 3, 0, 7459, 2674, 842, 223, 72, 19, 9, 3, 1, 197867, 50834, 10784, 2171, 504, 115, 34, 9, 4, 0, 9808968, 1653859, 228863, 32322, 5268, 944, 209, 46, 16, 4, 1

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
   1
   0  0
   0  0  1
   1  0  1  0
   3  1  1  1  1
  11  5  4  1  2  0

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Gus Wiseman, The unlabeled graphs covering 5 vertices with k endpoints.

Row sums are A002494.
Column k = 0 is A261919.
The non-covering version is A327371.
The labeled version is A327377.
Cf. A000088, A004110, A294217, A327227, A327369, A327370.

\\ Needs G(n) defined in A327371.
T(n)={my(v=Vec(G(n)*(1 - x))); vector(#v, n, Vecrev(v[n], n))}
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 11 2024

Column-wise first differences of A327371.

Terms a(21) and beyond from Andrew Howroyd, Sep 11 2019

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Original entry on oeis.org

0, 1, 1, 4, 12, 60, 378, 3843, 64455, 1921532, 104098702, 10348794144, 1893781768084, 639954768875644, 400905675004630820, 467554784370658979194, 1019317687720204607541914, 4170177760438554428852944352, 32130458453030025927403299167172

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Minimum Vertex Degree
Gus Wiseman, The a(2) = 1 through a(5) = 12 unlabeled graphs with minimum degree 1.

Column k = 1 of A294217.
A diagonal of A263293.
The labeled version is A327227.
The generalization to set-systems is A327335, with covering case A327230.
Unlabeled covering graphs are A002494.
Cf. A000088, A004110, A100743, A141580, A245797, A261919, A327105, A327362, A327364, A327366, A327372.

a(n) = A002494(n) - A261919(n).

First differences of A141580. - Andrew Howroyd, Jan 11 2021

A324670 Number of simple graphs on n unlabeled nodes with minimum degree exactly 2.

Original entry on oeis.org

0, 0, 1, 2, 8, 43, 360, 4869, 113622, 4605833, 325817259, 40350371693, 8825083057727, 3447229161054412, 2432897732375453872, 3135299553791882831175, 7445569254636418368355175, 32831169277561326131677454356, 270499962116368309216399255404116

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Eric Weisstein's World of Mathematics, Minimum Vertex Degree

Column k=2 of A294217.
A diagonal of A263293.
Cf. A005637, A007111, A261919.

a(n) = A261919(n) - A007111(n).

A324740 Number of simple graphs on n unlabeled nodes with maximum degree exactly 2.

Original entry on oeis.org

0, 0, 2, 4, 8, 15, 25, 41, 65, 100, 150, 225, 327, 474, 678, 962, 1348, 1884, 2602, 3581, 4889, 6644, 8968, 12064, 16124, 21476, 28462, 37585, 49407, 64747, 84495, 109936, 142522, 184226, 237350, 304977, 390669, 499169, 636039, 808468, 1024996, 1296573, 1636151

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Column k=2 of A263293.
A diagonal of A294217.
Cf. A003292, A008619.

seq(n) = Vec( (1-x)*(1-x^2)/prod(k=1, n, 1 - x^k + O(x*x^n))^2 - 1/((1-x)*(1-x^2)), -n) \\ Andrew Howroyd, Sep 03 2019

a(n) = A003292(n) - A008619(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A263293 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and maximum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A327366 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Views

Author

Keywords

Links

Crossrefs

Formula

A324670 Number of simple graphs on n unlabeled nodes with minimum degree exactly 2.

Views

Author

Keywords

Links

Crossrefs

Formula

A324740 Number of simple graphs on n unlabeled nodes with maximum degree exactly 2.

Views

Author

Keywords

Links

Crossrefs

Programs