cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 15 results. Next

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

Original entry on oeis.org

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

Views

Author

Chai Wah Wu, Aug 01 2014

Keywords

Crossrefs

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.

Programs

  • Mathematica
    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 *)

Formula

a(n) = 2^(n*(n+1)/2) - A059167(n).
Binomial transform of A327227 (assuming a(0) = 0).

Extensions

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

A327111 BII-numbers of set-systems with spanning edge-connectivity 1.

Original entry on oeis.org

1, 2, 4, 5, 6, 7, 8, 16, 17, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 88, 89, 90, 91, 96, 97, 98, 99
Offset: 1

Views

Author

Gus Wiseman, Aug 25 2019

Keywords

Comments

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.
The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty set-system.

Examples

			The sequence of all set-systems with spanning edge-connectivity 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  32: {{2,3}}
		

Crossrefs

Graphs with spanning edge-connectivity >= 2 are counted by A095983.
BII-numbers for vertex-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Set-systems with spanning edge-connectivity 2 are counted by A327130.
Graphs with spanning edge-connectivity 1 are counted by A327145.
Graphs with spanning edge-connectivity 2 are counted by A327146.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
    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]]]]]]]]];
    spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
    Select[Range[0,100],spanEdgeConn[Union@@bpe/@bpe[#],bpe/@bpe[#]]==1&]

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

Views

Author

Gus Wiseman, Sep 01 2019

Keywords

Comments

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.

Examples

			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}
		

Crossrefs

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.

Programs

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

Formula

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

A327125 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and cut-connectivity k.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 26, 28, 9, 0, 1, 296, 490, 212, 25, 0, 1, 6064, 15336, 9600, 1692, 75, 0, 1, 230896
Offset: 0

Views

Author

Gus Wiseman, Aug 25 2019

Keywords

Comments

We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

Examples

			Triangle begins:
    1
    0   1
    1   0   1
    4   3   0   1
   26  28   9   0   1
  296 490 212  25   0   1
		

Crossrefs

After the first column, same as A327126.
The unlabeled version is A327127.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = 1.
Column k = 1 is A327114, if we assume A327114(1) = 1.
Row sums without the first column are A001187.
Row sums without the first two columns are A013922.
Different from A327069.

Programs

  • Mathematica
    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],{2}]],cutConnSys[Range[n],#]==k&]],{n,0,4},{k,0,n}]

Extensions

a(21)-a(28) from Robert Price, May 20 2021
a(1) and a(2) corrected by Robert Price, May 20 2021

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 0, 0, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040
Offset: 0

Views

Author

Gus Wiseman, Aug 25 2019

Keywords

Comments

The cut-connectivity of a graph is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty graph.

Crossrefs

Column k = 1 of A327126.
The unlabeled version is A052442, if we assume A052442(2) = 0.
Connected non-separable graphs are A013922.
BII-numbers for cut-connectivity 1 are A327098.
Set-systems with cut-connectivity 1 are counted by A327197.
Labeled simple graphs with vertex-connectivity 1 are A327336.

Programs

  • Mathematica
    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]]]]]]]]];
    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],{2}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]
  • PARI
    seq(n)={my(g=log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))); Vec(serlaplace(g-intformal(1+log(x/serreverse(x*deriv(g))))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Formula

a(n) = A001187(n) - A013922(n), if we assume A001187(1) = 0.

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

Views

Author

Gus Wiseman, Sep 01 2019

Keywords

Comments

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.

Examples

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

Crossrefs

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.

Programs

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

Formula

Inverse binomial transform of A327228.

Extensions

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

A327082 BII-numbers of set-systems with cut-connectivity 2.

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 256, 257, 384, 385, 512, 514, 640, 642, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850
Offset: 1

Views

Author

Gus Wiseman, Aug 20 2019

Keywords

Comments

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.
We define the cut-connectivity (A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039), this is the same as vertex-connectivity (A327334, A327051).

Examples

			The sequence of all set-systems with cut-connectivity 2 together with their BII-numbers begins:
    4: {{1,2}}
    5: {{1},{1,2}}
    6: {{2},{1,2}}
    7: {{1},{2},{1,2}}
   16: {{1,3}}
   17: {{1},{1,3}}
   24: {{3},{1,3}}
   25: {{1},{3},{1,3}}
   32: {{2,3}}
   34: {{2},{2,3}}
   40: {{3},{2,3}}
   42: {{2},{3},{2,3}}
  256: {{1,4}}
  257: {{1},{1,4}}
  384: {{4},{1,4}}
  385: {{1},{4},{1,4}}
  512: {{2,4}}
  514: {{2},{2,4}}
  640: {{4},{2,4}}
  642: {{2},{4},{2,4}}
The first term involving an edge of size 3 is 832: {{1,2,3},{1,4},{2,4}}.
		

Crossrefs

Positions of 2's in A326786.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for spanning edge-connectivity 2 are A327108.
The cut-connectivity 1 version is A327098.
The cut-connectivity > 1 version is A327101.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
    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]]]]]]]]];
    vertConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
    Select[Range[0,100],vertConnSys[bpe/@bpe[#]]==2&]

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Original entry on oeis.org

0, 0, 1, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040, 9672967865350359173180572164444160
Offset: 0

Views

Author

Gus Wiseman, Sep 02 2019

Keywords

Comments

Same as A327114 except a(2) = 1.
The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton.

Examples

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

Crossrefs

Column k = 1 of A327334.
The unlabeled version is A052442.
Connected non-separable graphs are A013922.
Set-systems with vertex-connectivity 1 are A327128.
Labeled simple graphs with cut-connectivity 1 are A327114.

Programs

  • Mathematica
    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]]]]]]]]];
    vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],vertConnSys[Range[n],#]==1&]],{n,0,4}]

Extensions

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

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107
Offset: 1

Views

Author

Gus Wiseman, Aug 22 2019

Keywords

Comments

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.
A set-system is 2-cut-connected if any single vertex can be removed (along with any empty edges) without making the set-system disconnected or empty. Except for cointersecting set-systems (A326853), this is the same as 2-vertex-connectivity.

Examples

			The sequence of all 2-cut-connected set-systems together with their BII-numbers begins:
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{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}}
  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}}
		

