A326868 Number of connected connectedness systems on n vertices.

1, 1, 4, 64, 6048, 8064000, 1196002238976

Offset: 0

Author

Gus Wiseman, Jul 29 2019

Keywords

• nonn
• more

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 any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices.

Examples

			The a(3) = 64 connected connectedness systems:
  {{123}}              {{1}{123}}
  {{12}{123}}          {{2}{123}}
  {{13}{123}}          {{3}{123}}
  {{23}{123}}          {{1}{12}{123}}
  {{12}{13}{123}}      {{1}{13}{123}}
  {{12}{23}{123}}      {{1}{23}{123}}
  {{13}{23}{123}}      {{2}{12}{123}}
  {{12}{13}{23}{123}}  {{2}{13}{123}}
                       {{2}{23}{123}}
                       {{3}{12}{123}}
                       {{3}{13}{123}}
                       {{3}{23}{123}}
                       {{1}{12}{13}{123}}
                       {{1}{12}{23}{123}}
                       {{1}{13}{23}{123}}
                       {{2}{12}{13}{123}}
                       {{2}{12}{23}{123}}
                       {{2}{13}{23}{123}}
                       {{3}{12}{13}{123}}
                       {{3}{12}{23}{123}}
                       {{3}{13}{23}{123}}
                       {{1}{12}{13}{23}{123}}
                       {{2}{12}{13}{23}{123}}
                       {{3}{12}{13}{23}{123}}
.
  {{1}{2}{123}}              {{1}{2}{3}{123}}
  {{1}{3}{123}}              {{1}{2}{3}{12}{123}}
  {{2}{3}{123}}              {{1}{2}{3}{13}{123}}
  {{1}{2}{12}{123}}          {{1}{2}{3}{23}{123}}
  {{1}{2}{13}{123}}          {{1}{2}{3}{12}{13}{123}}
  {{1}{2}{23}{123}}          {{1}{2}{3}{12}{23}{123}}
  {{1}{3}{12}{123}}          {{1}{2}{3}{13}{23}{123}}
  {{1}{3}{13}{123}}          {{1}{2}{3}{12}{13}{23}{123}}
  {{1}{3}{23}{123}}
  {{2}{3}{12}{123}}
  {{2}{3}{13}{123}}
  {{2}{3}{23}{123}}
  {{1}{2}{12}{13}{123}}
  {{1}{2}{12}{23}{123}}
  {{1}{2}{13}{23}{123}}
  {{1}{3}{12}{13}{123}}
  {{1}{3}{12}{23}{123}}
  {{1}{3}{13}{23}{123}}
  {{2}{3}{12}{13}{123}}
  {{2}{3}{12}{23}{123}}
  {{2}{3}{13}{23}{123}}
  {{1}{2}{12}{13}{23}{123}}
  {{1}{3}{12}{13}{23}{123}}
  {{2}{3}{12}{13}{23}{123}}
		

Links

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

Crossrefs

The case without singletons is A072447.

The not necessarily connected case is A326866.

The unlabeled case is A326869.

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

Cf. A072445, A072446, A102896, A306445, A323818, A326867, A326870, A326872.

Programs

Mathematica

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

Formula

a(n > 1) = 2^n * A072447(n).

Logarithmic transform of A326870.

Extensions

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