# How many chains are there in a finite power set?

Let $A$ be a finite set with $n$ elements. How many chains are there in $\mathcal P(A)$ -- that is, how many different subsets of $\mathcal P(A)$ are totally ordered by inclusion?

It's easy enough to count maximal chains; there are $n!$ of them. But counting all chains gets me into horrible inclusion-exclusion situations even if I try to do it by hand for small $n$.

Of course this is also the number of chains in a Boolean algebra with $2^n$ elements, or the number of chains in a finite lattice with $2^n$ elements.

By hand computation, the number of chains for $n$ running from $0$ to $6$ is $2, 4, 12, 52, 300, 2164, 18732$. This sequence appears to be unknown in OEIS.

• "It's easy enough to count maximal chains; there are n! of them." Could you explain that in more detail? – Da Mike Jun 20 at 22:06
• @DaMike: You get a maximal chain by choosing some order of the elements of $A$ and adding them to a set one at a time in that order. There are $n!$ orders, and each gives a different maximal chain. – Henning Makholm Jun 20 at 22:26
• Oh I get it now. Thank you! – Da Mike Jun 21 at 9:29

Except for the degenerate $n=0$ case, the number of chains is $4$ times the $n$th Fubini number, A000670, also known as ordered Bell numbers.

The linked Wikipedia articles lists various ways formulas for these numbers, the most elementary ones being $$a_n = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} \binom{k}{j}j^n \qquad\text{and}\qquad a_n \approx \frac{n!}{2(\log 2)^{n+1}}$$ (and then the number of chains is then $4 a_n$).

The factor of $4$ makes sense; it represents the fact that each of $\varnothing$ and $A$ can either be omitted or included in the chain without affecting its validity.