Let $S=\{1,2,\ldots,n\}$. In how many ways can we choose two subsets $A$ and $B$ of $S$ so that $B \neq \emptyset$ and $B \subseteq A \subseteq S$?
My first approach involves finding the sum $\sum_{k=1}^{n}\sum_{i=1}^{k}{n \choose k}{k \choose i}$ which gives $3^n -2^n$ cases.
But,I was thinking of another way of calculating this.
I consider three pieces $B,AB^{c},A^{c}$.Now I select one integer in $n$ ways and place it in $B$ and the remaining $n-1$ integers have $3$ choices to be placed each, so, the number of cases comes out to be $n3^{n-1}$ which overcounts the number of cases. Can anyone provide a reason why?
Best Answer
Your method overcounts because choosing $b_1\in B$ first and then $b_2\in B$ later is the same as doing it the other way round.
Here is a combinatorial argument:
For each element in $S$ choose whether it is in $B$, $A- B$, or $A^c$. That's $3^n$ choices. To be clear: those choices define the sets $A,B$. Now, we exclude those in which no element is in $B$...that's an exclusion of $2^n$ choices, and we are done.