Pairs of non-empty disjoint sets

Question

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$

Answer 1

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$

Answer 2

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.