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
Best Answer
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.
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\;.$$