A327105 -id:A327105 - cp's OEIS frontend

A245797 The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1.

0, 1, 6, 49, 710, 19011, 954184, 90154415, 16108626420, 5481798833245, 3582369649269620, 4532127781040045649, 11177949079089720090800, 54050029251399545975868271, 514598463471970554205910304780, 9677402372862708729859372687791391

Offset: 1

Chai Wah Wu, Aug 01 2014

nonn

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

Equal to row sums of A245796.
The covering case is A327227.
The connected case is A327362.
The generalization to set-systems is A327228.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327229, A327230.

m = 16;
egf = Exp[x^2/2]*Sum[2^Binomial[n, 2]*(x/Exp[x])^n/n!, {n, 0, m}];
A059167[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
a[n_] := 2^(n(n-1)/2) - A059167[n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}] (* Gus Wiseman, Sep 11 2019 *)

a(n) = 2^(n*(n+1)/2) - A059167(n).

Binomial transform of A327227 (assuming a(0) = 0).

a(9)-a(16) from Andrew Howroyd, Oct 26 2017

A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf.

Original entry on oeis.org

0, 0, 1, 3, 31, 515, 15381, 834491, 83016613, 15330074139, 5324658838645, 3522941267488973, 4489497643961740521, 11119309286377621015089, 53893949089393110881259181, 513788884660608277842596504415, 9669175277199248753133328740702449

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Covering means there are no isolated vertices.
A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also graphs with minimum vertex-degree 1.

			The a(4) = 31 edge-sets:
  {12,34}  {12,13,14}  {12,13,14,23}
  {13,24}  {12,13,24}  {12,13,14,24}
  {14,23}  {12,13,34}  {12,13,14,34}
           {12,14,23}  {12,13,23,24}
           {12,14,34}  {12,13,23,34}
           {12,23,24}  {12,14,23,24}
           {12,23,34}  {12,14,24,34}
           {12,24,34}  {12,23,24,34}
           {13,14,23}  {13,14,23,34}
           {13,14,24}  {13,14,24,34}
           {13,23,24}  {13,23,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

Column k=1 of A327366.
The non-covering version is A245797.
The unlabeled version is A324693.
The generalization to set-systems is A327229.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327228, A327230.

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

Inverse binomial transform of A245797, if we assume A245797(0) = 0.

A327103 Minimum vertex-degree in the set-system with BII-number n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2

Offset: 0

Gus Wiseman, Aug 26 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

In a set-system, the degree of a vertex is the number of edges containing it.

			The BII-number of {{2},{3},{1,2},{1,3},{2,3}} is 62, and its degrees are (2,3,3), so a(62) = 2.

The maximum vertex-degree is A327104.
Positions of 1's are A327105.
Positions of terms > 1 are A327107.
Cf. A000120, A048793, A058891, A070939, A326031, A326701, A326783, A326786, A327041, A327228, A327229.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[If[n==0,0,Min@@Length/@Split[Sort[Join@@bpe/@bpe[n]]]],{n,0,100}]

A327229 Number of set-systems covering n vertices with at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 4, 50, 3069, 2521782, 412169726428, 4132070622008664529903, 174224571863520492185852863478334475199686, 133392486801388257127953774730008469744261637221272599199572772174870315402893538

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Covering means there are no isolated vertices.
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also covering set-systems with minimum vertex-degree 1.

			The a(2) = 4 set-systems:
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}

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

The non-covering version is A327228.
The specialization to simple graphs is A327227.
The unlabeled version is A327230.
BII-numbers of these set-systems are A327105.
Cf. A003465, A245797, A327079, A327098, A327103, A327107, A327197.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,3}]

Inverse binomial transform of A327228.

Terms a(5) and beyond from Andrew Howroyd, Jan 21 2023

A327230 Number of non-isomorphic set-systems covering n vertices with at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 3, 14, 198

Offset: 0

Gus Wiseman, Sep 01 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.

