|
|
A306445
|
|
Number of collections of subsets of {1, 2, ..., n} that are closed under union and intersection.
|
|
31
|
|
|
2, 4, 13, 74, 732, 12085, 319988, 13170652, 822378267, 76359798228, 10367879036456, 2029160621690295, 565446501943834078, 221972785233309046708, 121632215040070175606989, 92294021880898055590522262, 96307116899378725213365550192, 137362837456925278519331211455157, 266379254536998812281897840071155592
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
REFERENCES
|
R. Stanley, Enumerative Combinatorics, volume 1, second edition, Exercise 3.46.
|
|
LINKS
|
|
|
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.
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}];
|
|
PROG
|
(Python)
import math
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|