Proof of $A_3(n)$ in Stanley's Enumerative Combinatorics Exercise 14, Chapter 2

Question

The question is stated as follows:

Let $A_k(n)$ denote the number of $k$-element antichains in the Boolean algebra $B_n$, i.e., the number of subsets $S$ of $2^{[n]}$ such that no element of $S$ is a subset of another. Show that $A_3(n) = \frac{1}{6}(8^n-6\cdot 6^n+6\cdot 5^n+3\cdot 4^n-6\cdot 3^n+2\cdot 2^n)$.

My attempt

Use PIE, let $E_1$ denote the event that $A_1\subset A_2$ or $A_2\subset A_1$, $E_2$ for $A_1,A_3$ and $E_3$ for $A_2,A_3$ in a similar way. We have \begin{equation*} |E_1\cup E_2\cup E_3| = 3|E_1|-3|E_1\cap E_2|+|E_1\cap E_2\cap E_3| \end{equation*} by symmetry.

Now $|E_1\cup E_2\cup E_3| = {2^n\choose 3}-A_3(n)$, because the event is that at least one of $A_1,A_2,A_3$ contains another.

$|E_1| = ({2^n\choose 2}-A_2(n))(2^n-2)$, because the event is that two subsets are not an antichain and the third is chosen arbitrarily, and should be different to the first two. Here $A_2(n) = \frac{1}{2}(4^n-2\cdot 3^n+2^n)$.

$E_1\cap E_2\cap E_3$ denotes the event that the three subsets form an ascending chain. Thus \begin{equation*} |E_1\cap E_2\cap E_3|=\sum_{i = 0}^n{n\choose i}\sum_{j=1}^{i-1}{i\choose j}(2^j-1). \end{equation*}

$|E_1\cap E_2|$ is a big deal, it has two cases:

1. $A_1$ contains other two, the number of which is \begin{equation*} \sum_{i = 0}^n{n\choose i}{2^i-1\choose 2} \end{equation*}
2. one is bigger than $A_1$, the other one is contained in $A_1$, the number of which is \begin{equation*} \sum_{i=0}^n{n\choose i}(2^i-1)(2^{n-i}-1). \end{equation*}

Now we can compute $A_3(n)$, but it doesn't meet the result.

Where is the mistake in my proof?

Answer 1

Once you denote $E_1,E_2,E_3$ like this, the sets $A_1,A_2,A_3$ should be considered in order.

$|E_1\cup E_2\cup E_3|$ should be $3!({2^n\choose 3}-A_3(n))$. $|E_1|$ should be $2({2^n\choose 2}-A_2(n))(2^n-2)$, since we have two possible cases: $A_1\subset A_2$ or $A_2\subset A_1$. $|E_1\cap E_2\cap E_3|$ should be $6$ times of your result.

For $E_1\cap E_2$, we should have four cases:

(1). $A_1\subset A_2$ and $A_1\subset A_3$.

(2). $A_2\subset A_1$ and $A_3\subset A_1$.

(3). $A_2\subset A_1\subset A_3$.

(4). $A_3\subset A_1\subset A_2$.

The number of (1) and (2) are the same (we can take a complement of each), and the number of (3) and (4) are the same.

For (2), the number should be $$\sum_{i=0}^n{n\choose i}{2^i-1\choose 2}\cdot 2.$$Here we multiply $2$ because $A_2$ and $A_3$ are labelled.

For (3), the number should be what in your case 2.

So $|E_1\cap E_2| = 2(\#(2)+\#(3))$.

This should give the right result.