A141580 -id:A141580 - 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

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 3, 28, 475, 14646, 813813, 82060392, 15251272983, 5312295240010, 3519126783483377, 4487168285715524124, 11116496280631563128723, 53887232400918561791887118, 513757147287101157620965656285, 9668878162669182924093580075565776

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

A graph is covering if the vertex set is the union of the edge set, so there are no isolated vertices.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 28 connected covering graphs with at least one endpoint.

The non-connected version is A327227.
The non-covering version is A327364.
Graphs with endpoints are A245797.
Connected covering graphs are A001187.
Connected graphs with bridges are A327071.
Cf. A004110, A059166, A006125, A006129, A059166, A100743, A141580, A322395, A327105, A327229, A327230, A327366, A327369, A327377.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

seq(n)={Vec(serlaplace(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k! + O(x*x^n))) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Inverse binomial transform of A327364.

a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

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

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 6, 46, 655, 17991, 927416, 89009740, 16020407709, 5468601546685, 3578414666656214, 4529751815161579194, 11175105490563109463875, 54043272967471942825421219, 514566625051705610110588073460, 9677104749727084630538798805505880

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

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

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

The covering case is A327362.
Graphs with endpoints are A245797.
Graphs with connected edge-set are A287689.
Connected graphs with bridges are A327071.
Covering graphs with endpoints are A327227.
Cf. A001187, A059167, A141580, A322395, A327148, A327335, A327369.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

seq(n)={my(x=x + O(x*x^n)); Vec(serlaplace(exp(x)*(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!)) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x))^k/k!)))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Binomial transform of A327362.

Terms a(7) 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

A327379 Number of labeled non-mating-type graphs with n vertices.

Original entry on oeis.org

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset: 1

Gus Wiseman, Sep 05 2019

nonn

A mating-type graph has all different rows in its adjacency matrix.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(4) = 32 non-mating-type graphs.

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!UnsameQ@@AdjacencyMatrix[Graph[Range[n],#]]&]],{n,5}]

a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

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

A240168 T(n,k) is the number of unlabeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 5, 4, 2, 1, 1, 2, 4, 8, 13, 15, 16, 11, 5, 2, 1, 1, 2, 4, 9, 19, 35, 55, 75, 83, 72, 51, 29, 13, 5, 2, 1, 1, 2, 4, 10, 22, 50, 105, 196, 338, 511, 649, 695, 627, 473, 304, 172, 83, 35, 14, 5, 2, 1

Offset: 1

Chai Wah Wu, Aug 02 2014

The length of the rows are 1,1,2,4,7,11,16,22,...: (n-1)*(n-2)/2 + 1 = A152947(n).

T(n,k) = 0 if k > (n-1)*(n-2)/2 + 1. (Cf. A245796)

			First few rows of irregular triangle are:
..0
..1
..1....1
..1....2....2....1
..1....2....3....5....4....2....1
..1....2....4....8...13...15...16...11....5....2....1
..1....2....4....9...19...35...55...75...83...72...51...29...13....5....2....1
...

Cf. A245796. Sum of n-th row is equal to A141580(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

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

A327379 Number of labeled non-mating-type graphs with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A240168 T(n,k) is the number of unlabeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

Views

Author

Keywords

Comments

Examples

Crossrefs