Crossrefs

Positions of numbers >= 2 in A326786.
2-cut-connected graphs are counted by A013922, if we assume A013922(2) = 0.
2-cut-connected integer partitions are counted by A322387.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
The labeled cut-connectivity triangle is A327125, with unlabeled version A327127.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
    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]}]]];
    Select[Range[0,100],cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]>=2&]

Formula

If (*) is intersection and (-) is complement, we have A327101 * A326704 = A326751 - A058891, i.e., the intersection of A327101 (this sequence) with A326704 (antichains) is the complement of A058891 (singletons) in A326751 (blobs).

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 2, 0, 1, 13, 11, 7, 2, 0, 1
Offset: 0

Views

Author

Gus Wiseman, Aug 25 2019

Keywords

Comments

A graph with one vertex and no edges is considered to be connected. Except for complete graphs, this is the same as vertex-connectivity (A259862).
There are two ways to define (vertex) connectivity: the minimum size of a vertex cut, and the minimum of the maximum number of internally disjoint paths between two distinct vertices. For non-complete graphs they coincide, which is tremendously useful. For complete graphs with at least 2 vertices, there are no cuts but the second method still works so it is customary to use it to justify the connectivity of K_n being n-1. - Brendan McKay, Aug 28 2019.

Examples

			Triangle begins:
   1
   0  1
   1  0  1
   2  1  0  1
   5  3  2  0  1
  13 11  7  2  0  1
		

Crossrefs

Row sums are A000088.
Column k = 0 is A000719, if we assume A000719(0) = 1.
Column k = 1 is A052442, if we assume A052442(1) = 1 and A052442(2) = 0.
The labeled version is A327125.
A more standard version (zeros removed) is A259862.
Showing 1-10 of 15 results. Next