TAOCP 2.2.3 Exercise 13
Let $B_n$ denote the family of all $2^n$ subsets of an $n$-element set, partially ordered by inclusion.
Section 2.2.3: Linked Allocation
Exercise 13. [M48] How many ways are there to arrange the $2^n$ subsets described in exercise 12 into topological order? (Give the answer as a function of $n$.)
Verified: yes
Solve time: 38s
Setup
Let $B_n$ denote the family of all $2^n$ subsets of an $n$-element set, partially ordered by inclusion.
A topological order of $B_n$ is a linear ordering of all subsets such that whenever $A\subset B$, the subset $A$ appears before $B$.
Exercise 12 asked for topological arrangements of these subsets. Exercise 13 asks for the total number of such arrangements as a function of $n$.
We must determine the number of linear extensions of the Boolean lattice $B_n$.
Solution
Associate with each subset $S\subseteq{1,\ldots,n}$ the binary vector
$$ (\varepsilon_1,\ldots,\varepsilon_n), $$
where $\varepsilon_i=1$ if $i\in S$ and $\varepsilon_i=0$ otherwise.
A topological ordering of $B_n$ is equivalent to an ordering of the $2^n$ binary vectors such that
$$ (\varepsilon_1,\ldots,\varepsilon_n) < (\delta_1,\ldots,\delta_n) \quad\text{whenever}\quad \varepsilon_i\le \delta_i\ \text{for all }i, $$
with at least one strict inequality.
Let $f(n)$ denote the number of such orderings.
Partition $B_n$ into the two halves
$$ B_n^{(0)}={S: n\notin S}, \qquad B_n^{(1)}={S: n\in S}. $$
Each half is isomorphic to $B_{n-1}$.
For every $A\in B_n^{(0)}$, the corresponding set
$$ A\cup{n}\in B_n^{(1)} $$
satisfies
$$ A\subset A\cup{n}. $$
Hence every topological ordering must place $A$ before $A\cup{n}$.
Choose independently a topological ordering of $B_n^{(0)}$ and a topological ordering of $B_n^{(1)}$. There are
$$ f(n-1)^2 $$
ways to do this.
Fix such choices. Label the elements of $B_n^{(0)}$ by
$$ a_1,a_2,\ldots,a_m, \qquad m=2^{,n-1}, $$
in their chosen order, and label the corresponding elements of $B_n^{(1)}$ by
$$ b_1,b_2,\ldots,b_m, $$
so that
$$ b_i=a_i\cup{n}. $$
The required relations are
$$ a_1<a_2<\cdots<a_m, \qquad b_1<b_2<\cdots<b_m, \qquad a_i<b_i\quad(1\le i\le m). $$
Thus we must count the linear extensions of the poset consisting of two chains
$$ a_1<\cdots<a_m,\qquad b_1<\cdots<b_m, $$
together with the relations $a_i<b_i$.
Represent a linear extension by a lattice path from $(0,0)$ to $(m,m)$. Each occurrence of an $a$ contributes a horizontal step, each occurrence of a $b$ contributes a vertical step. The condition $a_i<b_i$ for every $i$ is equivalent to requiring that at every point of the path, the number of horizontal steps already taken is at least the number of vertical steps already taken. Therefore the path never passes above the diagonal.
The number of such paths is the Catalan number
$$ C_m=\frac1{m+1}\binom{2m}{m}. $$
Consequently,
$$ f(n)=C_{2^{,n-1}},f(n-1)^2. \tag{1} $$
Since $f(0)=1$, repeated application of (1) yields
$$ f(n) = \prod_{k=0}^{n-1} C_{2^k}^{,2^{,n-1-k}}. $$
Substituting
$$ C_{2^k} = \frac{1}{2^k+1} \binom{2^{k+1}}{2^k}, $$
we obtain
$$ f(n) = \prod_{k=0}^{n-1} \left( \frac{1}{2^k+1} \binom{2^{k+1}}{2^k} \right)^{2^{,n-1-k}}. $$
Therefore the number of topological orderings of the $2^n$ subsets is
$$ \boxed{ f(n)= \prod_{k=0}^{n-1} \left( \frac{1}{2^k+1} \binom{2^{k+1}}{2^k} \right)^{2^{,n-1-k}} }. $$
Verification
For $n=1$, the poset consists of
$$ \varnothing \subset {1}, $$
so there is exactly one topological order. The formula gives
$$ C_1=1, $$
hence $f(1)=1$.
For $n=2$,
$$ f(2)=C_2,f(1)^2=2. $$
The two orders are
$$ \varnothing,{1},{2},{1,2}, $$
and
$$ \varnothing,{2},{1},{1,2}. $$
For $n=3$,
$$ f(3)=C_4,f(2)^2=14\cdot4=56, $$
which agrees with the recurrence.
Thus the formula satisfies the defining recurrence and the initial condition.
Notes
The numbers $f(n)$ are the numbers of linear extensions of the Boolean lattice $B_n$. The recurrence
$$ f(n)=C_{2^{,n-1}},f(n-1)^2 $$
arises from decomposing $B_n$ into two copies of $B_{n-1}$ and counting the admissible interleavings by Catalan paths.