Matematické Fórum

stuart clark

Let $\bf{S = \{1,2,3,4,5\}}$ . Then the no. of unordered pairs $\bf{\{A,B\}.}$ of Subsets of $\bf{S}$ such that

$\bf{(i)\;\;\;\; A\cap B=\phi}$ . Where $\bf{A\neq B}$

$\bf{(ii)\;\;\;\; A\cup B=S}$ . Where $\bf{A\neq B}$

Here These two are different cases.

plz explain me in detail

Thanks

Brano · 25. 02. 2013 18:32 — Editoval Brano (25. 02. 2013 19:55)

$A\cap B=\emptyset$ iff $A^C\cup B^C=S$ ; and $A=B$ iff $A^C=B^C$ .
This means that cases (i) and (ii) are dual via complement so it is enough to solve (i), what we will do now.

Note that $A=B$ only when $A=B=\emptyset$ so we will subtract this possibility in the end and ignore the condition $A\not=B$ until then. First we count ordered pairs.
Denote $C=A\cup B$ . Since $A\cap B=\emptyset$ we have $B=C\setminus A$ and $A\subseteq C\subseteq S$ . It is enough to count pairs $(A,C)$ with that condition.
Consider that $C$ has k elements. How many options do we have to choose $C$ ?
It's $\binom{5}{k}$
and now how many options we have to choose $A\subseteq C$ ? It's $2^k$ . So the number of pairs is
$\sum_{k=0}^5\binom{5}{k}2^k=(2+1)^5$ .
Now we have to subtract that one possibility of $A=B$ to get $3^5-1=242$ . Now if $A\not=B$ then for each unordered pair $\{A,B\}$ we have exactly two ordered $(A,B)$ and $(B,A)$ so the final result for unordered pairs is
$\frac{3^5-1}{2}=121$

stuart clark · 25. 02. 2013 19:12

Thanks Barno but Here we have to Count for Unordered pairs.

Brano · 25. 02. 2013 19:38

Oh my bad! Edited.

Brano · 25. 02. 2013 20:16 — Editoval Brano (25. 02. 2013 20:16)

Now I have found much simpler solution. Again, let us count ordered pairs without condition $A\not=B$ first.
Denote $C=S\setminus (A\cup B)$ so $A,B,C$ are pairwise disjoint and $A\cup B\cup C=S$ . So every such decomposition is a mapping $f:\{1,2,3,4,5\}\to\{A,B,C\}$ (and vice versa). There are $3^5$ of such mappings. The rest is the same.

Matematické Fórum

#1 25. 02. 2013 09:33 — Editoval stuart clark (25. 02. 2013 10:05)

no. of unordered pairs

#2 25. 02. 2013 18:32 — Editoval Brano (25. 02. 2013 19:55)

Re: no. of unordered pairs

#3 25. 02. 2013 19:12

Re: no. of unordered pairs

#4 25. 02. 2013 19:38

Re: no. of unordered pairs

#5 25. 02. 2013 20:16 — Editoval Brano (25. 02. 2013 20:16)

Re: no. of unordered pairs

Zápatí