A330057 -id:A330057 - cp's OEIS frontend

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

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

A330053 Number of non-isomorphic set-systems of weight n with at least one singleton.

Original entry on oeis.org

0, 1, 1, 3, 6, 14, 32, 79, 193, 499, 1321, 3626, 10275, 30126, 91062, 284093, 912866, 3018825, 10261530, 35814255, 128197595, 470146011, 1764737593, 6773539331, 26561971320, 106330997834, 434195908353, 1807306022645, 7663255717310, 33079998762373

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty sets of positive integers. An singleton is an edge of size 1. The weight of a set-system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 14 multiset partitions:
  {1}  {1}{2}  {1}{12}    {1}{123}      {1}{1234}
               {1}{23}    {1}{234}      {1}{2345}
               {1}{2}{3}  {1}{2}{12}    {1}{12}{13}
                          {1}{2}{13}    {1}{12}{23}
                          {1}{2}{34}    {1}{12}{34}
                          {1}{2}{3}{4}  {1}{2}{123}
                                        {1}{2}{134}
                                        {1}{2}{345}
                                        {1}{23}{45}
                                        {2}{13}{14}
                                        {1}{2}{3}{12}
                                        {1}{2}{3}{14}
                                        {1}{2}{3}{45}
                                        {1}{2}{3}{4}{5}

Jean-François Alcover, Table of n, a(n) for n = 0..50 [using data from A283877 and A306005]

The complement is counted by A306005.
The multiset partition version is A330058.
Non-isomorphic set-systems with at least one endpoint are A330052.
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, A330055, A330056, A330057.

A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A283877 = A@283877;
A306005 = A@306005;
a[n_] := A283877[[n + 1]] - A306005[[n + 1]];
a /@ Range[0, 50] (* Jean-François Alcover, Feb 09 2020 *)

a(n) = A283877(n) - A306005(n). - Jean-François Alcover, Feb 09 2020

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

Original entry on oeis.org

1, 1, 2, 63, 29471, 2144945976, 9223371624669871587, 170141183460469227599616678821978424151, 57896044618658097711785492504343953752410420469299789800819363538011879603532

Offset: 0

Gus Wiseman, Dec 01 2019

nonn

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

			The a(2) = 2 set-systems are {} and {{1},{2},{1,2}}. The a(3) = 63 set-systems are:
  0                 {2}{3}{12}{13}       {1}{3}{12}{13}{23}
  {1}{2}{12}        {2}{12}{13}{23}      {2}{3}{12}{13}{23}
  {1}{3}{13}        {2}{3}{12}{123}      {1}{2}{12}{23}{123}
  {2}{3}{23}        {2}{3}{13}{123}      {1}{2}{13}{23}{123}
  {12}{13}{23}      {3}{12}{13}{23}      {1}{3}{12}{13}{123}
  {1}{23}{123}      {1}{13}{23}{123}     {1}{3}{12}{23}{123}
  {2}{13}{123}      {2}{12}{13}{123}     {1}{3}{13}{23}{123}
  {3}{12}{123}      {2}{12}{23}{123}     {2}{3}{12}{13}{123}
  {12}{13}{123}     {2}{13}{23}{123}     {2}{3}{12}{23}{123}
  {12}{23}{123}     {3}{12}{13}{123}     {2}{3}{13}{23}{123}
  {13}{23}{123}     {3}{12}{23}{123}     {1}{12}{13}{23}{123}
  {1}{2}{13}{23}    {3}{13}{23}{123}     {2}{12}{13}{23}{123}
  {1}{2}{3}{123}    {12}{13}{23}{123}    {3}{12}{13}{23}{123}
  {1}{3}{12}{23}    {1}{2}{3}{12}{13}    {1}{2}{3}{12}{13}{23}
  {1}{12}{13}{23}   {1}{2}{3}{12}{23}    {1}{2}{3}{12}{13}{123}
  {1}{2}{13}{123}   {1}{2}{3}{13}{23}    {1}{2}{3}{12}{23}{123}
  {1}{2}{23}{123}   {1}{2}{12}{13}{23}   {1}{2}{3}{13}{23}{123}
  {1}{3}{12}{123}   {1}{2}{3}{12}{123}   {1}{2}{12}{13}{23}{123}
  {1}{3}{23}{123}   {1}{2}{3}{13}{123}   {1}{3}{12}{13}{23}{123}
  {1}{12}{13}{123}  {1}{2}{3}{23}{123}   {2}{3}{12}{13}{23}{123}
  {1}{12}{23}{123}  {1}{2}{12}{13}{123}  {1}{2}{3}{12}{13}{23}{123}

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

The case with no singletons is A330056.
The unlabeled version is A330054 (by weight) or A330124 (by vertices).
Set-systems with no singletons are A016031.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Cf. A000612, A007716, A055621, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330057, A330058.

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

a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-1)*sum(j=0, k, stirling(k,j,2)*2^(j*(n-k)) ))} \\ Andrew Howroyd, Jan 16 2023

a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^k * binomial(n,k) * 2^(2^(n-k)-1) * Stirling2(k,j) * 2^(j*(n-k)). - Andrew Howroyd, Jan 16 2023

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

cp's OEIS Frontend

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

A330053 Number of non-isomorphic set-systems of weight n with at least one singleton.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions