# Total number of ordered pairs (A, B) possible?

$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 ?

• How does one read $A! = B$? – Alvin Lepik Jul 31 '17 at 7:00
• For one set (i.e. one entry of the ordered pair $(A,B)$), then $\{1,2\} = \{2,1\}$ in this situation, correct? – bloomers Jul 31 '17 at 7:13
• 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. – Adayah Jul 31 '17 at 7:35
• 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. – Adayah Jul 31 '17 at 7:48
• 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. – Adayah Jul 31 '17 at 8:27

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

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