# Pairs of non-empty disjoint sets

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$

• 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$.) – Misha Lavrov Apr 21 '18 at 5:28
• @MishaLavrov Ah yes, I see! I was not aware of AIME, I'll admit. Thanks – Tamojit Maiti Apr 21 '18 at 5:31

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$