Let $X$ be as set containing $n$ elements.Find the number of all ordered triplets $(A,B,C)$ of subsets of $X$ such that $A$ is a subset of $B$ and $B$ is a proper subset of $C.$
I have no idea how to solve this problem.Please help me.Thanks.
[Math] Find the number of all ordered triplets $(A,B,C)$ of subsets of $X$ such that $A$ is a subset of $B$ and $B$ is a proper subset of $C.$
combinatoricselementary-set-theory
Best Answer
Let us forget temporarily about the "proper" subset restriction on $B$. So we want to divide $X$ into $4$ pairwise disjoint parts, $A_1,A_2,A_3,A_4$, and then let $A=A_1$, $B=A_1\cup A_2$, and $C=A_1\cup A_2\cup A_3$.
Given such a partition of $X$, there is an associated function $f:X\to\{1,2,3,4\}$ given by $f(x)=i$ if and only if $x\in A_1$. And given any function $f:X\to \{1,2,3,4\}$, we can use $f$ to produce a partition of $X$ into sets $A_1,A_2, A_3,A_4$, and then produce uniquely determined sets $A\subseteq B\subseteq C\subseteq X$.
There are $4^n$ functions from $X$ to $\{1,2,3,4\}$. So without the proper subset restriction, there are $4^n$ ways to do the job. We leave dealing with the restriction to you. From $4^n$ we must subtract the number of ways to choose $A,B,C$ such that $A\subseteq B=C\subseteq X$.