A327229 -id:A327229 - 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.

A094574 Number of (<=2)-covers of an n-set.

Original entry on oeis.org

1, 1, 5, 40, 457, 6995, 136771, 3299218, 95668354, 3268445951, 129468914524, 5868774803537, 301122189141524, 17327463910351045, 1109375488487304027, 78484513540137938209, 6098627708074641312182, 517736625823888411991202, 47791900951140948275632148

Offset: 0

Goran Kilibarda, Vladeta Jovovic, May 12 2004

nonn

Also the number of strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. For example, the a(2) = 5 strict multiset partitions of {1, 1, 2, 2} are (1122), (1)(122), (2)(112), (11)(22), (1)(2)(12). - Gus Wiseman, Jul 18 2018

			From _Gus Wiseman_, Sep 02 2019: (Start)
These are set-systems covering {1..n} with vertex-degrees <= 2. For example, the a(3) = 40 covers are:
  {123}  {1}{23}    {1}{2}{3}     {1}{2}{3}{12}
         {2}{13}    {1}{2}{13}    {1}{2}{3}{13}
         {3}{12}    {1}{2}{23}    {1}{2}{3}{23}
         {1}{123}   {1}{3}{12}    {1}{2}{13}{23}
         {12}{13}   {1}{3}{23}    {1}{2}{3}{123}
         {12}{23}   {2}{3}{12}    {1}{3}{12}{23}
         {13}{23}   {2}{3}{13}    {2}{3}{12}{13}
         {2}{123}   {1}{12}{23}
         {3}{123}   {1}{13}{23}
         {12}{123}  {1}{2}{123}
         {13}{123}  {1}{3}{123}
         {23}{123}  {2}{12}{13}
                    {2}{13}{23}
                    {2}{3}{123}
                    {3}{12}{13}
                    {3}{12}{23}
                    {12}{13}{23}
                    {1}{23}{123}
                    {2}{13}{123}
                    {3}{12}{123}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..300

Row n=2 of A219585. - Alois P. Heinz, Nov 23 2012
Dominated by A003465.
Graphs with vertex-degrees <= 2 are A136281.
Cf. A002718, A007716, A020554, A020555, A050535, A094574, A136284, A316974, A327104, A327106, A327229.
Main diagonal of A346517.

facs[n_]:=facs[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[Array[Prime,n,1,Times]^2],UnsameQ@@#&]],{n,0,6}] (* Gus Wiseman, Jul 18 2018 *)
m = 20;
a094577[n_] := Sum[Binomial[n, k]*BellB[2 n - k], {k, 0, n}];
egf = Exp[(1 - Exp[x])/2]*Sum[a094577[n]*(x/2)^n/n!, {n, 0, m}] + O[x]^m;
CoefficientList[egf + O[x]^m, x]*Range[0, m-1]! (* Jean-François Alcover, May 13 2019 *)

Row sums of A094573.

E.g.f: exp(-1-1/2*(exp(x)-1))*Sum(exp(x*binomial(n+1, 2))/n!, n=0..infinity) or exp((1-exp(x))/2)*Sum(A094577 (n)*(x/2)^n/n!, n=0..infinity).

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}]

A100743 Number of labeled n-vertex graphs without vertices of degree <=1.

Original entry on oeis.org

1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 03 2005

nonn

			From _Gus Wiseman_, Aug 18 2019: (Start)
The a(4) = 10 edge-sets:
  {12,13,24,34}
  {12,14,23,34}
  {13,14,23,24}
  {12,13,14,23,24}
  {12,13,14,23,34}
  {12,13,14,24,34}
  {12,13,23,24,34}
  {12,14,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}
(End)

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

Graphs without isolated nodes are A006129.
The connected case is A059166.
Graphs without endpoints are A059167.
Labeled graphs with endpoints are A245797.
The unlabeled version is A261919.
Cf. A095983, A136284, A322395, A327079, A327107, A327227, A327229, A327230.
Cf. A095983, A322395.

m = 13;
egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];
s = egf + O[x]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}] (* Gus Wiseman, Aug 18 2019 *)

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

E.g.f.: exp(-x+x^2/2)*(Sum_{n>=0} 2^(n*(n-1)/2)*(x/exp(x))^n/n!). - Vladeta Jovovic, Jan 26 2006
Exponential transform of A059166. - Gus Wiseman, Aug 18 2019
Inverse binomial transform of A059167. - Gus Wiseman, Sep 02 2019

Terms a(14) and beyond from Andrew Howroyd, Sep 04 2019

A327105 BII-numbers of set-systems with minimum degree 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 46, 48, 49, 50, 56, 57, 58, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 80, 81, 88, 89, 96, 98, 104, 106, 128

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 minimum degree 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  18: {{2},{1,3}}
  19: {{1},{2},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}

Positions of 1's in A327103.
BII-numbers for minimum degree > 1 are A327107.
Graphs with minimum degree 1 are counted by A245797, with covering case A327227.
Set-systems with minimum degree 1 are counted by A327228, with covering case A327229.
Cf. A000120, A029931, A048793, A058891, A070939, A326031, A326701, A326786, A327041, A327104, A327230.

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

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

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 1, 0, 24, 1984

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. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain in a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity.

			The a(3) = 24 set-systems:
  {12}{13}  {1}{12}{13}  {1}{2}{12}{13}  {1}{2}{3}{12}{13}
  {12}{23}  {1}{12}{23}  {1}{2}{12}{23}  {1}{2}{3}{12}{23}
  {13}{23}  {1}{13}{23}  {1}{2}{13}{23}  {1}{2}{3}{13}{23}
            {2}{12}{13}  {1}{3}{12}{13}
            {2}{12}{23}  {1}{3}{12}{23}
            {2}{13}{23}  {1}{3}{13}{23}
            {3}{12}{13}  {2}{3}{12}{13}
            {3}{12}{23}  {2}{3}{12}{23}
            {3}{13}{23}  {2}{3}{13}{23}

The BII-numbers of these set-systems are A327098.
The same for cut-connectivity 2 is A327113.
The non-covering version is A327128.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327114, A327126, A327229.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]

Inverse binomial transform of A327128.

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

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

A094574 Number of (<=2)-covers of an n-set.

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

A100743 Number of labeled n-vertex graphs without vertices of degree <=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A327105 BII-numbers of set-systems with minimum degree 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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