login
Number of connectedness systems on n vertices.
26

%I #12 Oct 27 2023 23:39:41

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

%N Number of connectedness systems on n vertices.

%C 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.

%H Gus Wiseman, <a href="http://www.mathematica-journal.com/2017/12/every-clutter-is-a-tree-of-blobs/">Every Clutter Is a Tree of Blobs</a>, The Mathematica Journal, Vol. 19, 2017.

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

%e The a(0) = 1 through a(2) = 8 connectedness systems:

%e {} {} {}

%e {{1}} {{1}}

%e {{2}}

%e {{1,2}}

%e {{1},{2}}

%e {{1},{1,2}}

%e {{2},{1,2}}

%e {{1},{2},{1,2}}

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

%Y The case without singletons is A072446.

%Y The unlabeled case is A326867.

%Y The connected case is A326868.

%Y Binomial transform of A326870 (the covering case).

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

%Y Cf. A072444, A072447, A102896, A306445.

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Jul 29 2019

%E a(6) corrected by _Christian Sievers_, Oct 26 2023