(Translated by https://www.hiragana.jp/)
# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a306445
Showing 1-1 of 1
%I A306445 #30 Jan 20 2024 11:28:17
%S A306445 2,4,13,74,732,12085,319988,13170652,822378267,76359798228,
%T A306445 10367879036456,2029160621690295,565446501943834078,
%U A306445 221972785233309046708,121632215040070175606989,92294021880898055590522262,96307116899378725213365550192,137362837456925278519331211455157,266379254536998812281897840071155592
%N A306445 Number of collections of subsets of {1, 2, ..., n} that are closed under union and intersection.
%D A306445 R. Stanley, Enumerative Combinatorics, volume 1, second edition, Exercise 3.46.
%F A306445 a(n) = 1 + Sum_{d=0..n} Sum_{i=d..n} C(n,i)*C(i,i-d)*A000798(d). (Follows by caseworking on the maximal and minimal set in the collection.)
%F A306445 E.g.f.: exp(x) + exp(x)^2*B(exp(x)-1) where B(x) is the e.g.f. for A001035 (after Stanley reference above). - _Geoffrey Critzer_, Jan 19 2024
%e A306445 For n = 0, the empty collection and the collection containing the empty set only are both valid.
%e A306445 For n = 1, the 2^(2^1)=4 possible collections are also all closed under union and intersection.
%e A306445 For n = 2, there are only 3 invalid collections, namely the collections containing both {1} and {2} but not both {1,2} and the empty set. Hence there are 2^(2^2)-3 = 13 valid collections.
%e A306445 From _Gus Wiseman_, Jul 31 2019: (Start)
%e A306445 The a(0) = 2 through a(4) = 13 sets of sets:
%e A306445 {} {} {}
%e A306445 {{}} {{}} {{}}
%e A306445 {{1}} {{1}}
%e A306445 {{},{1}} {{2}}
%e A306445 {{1,2}}
%e A306445 {{},{1}}
%e A306445 {{},{2}}
%e A306445 {{},{1,2}}
%e A306445 {{1},{1,2}}
%e A306445 {{2},{1,2}}
%e A306445 {{},{1},{1,2}}
%e A306445 {{},{2},{1,2}}
%e A306445 {{},{1},{2},{1,2}}
%e A306445 (End)
%t A306445 Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union[Union@@@Tuples[#,2],Intersection@@@Tuples[#,2]]]&]],{n,0,3}] (* _Gus Wiseman_, Jul 31 2019 *)
%t A306445 A000798 = Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {_, _}][[All, 2]];
%t A306445 a[n_] := 1 + Sum[Binomial[n, i]*Binomial[i, i - d]*A000798[[d + 1]], {d, 0, n}, {i, d, n}];
%t A306445 a /@ Range[0, Length[A000798] - 1] (* _Jean-François Alcover_, Dec 30 2019 *)
%o A306445 (Python)
%o A306445 import math
%o A306445 # Sequence A000798
%o A306445 topo = [1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203]
%o A306445 def nCr(n, r):
%o A306445 return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))
%o A306445 for n in range(len(topo)):
%o A306445 ans = 1
%o A306445 for d in range(n+1):
%o A306445 for i in range(d, n+1):
%o A306445 ans += nCr(n,i) * nCr(i, i-d) * topo[d]
%o A306445 print(n, ans)
%Y A306445 The covering case with {} is A000798.
%Y A306445 The case closed under union only is A102897.
%Y A306445 The case closed under intersection only is (also) A102897.
%Y A306445 The BII-numbers of these set-systems are A326876.
%Y A306445 Cf. A001930, A102895, A102896, A326866, A326878, A326882.
%K A306445 nonn
%O A306445 0,1
%A A306445 _Yuan Yao_, Feb 15 2019
%E A306445 a(16)-a(18) from A000798 by _Jean-François Alcover_, Dec 30 2019
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE