1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lulu Apr 13 at 15:28
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.