Also covering set-systems with minimum vertex-degree 1.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 14 set-systems:
  {{1}}  {{1,2}}      {{1,2,3}}
         {{1},{2}}    {{1},{2,3}}
         {{2},{1,2}}  {{1},{2},{3}}
                      {{1,3},{2,3}}
                      {{3},{1,2,3}}
                      {{1},{3},{2,3}}
                      {{2,3},{1,2,3}}
                      {{2},{1,3},{2,3}}
                      {{2},{3},{1,2,3}}
                      {{3},{1,3},{2,3}}
                      {{1},{2},{3},{2,3}}
                      {{3},{2,3},{1,2,3}}
                      {{2},{3},{1,3},{2,3}}
                      {{2},{3},{2,3},{1,2,3}}

Unlabeled covering set-systems are A055621.
The labeled version is A327229.
The non-covering version is A327335 (partial sums).
Cf. A002494, A245797, A261919, A283877, A327103, A327105, A327197, A327227, A327228.

A327228 Number of set-systems with n vertices and at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 6, 65, 3297, 2537672, 412184904221, 4132070624893905681577, 174224571863520492218909428465944685216436, 133392486801388257127953774730008469745829658368044283629394202488602260177922751

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.

Also set-systems with minimum covered vertex-degree 1.

			The a(2) = 6 set-systems:
  {{1}}
  {{2}}
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}

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

The covering version is A327229.
The specialization to simple graphs is A245797.
BII-numbers of these set-systems are A327105.
Cf. A058891, A059167, A327098, A327103, A327104, A327107, A327197, A327227, A327230, A330059.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,4}]

Binomial transform of A327229.

a(n) = A058891(n+1) - A330059(n). - Andrew Howroyd, Jan 21 2023

Terms a(5) and beyond from Andrew Howroyd, Jan 21 2023

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

A327107 BII-numbers of set-systems with minimum vertex-degree > 1.

Original entry on oeis.org

7, 25, 30, 31, 42, 45, 47, 51, 52, 53, 54, 55, 59, 60, 61, 62, 63, 75, 76, 77, 78, 79, 82, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 97, 99, 100, 101, 102, 103, 105, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124

Offset: 1

Gus Wiseman, Aug 26 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

In a set-system, the degree of a vertex is the number of edges containing it.

			The sequence of all set-systems with maximum degree > 1 together with their BII-numbers begins:
   7: {{1},{2},{1,2}}
  25: {{1},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  42: {{2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  47: {{1},{2},{1,2},{3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  59: {{1},{2},{3},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}
  75: {{1},{2},{3},{1,2,3}}
  76: {{1,2},{3},{1,2,3}}

Positions of terms > 1 in A327103.
BII-numbers for minimum degree 1 are A327105.
Graphs with minimum degree > 1 are counted by A059167.
Cf. A000120, A029931, A048793, A058891, A070939, A245797, A326031, A326701, A326786, A327041, A327104, A327227-A327230.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100],Min@@Length/@Split[Sort[Join@@bpe/@bpe[#]]]>1&]

A327335 Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 4, 18, 216

Offset: 0

Gus Wiseman, Sep 02 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.

Also covering set-systems with minimum covered vertex-degree 1.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 18 set-systems:
  {{1}}  {{1}}        {{1}}
         {{1,2}}      {{1,2}}
         {{1},{2}}    {{1},{2}}
         {{1},{1,2}}  {{1,2,3}}
                      {{1},{1,2}}
                      {{1},{2,3}}
                      {{1},{1,2,3}}
                      {{1,2},{1,3}}
                      {{1},{2},{3}}
                      {{1,2},{1,2,3}}
                      {{1},{2},{1,3}}
                      {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{2},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1},{2},{3},{1,2}}
                      {{1},{2},{1,2},{1,3}}
                      {{1},{2},{1,2},{1,2,3}}

Unlabeled set-systems are A000612.
The labeled version is A327228.
The covering version is A327230 (first differences).
Cf. A002494, A245797, A261919, A283877, A327103, A327105, A327197, A327227, A327229, A327336.

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

cp's OEIS Frontend

A245797 The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A327103 Minimum vertex-degree in the set-system with BII-number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327229 Number of set-systems covering n vertices with at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327230 Number of non-isomorphic set-systems covering n vertices with at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327228 Number of set-systems with n vertices and at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A327107 BII-numbers of set-systems with minimum vertex-degree > 1.

Views

Author

Keywords

Comments

Examples