GATE Overflow Test Series | Mock GATE | Test 2 | Question: 32

Question

Let $S = \{1, 2, 3, 4, 5\}.$ The number of unordered pairs $A, B$ where $A$ and $B$ are disjoint subsets of $S$ is. (counting unordered pairs simply means we do not distinguish the pairs $A,B$ and $B,A)$

• A. $243$
• B. $125$
• C. $122$
• D. $257$

Comments

We want disjoint subsets, for that, we can either put the elements in set A or in set B

This is what I did, 

First choose for A and second for B

$\binom{5}{0}*\binom{5}{5} + \binom{5}{1}*\binom{5}{4} + \binom{5}{2}*\binom{5}{3}$

$1 + 5*5 +  10 * 10 $

$1 + 25 + 100$

$126$

@gatecse where did I go wrong?

---

here two elements set also can be disjoint like

a={1,2} b={3,4}

---

@Deepak Poonia sir I don't understand where I'm extra counting can u please help on this

Answer 1

For each element $[n]$ you have three choices.

1.  Either include it in $A$ but  not in $B.$
2.  Either include it in $B$ but not in $A.$
3.  Neither in $A$ not in $B.$

 This gives us $3^5 = 243$ ordered pairs. It also include the case $(\emptyset, \emptyset).$ Other than this, for every other pair of subsets there are $2!$ pairs when counted as ordered pair. So, number of disjoint unordered pairs $ = \dfrac{243-1}{2} + 1 = 122.$

Comments

why did you subtract 1 after from 243 before division

---

@Atri, See This.

---

Thank you sir got it.

Answer 2

The number of unordered pairs $A, B$ where $A$ and  $B$ are disjoint subsets of $S$ is given by the formula:-

$\tfrac{3^{n}+1}{2}$

Here, $n$ is the number of elements in the set.

Answer 3

@Deepak sir answer here answer should be opiton A na this is my approach please correct me if i am wrong

Comments

@Deepak Poonia  @Arjun Suresh 6 @gatecse sir please check my approach

---

@JayRathi, Your approach is correct if question asks for Ordered Pairs. But question says that $( \{ 1,2 \}, \{ 3,4 \} )$ and $( \{ 3,4 \}, \{ 1,2 \} )$  are Same. You have counted them twice. 

Correct answer will be half of your answer because you have counted every correct answer twice, except $(\phi, \phi)$ which is counted once. So, answer will be 1(for $(\phi, \phi)$) + (243 - 1)/2 (for rest) = 122

Also understand this other approach which is quick. Check out ALL similar GATE & TIFR questions HERE.

---

ok sir