A327103 -id:A327103 - cp's OEIS frontend

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

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

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.

A327106 BII-numbers of set-systems with maximum degree 2.

Original entry on oeis.org

5, 6, 7, 13, 14, 15, 17, 19, 20, 22, 24, 25, 26, 27, 28, 30, 34, 35, 36, 37, 40, 41, 42, 43, 44, 45, 48, 49, 50, 51, 52, 65, 66, 67, 68, 72, 73, 74, 75, 76, 80, 82, 96, 97, 133, 134, 135, 141, 142, 143, 145, 147, 148, 150, 152, 153, 154, 155, 156, 158, 162

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 2 together with their BII-numbers begins:
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  17: {{1},{1,3}}
  19: {{1},{2},{1,3}}
  20: {{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  26: {{2},{3},{1,3}}
  27: {{1},{2},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  34: {{2},{2,3}}
  35: {{1},{2},{2,3}}
  36: {{1,2},{2,3}}
  37: {{1},{1,2},{2,3}}

Positions of 2's in A327104.
Graphs with maximum degree 2 are counted by A136284.
Cf. A000120, A048793, A058891, A070939, A326031, A326701, A326786, A327041, A327103.

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

A327438 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 3, 1, 6, 2, 1, 15, 7, 5, 2, 52, 53, 62, 31, 9, 1, 1

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other.

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 set-system that is disconnected or covers fewer vertices.

			Triangle begins:
   1
   1  1
   3  1
   6  2  1
  15  7  5  2
  52 53 62 31  9  1  1
The antichains counted in row n = 4 are the following:
  0             {1234}         {12}{134}{234}     {123}{124}{134}{234}
  {1}           {12}{134}      {123}{124}{134}    {12}{13}{14}{23}{24}{34}
  {12}          {123}{124}     {12}{13}{24}{34}
  {123}         {12}{13}{14}   {12}{13}{14}{234}
  {1}{2}        {12}{13}{24}   {12}{13}{14}{23}{24}
  {1}{23}       {12}{13}{234}
  {12}{13}      {12}{13}{14}{23}
  {1}{234}
  {12}{34}
  {1}{2}{3}
  {1}{2}{34}
  {2}{13}{14}
  {12}{13}{23}
  {1}{2}{3}{4}
  {4}{12}{13}{23}

Row sums are A306505.
Column k = 0 is A327437.
The labeled version is A327352.
Cf. A014466, A052446, A327062, A327071, A327103, A327111, A327144, A327352, A327353.

A327110 BII-numbers of set-systems with spanning edge-connectivity 3.

Original entry on oeis.org

116, 117, 118, 119, 124, 125, 126, 127, 1796, 1797, 1798, 1799, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914, 1915, 1916, 1917, 1918, 1919, 1924, 1925, 1926, 1927, 2032, 2033, 2034, 2035, 2036, 2037, 2038, 2039, 2040, 2041, 2042, 2043, 2044

Offset: 1

Gus Wiseman, Oct 03 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.

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 set-system that is disconnected or covers fewer vertices.

			The sequence of all set-systems with spanning edge-connectivity 3 together with their BII-numbers begins:
   116: {{1,2},{1,3},{2,3},{1,2,3}}
   117: {{1},{1,2},{1,3},{2,3},{1,2,3}}
   118: {{2},{1,2},{1,3},{2,3},{1,2,3}}
   119: {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
   124: {{1,2},{3},{1,3},{2,3},{1,2,3}}
   125: {{1},{1,2},{3},{1,3},{2,3},{1,2,3}}
   126: {{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
   127: {{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
  1796: {{1,2},{1,4},{2,4},{1,2,4}}
  1797: {{1},{1,2},{1,4},{2,4},{1,2,4}}
  1798: {{2},{1,2},{1,4},{2,4},{1,2,4}}
  1799: {{1},{2},{1,2},{1,4},{2,4},{1,2,4}}
  1904: {{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1905: {{1},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1906: {{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1907: {{1},{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1908: {{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1909: {{1},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1910: {{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1911: {{1},{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}

Positions of 3's in A327144.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
BII-numbers for spanning edge-connectivity 1 are A327111.
Cf. A001187, A095983, A322395, A326749, A326753, A326787, A327069, A327071, A327103, A327130, A327146, A327147.

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

A327367 Number of labeled simple graphs with n vertices, at least one of which is isolated.

Original entry on oeis.org

0, 1, 1, 4, 23, 256, 5319, 209868, 15912975, 2343052576, 675360194287, 383292136232380, 430038382710483623, 956430459603341708896, 4224538833207707658410103, 37106500399796746894085512140, 648740170822904504303462104598943

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

The unlabeled version is A000088(n - 1).
Labeled graphs with no isolated vertices are A006129.
Covering graphs with at least one endpoint are A327227.
Cf. A006125, A006129, A054592, A245797, A327103, A327105.

b:= proc(n) option remember; `if`(n=0, 1,
      2^binomial(n, 2)-add(b(k)*binomial(n, k), k=0..n-1))
    end:
a:= n-> 2^(n*(n-1)/2)-b(n):
seq(a(n), n=0..17);  # Alois P. Heinz, Sep 04 2019

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#!=Range[n]&]],{n,0,5}]

b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2)); \\ A006129
a(n) = 2^(n*(n-1)/2) - b(n); \\ Michel Marcus, Sep 05 2019

a(n) = A006125(n) - A006129(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

A327106 BII-numbers of set-systems with maximum degree 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327438 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327110 BII-numbers of set-systems with spanning edge-connectivity 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327367 Number of labeled simple graphs with n vertices, at least one of which is isolated.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula