16 votes 16 votes 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)$ $243$ $125$ $122$ $257$ Combinatory go2025-mockgate-2 counting set-theory + – gatecse asked Jan 17, 2021 • recategorized Jan 17, 2021 by Lakshman Bhaiya gatecse 827 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply faisal_sayyed commented Jan 12, 2023 reply Follow Share 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? 0 votes 0 votes JayRathi commented Jan 11 reply Follow Share here two elements set also can be disjoint like a={1,2} b={3,4} 0 votes 0 votes Shamshuddin commented Jan 21 reply Follow Share @Deepak Poonia sir I don't understand where I'm extra counting can u please help on this 0 votes 0 votes Please log in or register to add a comment.
Best answer 15 votes 15 votes For each element $[n]$ you have three choices. Either include it in $A$ but not in $B.$ Either include it in $B$ but not in $A.$ 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.$ gatecse answered Jan 17, 2021 • selected Dec 25, 2021 by Arjun gatecse comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments Atri commented Jan 7 reply Follow Share why did you subtract 1 after from 243 before division 0 votes 0 votes Deepak Poonia commented Jan 12 reply Follow Share @Atri, See This. 0 votes 0 votes Atri commented Jan 12 reply Follow Share Thank you sir got it. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes 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. Vishal_kumar98 answered Jan 9, 2022 Vishal_kumar98 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes @Deepak sir answer here answer should be opiton A na this is my approach please correct me if i am wrong JayRathi answered Jan 11 JayRathi comment Share Follow See all 3 Comments See all 3 3 Comments reply JayRathi commented Jan 11 reply Follow Share @Deepak Poonia @Arjun Suresh 6 @gatecse sir please check my approach 0 votes 0 votes Deepak Poonia commented Jan 12 i edited by Deepak Poonia Jan 12 reply Follow Share @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) = 122Also understand this other approach which is quick. Check out ALL similar GATE & TIFR questions HERE. 1 votes 1 votes JayRathi commented Jan 12 reply Follow Share ok sir 0 votes 0 votes Please log in or register to add a comment.