5
$\begingroup$

Question: Let $S=\{1,2, \cdots, 10 \}$. Then the number of pairs $(A, B)$, where $A$ and $B$ are non-empty disjoint subsets of $S$ is?

[I could solve the question as demonstrated below, but it involves calculating a tedious sum of products, which would take up a lot of time. It is typically expected to solve this in a couple of minutes, so I was wondering if there was a faster way to do this.]

My approach: Let the set $A$ consist of $x$ elements. There are ${10 \choose x}$ ways of making that selection.

We are now left with $10-x$ elements.

Let the set $B$ consist of $y$ elements. This selection can be done by ${10-x \choose y}$ ways.

The total number of ways can be found out by summing over the product of the two above as $\sum_{x=1}^{9} \sum_{y=1}^{10-x} {10 \choose x}{10-x \choose y} $ which comes out to be $57002$

$\endgroup$
  • 2
    $\begingroup$ Note: this is problem #9 on the 2002 AIME II. (Well, aside from the nonsense that all AIME problems tack onto the end where you need to convert the answer to an integer between $0$ and $999$.) $\endgroup$ – Misha Lavrov Apr 21 '18 at 5:28
  • $\begingroup$ @MishaLavrov Ah yes, I see! I was not aware of AIME, I'll admit. Thanks $\endgroup$ – Tamojit Maiti Apr 21 '18 at 5:31
8
$\begingroup$

Suppose we have set $A$, $B$ and $S=\{1,2,...10\}$. So for each $x\in S$ you can put it in exactly one of this sets: $A$ or in $B$ or $(A\cup B)'$. So for each $x$ you have 3 choices and thus you can choose $A,B$ on $3^{10}$ ways.

Now we have to substract all pairs where one of the sets is empty. If $A$ is empty, $B$ could be any subset apart from $A$. So we have $2^{10}$ choices. The same is true if $B$ is empty. So we have $2^{11}$ such pair of sets. But we have pair $(\emptyset,\emptyset )$ counted twice, we have to substract $2^{11}-1$ bad pairs of sets.

So the finaly result is $3^{10}-2^{11}+1$

$\endgroup$
  • 1
    $\begingroup$ It will be $3^{10}$, since $A$ has 10 elements $\endgroup$ – Tamojit Maiti Apr 21 '18 at 5:14
  • 1
    $\begingroup$ It cannot be $3^{10}$.You need to ensure that $A,B$ are non empty. $\endgroup$ – copper.hat Apr 21 '18 at 5:14
  • 2
    $\begingroup$ $A,B$ can be empty in $2^{11}$ ways. And in one of these instances, both $A,B$ are empty, so we need to add $1$ to the result. $\endgroup$ – Tamojit Maiti Apr 21 '18 at 5:16
  • $\begingroup$ The final result becomes $3^{10} - 2^{11} + 1 = 57002$ $\endgroup$ – Tamojit Maiti Apr 21 '18 at 5:18
  • 1
    $\begingroup$ Edit........... $\endgroup$ – Aqua Apr 21 '18 at 5:50
5
$\begingroup$

It is also interesting to note that the sum you get can be simplified in the following way using the binomial theorem: \begin{align} \sum_{x=1}^{9}\sum_{y=1}^{10-x}{ 10 \choose x}{ 10-x \choose y} &= \sum_{x=1}^{9}{ 10 \choose x}\left(\sum_{y=0}^{10-x}{ 10-x \choose y} -1 \right)\\ &=\sum_{x=1}^{9}{ 10 \choose x} (2^{10-x} -1) \\ &= \sum_{x=0}^{10}{ 10 \choose x}2^{10-x} -2^{10}-1 - \sum_{x=0}^{10}{ 10 \choose x}+1+1 \\ &= 3^{10}-2^{10}-1-2^{10}+1+1 \\ &= 3^{10}-2^{11}+1 \end{align} Thus getting a pretty interesting identity.

$\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.