A330052 -id:A330052 - cp's OEIS frontend

A330055 Number of non-isomorphic set-systems of weight n with no singletons or endpoints.

1, 0, 0, 0, 0, 0, 1, 1, 3, 5, 16, 24, 90, 179, 567, 1475, 4623, 13650, 44475, 144110, 492017, 1706956, 6124330, 22442687, 84406276, 324298231, 1273955153, 5106977701, 20885538133, 87046940269, 369534837538, 1596793560371, 7019424870960, 31374394197536, 142514998263015

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 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(7) = 1 through a(10) = 16 set-systems:
  {12}{13}{123}  {12}{134}{234}    {12}{134}{1234}    {12}{1345}{2345}
                 {12}{34}{1234}    {123}{124}{134}    {123}{124}{1234}
                 {12}{13}{24}{34}  {12}{13}{14}{234}  {123}{145}{2345}
                                   {12}{13}{23}{123}  {12}{345}{12345}
                                   {12}{13}{24}{134}  {12}{13}{124}{134}
                                                      {12}{13}{124}{234}
                                                      {12}{13}{14}{1234}
                                                      {12}{13}{24}{1234}
                                                      {12}{13}{245}{345}
                                                      {12}{13}{45}{2345}
                                                      {12}{34}{123}{124}
                                                      {12}{34}{125}{345}
                                                      {12}{34}{135}{245}
                                                      {13}{24}{123}{124}
                                                      {12}{13}{14}{23}{24}
                                                      {12}{13}{24}{35}{45}

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

The labeled version is A330056.
The "multi" version is A320665.
Non-isomorphic set-systems with no singletons are A306005.
Non-isomorphic set-systems with no endpoints are A330054.
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, A321405, A330052, A330058.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g-subst(g,x,x^2)}
S(q, t, k)={(x-x^2)*sum(j=1, #q, if(t%q[j]==0, q[j])) + O(x*x^k)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q, t, n\t)-S(q,t,n\t),x,x^t)/t )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024

a(11) onwards from Andrew Howroyd, Jan 27 2024

A330054 Number of non-isomorphic set-systems of weight n with no endpoints.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 4, 4, 16, 26, 87, 181, 570, 1453, 4464, 13038, 41548, 132217, 442603, 1506803, 5305174, 19092816, 70548770, 266495254, 1029835424, 4063610148, 16366919221, 67217627966, 281326631801, 1199048810660, 5201341196693, 22950740113039, 102957953031700

Offset: 0

Gus Wiseman, Nov 30 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 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(0) = 1 through a(8) = 16 multiset partitions (empty columns not shown):
  0  {1}{2}{12}  {12}{13}{23}    {13}{23}{123}      {12}{134}{234}
                 {1}{23}{123}    {1}{3}{23}{123}    {1}{234}{1234}
                 {1}{2}{13}{23}  {3}{12}{13}{23}    {12}{34}{1234}
                 {1}{2}{3}{123}  {1}{2}{3}{13}{23}  {1}{12}{34}{234}
                                                    {12}{13}{24}{34}
                                                    {1}{2}{134}{234}
                                                    {1}{2}{34}{1234}
                                                    {2}{13}{14}{234}
                                                    {2}{13}{23}{123}
                                                    {3}{13}{23}{123}
                                                    {1}{2}{13}{24}{34}
                                                    {1}{2}{3}{14}{234}
                                                    {1}{2}{3}{23}{123}
                                                    {1}{2}{3}{4}{1234}
                                                    {2}{3}{12}{13}{23}
                                                    {1}{2}{3}{4}{12}{34}

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

The complement is counted by A330052.
The multiset partition version is A302545.
Non-isomorphic set-systems with no singletons are A306005.
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A317533, A317794, A319559, A320665, A330055, A330056, A330058.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=1+x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g - subst(g,x,x^2)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q,t,n\t)/t,x,x^t) )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024

a(11) onwards from Andrew Howroyd, Jan 27 2024

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

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

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.

A330196 Number of unlabeled set-systems covering n vertices with no endpoints.

Original entry on oeis.org

1, 0, 1, 20, 1754

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) = 20 set-systems:
  {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}

First differences of the non-covering version A330124.
The "multi" version is A302545.
Unlabeled set-systems with no endpoints counted by vertices are A317794.
Unlabeled set-systems with no endpoints counted by weight are A330054.
Unlabeled set-systems counted by vertices are A000612.
Unlabeled set-systems counted by weight are A283877.
Cf. A007716, A016031, A306005, A317795, A320665, A330052, A330053, A330055.

cp's OEIS Frontend

A330055 Number of non-isomorphic set-systems of weight n with no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A330054 Number of non-isomorphic set-systems of weight n with no endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica