cp's OEIS Frontend

A072447 Number of connectedness systems on n vertices that contain all singletons and the set of all the vertices.

%I A072447 #44 Oct 28 2023 11:12:14
%S A072447 1,1,8,378,252000,18687534984
%N A072447 Number of connectedness systems on n vertices that contain all singletons and the set of all the vertices.
%C A072447 Previous name was: a(1) = 1; for n > 1, a(n) = number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons.
%C A072447 A connectedness system is (as below) a set of (finite) nonempty sets that is closed under union of nondisjoint sets.
%C A072447 The old definition was: "Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; {1,2,...n} is an element of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S."
%C A072447 Comments on the old definition from _Gus Wiseman_, Aug 01 2019: (Start)
%C A072447  If this sequence were defined similarly to A326877, we would have a(1) = 0.
%C A072447 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. It is connected if it is empty or contains an edge with all the vertices. a(n) is the number of connected connectedness systems on n vertices without singletons. For example, the a(3) = 8 connected connectedness systems without singletons are:
%C A072447   {{1,2,3}}
%C A072447   {{1,2},{1,2,3}}
%C A072447   {{1,3},{1,2,3}}
%C A072447   {{2,3},{1,2,3}}
%C A072447   {{1,2},{1,3},{1,2,3}}
%C A072447   {{1,2},{2,3},{1,2,3}}
%C A072447   {{1,3},{2,3},{1,2,3}}
%C A072447   {{1,2},{1,3},{2,3},{1,2,3}}
%C A072447 (End)
%C A072447 Conjecture concerning the original definition: a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under intersection and contain no sets of cardinality n-1. - _Tian Vlasic_, Nov 04 2022. [This was false, as pointed out by _Christian Sievers_, Oct 20 2023. It is easy to see that for n>1, a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons; whereas by duality, the sequence suggested in the conjecture is also the number of those families that are also closed under arbitrary union. For details see the Sievers link. - _N. J. A. Sloane_, Oct 21 2023]
%H A072447 Christian Sievers, <a href="/A072447/a072447_1.txt">Comments on connectedness systems: the conjecture about A072447</a>
%H A072447 Wim van Dam, <a href="http://www.cs.berkeley.edu/~vandam/subpowersets/sequences.html">Sub Power Set Sequences</a>
%H A072447 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 A072447 a(n > 1) = A326868(n)/2^n. - _Gus Wiseman_, Aug 01 2019
%e A072447 a(3) = 8 because of the 8 sets: {{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}}.
%t A072447 Table[Length[Select[Subsets[Subsets[Range[n],{2,n}]],(n==0||MemberQ[#,Range[n]])&&SubsetQ[#,Union@@@Select[Tuples[#,2],Intersection@@#!={}&]]&]],{n,0,4}] (* returns a(1) = 0 similar to A326877. - _Gus Wiseman_, Aug 01 2019 *)
%Y A072447 The unlabeled case is A072445.
%Y A072447 The non-connected case is A072446.
%Y A072447 The case with singletons is A326868.
%Y A072447 The covering version is A326877.
%Y A072447 Cf. A072444, A326866, A326869, A326870, A326873, A326879.
%K A072447 nonn,more
%O A072447 1,3
%A A072447 Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002
%E A072447 Edited by _N. J. A. Sloane_, Oct 21 2023 (a(6) corrected by _Christian Sievers_, Oct 20 2023)
%E A072447 Edited by _Christian Sievers_, Oct 26 2023