$\begingroup$

Let $A$ be a set of $n$ elements. Then, in how many ways, can we choose an ordered pair $(B,C)$, where $B,C$ are disjoint subsets of $A$?

Let A={1}, then B can be {phi} and C can be {1}. So, one ordered pair.

Let A={1,2}, then B can be {phi}, {1} and C can be {1},{2}. So three ordered pairs.

Let A={1,2,3}. Then B can be {phi},{1},{2} and C can be {1},{2},{3}.

So six pairs ? Am I going in the right direction ?

$\endgroup$ 1

2 Answers

$\begingroup$

Your question means that you need to find the number of ways an ordered pair $(B,C)$ can be selected such that $B$ and $C$ are subsets and $B \cap C=\emptyset$.

To do so we can reduce this problem into another simpler one. Let each element of $A$(which has say $n$ elements) represent a different ball. So now you have $n$ balls.

Let's take two boxes $B$ and $C$ and a rubbish chute $R$(which will be of use when you don't want the element/ball in any of the set/box).

Now each of the $n$ balls can go into either $B$, $C$ or $R$. Which implies that each of the $n$ ball can be used in three ways.

It means that the number of ways of using the balls is $3^n$. The balls in $B$ and $C$ represent the different elements of subsets.

Therefore if we have a set $A$ with $n$ elements, there would exist $3^n$ ordered pair of disjoint subsets $(B,C)$.

$\endgroup$ $\begingroup$

Hint: Each element of $A$ is either in $B$, in $C$ or in neither. Hence, how many disjoint subsets pairs are there?

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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