5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "It's easy enough to count maximal chains; there are n! of them." Could you explain that in more detail? $\endgroup$ – Da Mike Jun 20 at 22:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Henning Makholm Jun 20 at 22:26
  • $\begingroup$ Oh I get it now. Thank you! $\endgroup$ – Da Mike Jun 21 at 9:29
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.