If a set $U$ has $n$ elements. How many pairs of subsets $(C,D)$ of $U$ can we find satisfying the strict inclusion $D\subset C$ ?
Assume $D$ has $k$ elements, then $C$ must contain at least $k+1$ elements, and the new elements can be chosen from $n-k$ elements, which are not in $D$ in $2^{n-k}-1$ ways. (Without empty set), Therefore we obtain:
$\displaystyle\sum\limits_{k=0}^{n}\binom{n}{k}(2^{n-k}-1)$
Can you verify this ?
Thanks.
Yes it's correct, you can write it as $-2^n + 2^n(\sum_{k=0}^{n} {n \choose k}2^{-k})$ which is $3^n-2^n$ by applying the binomial theorem.
You can also see that the answer is $3^n-2^n$ by considering each element, it has 3 choices: it can be in neither $C$ nor $D$, $D$ but not $C$, or both $D$ and $C$. This gives $3^n$, but since there was the strict inclusion, we counted the $2^n$ choices where no element was in $D$ but not $C$ so the answer is $3^n-2^n$