A072446 - OEIS

%I #17 Oct 02 2024 21:56:36

%S 1,1,2,12,420,254076,18689059680

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

%C From _Gus Wiseman_, Jul 31 2019: (Start)

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

%C   {}

%C   {{1,2}}

%C   {{1,3}}

%C   {{2,3}}

%C   {{1,2,3}}

%C   {{1,2},{1,2,3}}

%C   {{1,3},{1,2,3}}

%C   {{2,3},{1,2,3}}

%C   {{1,2},{1,3},{1,2,3}}

%C   {{1,2},{2,3},{1,2,3}}

%C   {{1,3},{2,3},{1,2,3}}

%C   {{1,2},{1,3},{2,3},{1,2,3}}

%C (End)

%H Wim van Dam, <a href="http://www.cs.berkeley.edu/~vandam/subpowersets/sequences.html">Sub Power Set Sequences</a>

%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) = A326866(n)/2^n. - _Gus Wiseman_, Jul 31 2019

%e a(3)=12 because of the 12 sets:

%e {{1}, {2}, {3}};

%e {{1}, {2}, {3}, {1, 2}};

%e {{1}, {2}, {3}, {1, 3}};

%e {{1}, {2}, {3}, {2, 3}};

%e {{1}, {2}, {3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 2}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {2, 3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}};

%e {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

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

%Y The unlabeled case is A072444.

%Y Exponential transform of A072447 (the connected case).

%Y The case with singletons is A326866.

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

%Y Cf. A102896, A306445, A326872, A326873.

%K nonn

%O 0,3

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

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

%E a(0)=1 prepended by _Sean A. Irvine_, Oct 02 2024