0
$\begingroup$

$U=\left \{ 1,2,3,4,5 \right \}$

and $A$ and $B$ are two subsets. If $n(A ∩ B) = 2$ and $A \neq B$ .

Then total number of ordered pairs $(A, B)$ are possible where $n(X)$ represents the cardinality of set $X$ ?


My Try:-

A). First select $2$ elements for set A and put the same elements in set $B$. Now, we can have different possibilites like

$A=\left \{ 1,2 \right \}$ and possibilities for B are $\left \{ 1,2,3/4/5/34/35/45/345 \right \}$

Total $140$ ways .

B). Then select $3$ elements for set $A$ and do same procedure for B, but every time pairs will decrease .

$18 + 16 + 14 + 12 +10+8+6+4+2=90 $ ways .

Hence, Total = $230$ ways.


But, I don't have answer for this ? Is it correct ?

$\endgroup$
  • $\begingroup$ How does one read $A! = B$? $\endgroup$ – Alvin Lepik Jul 31 '17 at 7:00
  • $\begingroup$ For one set (i.e. one entry of the ordered pair $(A,B)$), then $\{1,2\} = \{2,1\}$ in this situation, correct? $\endgroup$ – bloomers Jul 31 '17 at 7:13
  • 2
    $\begingroup$ Doing that way, you should obtain $\binom{5}{2} \cdot (2^3-1) + \binom{5}{3} \cdot \binom{3}{2} \cdot 2^2 + \binom{5}{4} \cdot \binom{4}{2} \cdot 2^1 + \binom{5}{5} \cdot \binom{5}{2} \cdot 2^0 = 70 + 120 + 60 + 10 = 260$ ways where summands correspond to $A$ of subsequent sizes $2, 3, 4, 5$. However, your solution doesn't fully explain how you get those numbers and why there are only two cases, so it's difficult to tell where the mistake is. $\endgroup$ – Adayah Jul 31 '17 at 7:35
  • 2
    $\begingroup$ To get a pair $(A, B)$ with $|A| = i$, we first pick $A \subseteq U$ of size $i$, we can do this in $\binom{5}{i}$ ways. Then pick a $2$-element subset of $A$ for the intersection $A \cap B$, this can be done in $\binom{i}{2}$ ways. In the end for every element in $U \setminus A$ choose whether it should belong to $B$ or not - that gives $2^{5-i}$ ways. Then just sum over $i = 2, 3, 4, 5$. However, for $i=2$ we have to ensure that $A$ and $B$ are distinct, so in the last step above at least one element from $U \setminus A$ must be chosen to belong to $B$, yielding $2^3-1$ ways to do it. $\endgroup$ – Adayah Jul 31 '17 at 7:48
  • 1
    $\begingroup$ Yes, because to each unordered pair $\{ A, B \}$ correspond exactly two ordered pairs -- $(A, B)$ and $(B, A)$. Since we demand the sets are distinct, we never get one pair $(A, A)$ instead of two. $\endgroup$ – Adayah Jul 31 '17 at 8:27
5
$\begingroup$

A nice way to do this:

First note that the number of ways to pick two disjoint subsets $A, B \subseteq \{ 1, 2, \ldots, n \}$ is $3^n$, because for every $i \in \{ 1, 2, \ldots, n \}$ we choose whether it belongs to $A$ or $B$ or neither. If we want the sets to be distinct, we should subtract $1$ for the case $A = B = \varnothing$, so we get $3^n - 1$.

Now to pick $A, B \subseteq U$ such that $|A \cap B| = 2$ we can:

  • First select $I \subseteq U$ of size $2$ to be the intersection - we can do this in $\binom{5}{2} = 10$ ways,
  • Then select disjoint and distinct $A \setminus I, B \setminus I \subseteq U \setminus I$ - we can do this in $3^3 - 1 = 26$ ways.

So the total number of ways is $10 \cdot 26 = 260$.

$\endgroup$
  • $\begingroup$ What is the meaning of "$A∖I,B∖I⊆U∖I$" ? $\endgroup$ – Jon Garrick Jul 31 '17 at 7:28
  • $\begingroup$ You can think of $\setminus$ as subtraction. $A\setminus I = A - I$. Take the elements of $I$ away from set $A$. $\endgroup$ – Alvin Lepik Jul 31 '17 at 7:30
  • $\begingroup$ @AlvinLepik if suppose we do not consider "A not equal to B" condition then number of unordered pairs would be 130+10 = 140 right ? $\endgroup$ – Zephyr Dec 1 '17 at 19:13

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.