A306445 Number of collections of subsets of {1, 2, ..., n} that are closed under union and intersection.

2, 4, 13, 74, 732, 12085, 319988, 13170652, 822378267, 76359798228, 10367879036456, 2029160621690295, 565446501943834078, 221972785233309046708, 121632215040070175606989, 92294021880898055590522262, 96307116899378725213365550192, 137362837456925278519331211455157, 266379254536998812281897840071155592

Offset

0,1

References

R. Stanley, Enumerative Combinatorics, volume 1, second edition, Exercise 3.46.

Links

Table of n, a(n) for n=0..18.

Formula

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

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

Example

For n = 0, the empty collection and the collection containing the empty set only are both valid.
For n = 1, the 2^(2^1)=4 possible collections are also all closed under union and intersection.
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.
From Gus Wiseman, Jul 31 2019: (Start)
The a(0) = 2 through a(4) = 13 sets of sets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{2}}
                  {{1,2}}
                  {{},{1}}
                  {{},{2}}
                  {{},{1,2}}
                  {{1},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n]]], SubsetQ[#, Union[Union@@@Tuples[#, 2], Intersection@@@Tuples[#, 2]]]&]], {n, 0, 3}] (* Gus Wiseman, Jul 31 2019 *)
A000798 = Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {_, _}][[All, 2]];
a[n_] := 1 + Sum[Binomial[n, i]*Binomial[i, i - d]*A000798[[d + 1]], {d, 0, n}, {i, d, n}];
a /@ Range[0, Length[A000798] - 1] (* Jean-François Alcover, Dec 30 2019 *)

Prog

(Python)
import math
# Sequence A000798
topo = [1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203]
def nCr(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))
for n in range(len(topo)):
    ans = 1
    for d in range(n+1):
        for i in range(d, n+1):
            ans += nCr(n, i) * nCr(i, i-d) * topo[d]
    print(n, ans)

Crossrefs

The covering case with {} is A000798.

The case closed under union only is A102897.

The case closed under intersection only is (also) A102897.

The BII-numbers of these set-systems are A326876.

Cf. A001930, A102895, A102896, A326866, A326878, A326882.

Sequence in context: A132786 A298065 A298714 * A216670 A103845 A055463

Adjacent sequences: A306442 A306443 A306444 * A306446 A306447 A306448

Keyword

nonn

Author

Yuan Yao, Feb 15 2019

Extensions

a(16)-a(18) from A000798 by Jean-François Alcover, Dec 30 2019

Status

approved