A330059 -id:A330059 - cp's OEIS frontend

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

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

A330058 Number of non-isomorphic multiset partitions of weight n with at least one endpoint.

Original entry on oeis.org

0, 1, 2, 7, 21, 68, 214, 706, 2335, 7968, 27661, 98366, 357212, 1326169, 5027377, 19459252, 76850284, 309531069, 1270740646, 5314727630, 22633477157, 98096319485, 432490992805, 1938762984374, 8832924638252, 40882143931620, 192148753444380, 916747097916418

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
An endpoint is a vertex appearing only once (degree 1).
Also the number of non-isomorphic multiset partitions of weight n with at least one singleton.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions:
  {1}  {12}    {122}      {1222}
       {1}{2}  {123}      {1233}
               {1}{22}    {1234}
               {1}{23}    {1}{222}
               {2}{12}    {12}{22}
               {1}{2}{2}  {1}{233}
               {1}{2}{3}  {12}{33}
                          {1}{234}
                          {12}{34}
                          {13}{23}
                          {2}{122}
                          {3}{123}
                          {1}{1}{23}
                          {1}{2}{22}
                          {1}{2}{33}
                          {1}{2}{34}
                          {1}{3}{23}
                          {2}{2}{12}
                          {1}{2}{2}{2}
                          {1}{2}{3}{3}
                          {1}{2}{3}{4}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Wikipedia, Degree (graph theory)

The case of set-systems is A330053 (singletons) or A330052 (endpoints).
The complement is counted by A302545.
Cf. A007716, A283877, A306005, A330054, A330055, A330059.

a(n) = A007716(n) - A302545(n). - Andrew Howroyd, Jan 15 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 15 2023

A330056 Number of set-systems with n vertices and no singletons or endpoints.

Original entry on oeis.org

1, 1, 1, 6, 1724, 66963208, 144115175600855641, 1329227995784915809349010517957163445, 226156424291633194186662080095093568675422295082604716043360995547325655259

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. An endpoint is a vertex appearing only once (degree 1).

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

Andrew Howroyd, Table of n, a(n) for n = 0..11
Wikipedia, Degree (graph theory)

The version for non-isomorphic set-systems is A330055 (by weight).
The covering case is A330057.
Set-systems with no singletons are A016031.
Set-systems with no endpoints are A330059.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Non-isomorphic set-systems with no endpoints are A330054, (by weight).
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A008299, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330058.

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

\\ Here AS2(n,k) is A008299 (associated Stirling of 2nd kind)
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-(n-k)-1) * sum(j=0, k\2, sum(i=0, k-2*j, binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) )))} \\ Andrew Howroyd, Jan 16 2023

Binomial transform of A330057.

a(n) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} Sum_{i=0..k-2*j} (-1)^k * binomial(n,k) * 2^(2^(n-k)-(n-k)-1) * binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) where AS2(n,k) are the associated Stirling numbers of the 2nd kind (A008299). - Andrew Howroyd, Jan 16 2023

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

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Original entry on oeis.org

1, 0, 0, 5, 1703, 66954642, 144115175199102143, 1329227995784915808340204290157341181, 226156424291633194186662080095093568664788471116325389572604136316742486364

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. An endpoint is a vertex appearing only once (degree 1).

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

Andrew Howroyd, Table of n, a(n) for n = 0..11
Wikipedia, Degree (graph theory)

The version for non-isomorphic set-systems is A330055 (by weight).
The non-covering version is A330056.
Set-systems with no singletons are A016031.
Set-systems with no endpoints are A330059.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Non-isomorphic set-systems with no endpoints are A330054 (by weight).
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330058.

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

\\ here b(n) is A330056(n).
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
b(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-(n-k)-1) * sum(j=0, k\2, sum(i=0, k-2*j, binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) )))}
a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*b(n-k))} \\ Andrew Howroyd, Jan 16 2023

Binomial transform is A330056.

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

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

Original entry on oeis.org

1, 1, 2, 22, 1776

Offset: 0

Gus Wiseman, Dec 05 2019

A set-system is a finite set of finite nonempty sets. An endpoint is a vertex appearing only once (degree 1).

			Non-isomorphic representatives of the a(3) = 22 set-systems:
  0
  {1}{2}{12}
  {12}{13}{23}
  {1}{23}{123}
  {12}{13}{123}
  {1}{2}{13}{23}
  {1}{2}{3}{123}
  {1}{12}{13}{23}
  {1}{2}{13}{123}
  {1}{12}{13}{123}
  {1}{12}{23}{123}
  {12}{13}{23}{123}
  {1}{2}{3}{12}{13}
  {1}{2}{12}{13}{23}
  {1}{2}{3}{12}{123}
  {1}{2}{12}{13}{123}
  {1}{2}{13}{23}{123}
  {1}{12}{13}{23}{123}
  {1}{2}{3}{12}{13}{23}
  {1}{2}{3}{12}{13}{123}
  {1}{2}{12}{13}{23}{123}
  {1}{2}{3}{12}{13}{23}{123}

Partial sums of the covering case A330196.
The labeled version is A330059.
The "multi" version is A302545.
Unlabeled set-systems with no endpoints counted by weight are A330054.
Unlabeled set-systems with no singletons are A317794.
Unlabeled set-systems counted by vertices are A000612.
Unlabeled set-systems counted by weight are A283877.
The case with no singletons is A320665.
Cf. A007716, A016031, A306005, A317795, A321405, A330052, A330055.

cp's OEIS Frontend

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

A330058 Number of non-isomorphic multiset partitions of weight n with at least one endpoint.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A330056 Number of set-systems with n vertices and no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

Views

Author

Keywords

Comments

Examples

Crossrefs