8
$\begingroup$

How many sublattices does the powerset lattice $2^n$ contain for $n$ finite? (up to equality, not isomorphism)

I thought for sure this would be easy to find on OEIS, but so far I am coming up empty.

I really am interested in seeing a list of small examples, say up to $n=5$ or $6$ maybe, although perhaps already things blow up too much at that point for this to be feasible. Ideally there would be a systematic way to write down examples, but just as an entryway to the literature, I thought I'd ask this as a counting question.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The number of Boolean subalgebras of the Boolean algebra would be easier to compute, I guess. $\endgroup$
    – markvs
    Commented Oct 8, 2021 at 3:33
  • 3
    $\begingroup$ If $L$ is a sublattice of $P(X)$, then $L$ has a least element $A_{L}$ and greatest element $B_{L}$, and $\mathcal{T}_{L}=\{R\setminus A_{L}\mid R\in L\}$ is a topology on $B_{L}\setminus A_{L}$. Furthermore, every triple $(A,B,\mathcal{T})$ where $A\subseteq B$ and $\mathcal{T}$ is a topology on $B\setminus A$ can be formed this way. Since the specialization ordering gives a correspondence between the topologies and the finite pre-orders, we can count the number of sublattices of $P(X)$ when $X$ is finite in terms of the number of pre-orders. $\endgroup$
    – Joseph Van Name
    Commented Oct 8, 2021 at 4:05
  • $\begingroup$ @JosephVanName Thanks! As explained in my comment on Keith Kearnes' answer below, I think it's actually the finite topologies themselves that I'm interested -- thanks for explaining the connection! And the fact that one can then reduce further to thinking about the specialization order is exactly the sort of insight I was hoping for! $\endgroup$
    – Tim Campion
    Commented Oct 8, 2021 at 12:58
  • 5
    $\begingroup$ A reference is Enumerative Combinatorics, vol. 1, second ed., Exercise 3.46. $\endgroup$
    – Richard Stanley
    Commented Oct 8, 2021 at 13:34

1 Answer 1

Reset to default
15
$\begingroup$

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

Number of collections of subsets of $\{1, 2,\ldots,n\}$ that are closed under union and intersection (starting at $n=0$).

This count includes the empty sublattice, so if you don't want that you should subtract one from every term.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Great, thanks! I neglected to clarify that for me, "sublattice" includes the condition that the bottom and top elements agree with those in the ambient lattice. So what I failed to notice is that I was asking about precisely the number of topologies on a finite set, as mentioned by Joseph van Name and linked to from the OEIS page you found. (BTW this OEIS link doesn't really have any references, but it does link to the OEIS page for finite topologies, which does have ample references it seems.) $\endgroup$
    – Tim Campion
    Commented Oct 8, 2021 at 12:58
  • $\begingroup$ @markvs The formula writes these numbers in terms of the number of finite topologies, but the number of finite topologies does not itself have a formula so far as I understand. So it's more a relationship between two series than a "closed form" formula per se. $\endgroup$
    – Tim Campion
    Commented Oct 8, 2021 at 13:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .