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

1, 1, 2, 12, 420, 254076, 18689059680

Offset: 0

Author

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

Keywords

• nonn

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)

Examples

			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}}.
		

Links

• Wim van Dam, Sub Power Set Sequences
• Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

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.

Programs

Mathematica

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

Formula

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

Extensions

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

a(0)=1 prepended by Sean A. Irvine, Oct 02 2024