Generating Function for sublattices of $B_n$ that contain $\emptyset$ and $[n]$

Question

This is Chapter $3$, Problem $46$(b) from Stanley's Enumerative Combinatorics.

Let $f(n)$ be the number of sublattices of rank $n$ of the Boolean algebra $B_n$... Let $g(n)$ be the number of sublattices of $B_n$ that contain $\emptyset$ and $[n]$. Write \begin{align} F(x) &= \sum_{n \ge 0} f(n)\frac{x^n}{n!}\\ G(x) &= \sum_{n \ge 0} g(n) \frac{x^n}{n!}. \end{align} Show that $G(x)=F(e^x-1)$.

By the Compositional Formula, $F(e^x-1)$ counts the number of ways to take an unordered partition of $[n]$, then put a "$e^x-1$"-structure on each block, and then put a $F(x)$ structure (sublattice with rank $n$) on the set of blocks.

The exponential generating function $e^x-1$ has coefficients $1$ everywhere except for $[x^0]$. Hence it just eliminates situations where some blocks of our unordered partition were empty.

So we can interpret $[x^n]F(e^x-1)$ as counting the number of ways to take an unordered partition of $[n]$ into $k$ nonempty blocks, and then (corresponding the $k$ blocks with [k] as needed) find a rank-$k$ sublattice of $B_k$.

I searched this site for a similar question, and found Trevor Gunn's answer here. I can understand how Trevor Gunn takes some lattice $L\subseteq B_n$ and then determines the associated $k$. However, after trying some examples, I'm still struggling to see the correspondence that his construction creates between the set of sublattices of $B_n$ containing $\emptyset$ and $[n]$, and selections of a partition $S_1, ..., S_k$ of $[n]$ combined with a rank $k$ graded sublattice of $B_k$.

I was wondering if someone could help clarify this correspondence, or point me in the direction of a different proof?

Answer 1

Given a lattice $L\subseteq B_n$, define an equivalence relation $\sim$ on $[n]$ by $x\sim y$ iff for all $a\in L$, $x\in a$ iff $y\in a$. Say that $\sim$ has $k$ equivalence classes. We can then naturally identify $L$ with a lattice $L'\subseteq B_k$ if we identify $[k]$ with $[n]/{\sim}$ (replace each element of $L$ with the set of equivalence classes that it contains). I claim that if $L$ contains $\emptyset$ and $[n]$, then $L'$ has rank $k$.

Indeed, suppose $\emptyset=a_0\subseteq a_1\subseteq \dots\subseteq a_m=[k]$ is a maximal chain in $L'$ but $m<k$. Then for some $i$, $a_{i+1}\setminus a_i$ contains two distinct elements $x$ and $y$. Now there exists some element $b\in L'$ which contains exactly one of $x$ or $y$ (otherwise $\sim$ would have identified $x$ and $y$); say $x\in b$ and $y\not\in b$. Observe now that $a_i\cup (b\cap a_{i+1})\in L'$ contains $x$ but not $y$ and so is strictly between $a_i$ and $a_{i+1}$. This contradicts the assumption that our chain was maximal.

Conversely, if we start with a lattice $L'\subseteq B_k$ and an identification of $[k]$ with a partition of $[n]$, we obtain a lattice $L$ on $[n]$ by just replacing each element of $L'$ with the union of the corresponding subsets of $[n]$. If $L'$ had rank $k$, then $L$ must contain $\emptyset$ and $[n]$ and the equivalence relation $\sim$ induced by $L$ as above is exactly the equivalence relation of the partition of $[n]$ we used (since $L'$ distinguishes all elements of $[k]$). It is then easy to see that this construction is inverse to the one described in the first paragraph.

Answer 2

First, we can associate a sublattice of rank $k$ of $B_n$ that contains $\emptyset$ and $[n]$ with a sublattice of rank $k$ of $B_k$ and an unordered partition of $[n]$ by fixing an arbitrary order (say, order the partitions by the least elements of their subsets) and replacing the $j$-th atom of $B_k$ by the atoms in the $j$-th element of the partition. For instance, with the sublattice $\{\emptyset,\{1\},\{1,2\}\}$ of $B_2$ and the unordered partition $\{\{1\},\{2,3\}\}$ this associates the sublattice $\{\emptyset,\{1\},\{1,2,3\}\}$ of rank $2$ of $B_3$ that contains $\emptyset$ and $[3]=\{1,2,3\}$. This map is injective.

Now we have to show that it is also surjective. This follows if we can show that every sublattice of rank $k$ of $B_n$ distinguishes exactly $k$ different subsets of $[n]$, that is, there are $k$ subsets of $[n]$ from which all elements of the sublattice can be formed by unions. Assume for the sake of contradiction that this is not the case. Then we can find a maximal chain of length $k$ (which necessarily distinguishes exactly $k$ different subsets) and a further element $z$ that distinguishes two atoms $a$ and $b$ (i.e. contains $a$ but not $b$) that the chain does not distinguish. Let $x$ be the greatest element of the chain that doesn't contain $a$ and $b$ and $y$ the least element of the chain that contains $a$ and $b$. Then $(y\land z)\lor x$ contains $a$ but not $b$, so $x\lt(y\land z)\lor x\lt y$, which contradicts the maximality of the chain.

It follows that the map is bijective, and hence each sublattice of rank $k$ of $B_n$ that contains $\emptyset$ and $[n]$ corresponds to exactly one pair of a sublattice of rank $k$ of $B_k$ and an unordered partition of $[n]$ (via the fixed arbitrary ordering of the partitions).