# If $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$?

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?

• You overcount because choosing $b_1\in B$ first and then $b_2\in B$ later is the same as doing it the other way round. – lulu Apr 13 at 15:28

## 1 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.