A072446 Number of connectedness systems on n vertices that contain all singletons.

1, 2, 12, 420, 254076, 18689059680

Offset

1,2

Comments

From Gus Wiseman, Jul 31 2019: (Start)

If we define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges, then a(n) is the number of connectedness systems on n vertices without singleton edges. The BII-numbers of these set-systems are given by A326873. The a(3) = 12 connectedness systems without singletons are:

{}

{{1,2}}

{{1,3}}

{{2,3}}

{{1,2,3}}

{{1,2},{1,2,3}}

{{1,3},{1,2,3}}

{{2,3},{1,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}}

(End)

Links

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

Wim van Dam, Sub Power Set Sequences

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

Formula

a(n) = A326866(n)/2^n. - Gus Wiseman, Jul 31 2019

Example

a(3)=12 because of the 12 sets:
{{1}, {2}, {3}};
{{1}, {2}, {3}, {1, 2}};
{{1}, {2}, {3}, {1, 3}};
{{1}, {2}, {3}, {2, 3}};
{{1}, {2}, {3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n], {2, n}]], SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 3}] (* Gus Wiseman, Jul 31 2019 *)

Crossrefs

The unlabeled case is A072444.

Exponential transform of A072447 (the connected case).

The case with singletons is A326866.

Binomial transform of A326877 (the covering case).

Cf. A102896, A306445, A326872, A326873.

Sequence in context: A051009 A324616 A060942 * A220113 A015181 A012378

Adjacent sequences: A072443 A072444 A072445 * A072447 A072448 A072449

Keyword

nonn

Author

Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002

Extensions

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

Status

approved