A326866 Number of connectedness systems on n vertices.

1, 2, 8, 96, 6720, 8130432, 1196099819520

Offset

0,2

Comments

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of two overlapping edges.

Links

Table of n, a(n) for n=0..6.

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Formula

a(n) = 2^n * A072446(n).

Example

The a(0) = 1 through a(2) = 8 connectedness systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 3}]

Crossrefs

The case without singletons is A072446.

The unlabeled case is A326867.

The connected case is A326868.

Binomial transform of A326870 (the covering case).

The BII-numbers of these set-systems are A326872.

Cf. A072444, A072447, A102896, A306445.

Sequence in context: A001417 A156926 A361388 * A001697 A006069 A270485

Adjacent sequences: A326863 A326864 A326865 * A326867 A326868 A326869

Keyword

nonn,more

Author

Gus Wiseman, Jul 29 2019

Extensions

a(6) corrected by Christian Sievers, Oct 26 2023

Status

approved