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

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

Offset

0,3

Comments

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

Links

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

Formula

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

Example

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}

Mathematica

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

Prog

(PARI) 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

Crossrefs

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.

Sequence in context: A024238 A234279 A109667 * A004853 A249073 A064010

Adjacent sequences: A330056 A330057 A330058 * A330060 A330061 A330062

Keyword

nonn

Author

Gus Wiseman, Dec 01 2019

Extensions

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

Status

approved