I'm trying to calculate the number of $2$-element chains and anti-chains of $B_n$, where $B_n$ is the boolean algebra partially ordered set of degree $n$.
I understand that I want to take all of the different combinations of two sets $A$ and $B$ that are subsets of $[n]$, in which $A\subsetneq B$. But I'm not sure about the general strategy. Could any one give me some hints on this problem?
On
EDIT: THIS IS ALL WRONG, I WAS CONFUSING THE DEFINITION OF CHAIN WITH THE EDGE ON HASSEL DIAGRAM. SILLY ME. I'LL STILL LEAVE THIS HERE SO PEOPLE WHO STUMBLED UPON THIS WILL KNOW THAT THIS IS A POSSIBLE MISTAKE.
I am challenging @Brian M. Scott (@brian-m-scott)'s answer.
Let's take a look at $B_3$:
It has 12 2-element chains, if we plug n = 3 into $3^{n}-2^{n}$ we will get an answer of 19, which is incorrect.
By examine $B_3$, or in fact any this kind of Hasse Diagram, we will find out that at depth i (starting from 0):
Number of Nodes = $(_{i}^{n})$
Number of Edges Connecting Next Depth = $(_{n-i-1}^{n-i})$ = n-i
Thus, the total number of 2 element chains = $\sum _{i=0}^{n-i} (_{i}^{n})(n-i)$
I have tested this result with $B_3$ and $B_4$ and they are correct.
And then we can in some way write this as a closed form.
And since we have the number of 2-element chains, and like Brian said, the relationship between 2 elements are either chains or antichains. The total number of chains and antichains is $(_{2}^{n})$. So the number of antichains is $(_{2}^{n})$ minus what we got for the previous part.
HINT: Every pair of subsets of $[n]$ is either a chain or an antichain. It’s probably a bit easier to count the chains. To form a chain $A\subsetneqq B\subseteq[n]$, you need to split $[n]$ into three subsets, $A$, $B\setminus A$, and $[n]\setminus B$. The only restriction is that $B\setminus A$ must not be empty. Imagine going through $[n]$ one element at a time, tossing each element into one of the three sets. How many ways are there to do this? How many of them have to be discarded, because they leave $B\setminus A$ empty?