2
$\begingroup$

Let $X$ be a set of $5$ elements. Then the number of ordered pairs $(A,B)$ of subsets of $X$

such that $A\neq \phi\;,B\neq \phi$ and $A\cap B = \phi\;,$ is

$\bf{My\; Try::}$ Let $X = \left\{1,2,3,4,5\right\}\;,$ then total no. of Subest of $X = 2^5 = 32$

(Which also contain $\phi$)

$\bullet\; $ If $A = \{1\}\;,$ Then $B=\left (\{2\}\;,\{3\}\;,\{4\}\;,\{5\}\;,\{2,3\}\;,\{2,4\}\;,\{2,5\}\;,\{3,4\}\;,\{3,5\}\;,\{4,5\}\;,\{2,3,4\}\;,\{2,3,5\}\;,\{3,4,5\}\;,\{2,4,5\}\;,\{2,3,4,5\}\right )$

Similarly for $A=\{2\}\;,A=\{3\}\;,A=\{4\}$ and $A=\{5\}\;,$ we get $15$ ordered pair for each single

element ed set $A$

$\bullet\; $ If $A = \{1,2\}\;,$ Then $B=\left(\{3\}\;,\{4\}\;,\{5\},\{3,4\}\;,\{3,5\}\;,\{4,5\}\;,\{3,4,5\}\right)$

Similarly for $A=\{1,3\}\;,A=\{1,4\}\;,A=\{1,5\}\;,A=\{2,3\}\;,A=\{2,4\}\;,A=\{2,5\}\;,A=\{3,4\}\;,A=\{3,5\}\;,A=\{4,5\}$ we get $7$ ordered pair for each double elemented set $A$

$\bullet\; $ If $A=\{1,2,3\}\;,$ Then $B=\left(\{4\}\;,\{5\}\;,\{4,5\}\right)$

So for $10$ ordered pair of $A\;,$ we get $3$ ordered pair of $B$

$\bullet \;$ If $A = \{1,2,3,4\}\;,$ Then $B = \{5\}$

So for $5$ ordered pair of $A\;,$ we get $1$ ordered pair of $B$

So Total ordered pair of $\left(A,B\right)$ is $ = \left(5\times 15\right)+\left(10 \times 7\right)+\left(10 \times 3\right)+\left(5 \times 1\right) = 75+70+30+5 = 180$

If Question is How can we solve using Combination (selection) way.

plz explain me, Thanks

$\endgroup$
4
$\begingroup$

Phicar’s answer gives you a nice, short calculation if you know about Stirling numbers of the second kind. If not, you can still organize your argument a bit more efficiently.

Suppose that the set $A\cup B$ has $n$ elements; clearly $n$ must be $2,3,4$, or $5$. For each of these four possible values of $n$ we can argue as follows.

There are $\binom5n$ ways to choose the set $A\cup B$. $A$ can be any non-empty proper subset of $A\cup B$. $A\cup B$ has $2^n$ subsets, but one is empty and one is all of $A\cup B$, so there are only $2^n-2$ choices available for $A$. Thus, there are $\binom5n(2^n-2)$ ordered pairs $\langle A,B\rangle$ with $|A\cup B|=n$.

The answer, therefore, is

$$\sum_{n=2}^5\binom5n(2^n-2)=\sum_{n=2}^5\binom5n2^n-2\sum_{n=2}^5\binom5n\;.$$

Now notice that

$$\sum_{n=2}^5\binom5n=\sum_{n=0}^5\binom5n-\binom51-\binom50=2^5-5-1=26\;,$$

and

$$\begin{align*} \sum_{n=2}^5\binom5n2^n&=\sum_{n=0}^5\binom5n2^n-\binom512-\binom50\\\\ &=\sum_{n=0}^5\binom5n2^n1^{5-n}-10-1\\\\ &=(2+1)^5-11\\\\ &=232\;, \end{align*}$$

so the final answer is $232-52=180$.

This calculation suggests another elementary way to perform the calculation. If we temporarily allow $A$ and $B$ to be empty, we are in effect counting the ways to split $X$ into $3$ pieces, any of which may be empty. For each of the $5$ elements of $X$ we can put that element into $A$, into $B$, or into $X\setminus(A\cup B)$. This is a $3$-way choice made $5$ times, so there are $3^5=243$ ways to make it. However, some of these splits leave $A$ or $B$ or both empty. We can use an inclusion-exclusion argument to take care of them.

How many of these splits leave $A$ empty? They are the splits that put every element into $B$ or $X\setminus(A\cup B)$, so there are $2^5$ of them. There are also $2^5$ splits leaving $B$ empty, so we have to subtract $2\cdot2^5=64$. However, that subtracts the one split with $A=B=\varnothing$ twice, so we have to add it back in. The final result is

$$243-64+1=180\;.$$

$\endgroup$
3
$\begingroup$


Hi.
You might want to look about Stirling numbers of the second kind. You want the number of ways you can take a surjective function from $[5]=\{1,2,3,4,5\}$ to $[2]=\{1,2\}$ plus the number of surjective functions from $[5]=\{1,2,3,4,5\}$ to $[3]=\{1,2,3\}$.(in $3$ to represent elements that are not taken)
In your case $2!*S_{5,2}+3!*S_{5,3}=180$.
Hope this helps.

$\endgroup$
2
$\begingroup$

First let us try to get the number of ordered pairs $(A,B)$ such that $A\cup B = \phi$, without any restrictions on $A$ and $B$. Clearly, each element can EITHER be in only $A$ OR only $B$ OR neither. So, that is $3^5$. Now, remove the cases when $A = \phi$. This is $2^5-1$. Similarly for $B$. So, the total is $3^5 - 2^5 - 2^5 + 1 = 180$ (the +1 is because we have counted the pair $(A,B) = (\phi,\phi)$ twice).

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