3
$\begingroup$

I found this question in a book. The same question has been asked before, but I want a more generalised and rigorous, so to speak, answer. The question reads- " Consider the set $S= \{1,2,3,4\}.$ Calculate the no. of unordered pairs of disjoint subsets."

To start with, I have no idea as to what is meant by "unordered pair of disjoint subsets". Can someone explain that please?(of course, I do know what disjoint sets are)

Secondly (probably the more important one), the book gives the answer as $41,$ with the solution reading- " no. of unordered pairs of disjoint subsets is $\frac{3^{n} + 1}{2}$. Using $n=4,$ we get $41".$

Now, I don't know how do they derive the term $\frac{3^{n} + 1}{2}$. Can someone please give a rigorous derivation for it? I want to know how does it give the no. of disordered pairs of disjoint subsets( I don't know what that means). Also, if the total no. of subsets is $2^m = 16$, how do I get $41(>16)$ sets as the answer? I am in a fix.

So, in short, can someone-

(1) Explain the meaning of unordered pair of disjoint subsets

(2) Explain the DERIVATION of the formula- no. of unordered pairs of disjoint subsets = $\frac{3^n +1}{2}$

Thanks in advance!

$\endgroup$
4
  • 3
    $\begingroup$ math.stackexchange.com/questions/1223425/… $\endgroup$
    – juantheron
    Apr 18 '15 at 15:15
  • 1
    $\begingroup$ Or instead of just reading the answer linked by @juantheron you could try and see if you can come up with it on your own using just a hint or two. $\endgroup$
    – DRF
    Apr 18 '15 at 15:17
  • 1
    $\begingroup$ @RobArthan The formula the OP gives is actually correct plus it corresponds to the other answer. $\endgroup$
    – DRF
    Apr 19 '15 at 16:04
  • 1
    $\begingroup$ @DRF: you are right. Brainstorm on my point. I'll delete my comment. $\endgroup$
    – Rob Arthan
    Apr 19 '15 at 18:09
3
$\begingroup$

Unordered pair of disjoint subsets is exactly what it says it is. You are counting pairs of disjoint subsets (say $(\{1,2\},\{3\}$)) but you want them unordered so the pair I just wrote is the same as $(\{3\},\{1,2\})$.

As for the second part of you question consider what the choice for each element in you set is in terms of where it appears in the pair of disjoint subsets and try and think if you could come up with a characteristic function for this.

One more quick hint. If you're like me you might be slightly confused by the +1 in the formula but consider what you are and aren't double counting edit and then fix it as pointed out in the comments below your question. Missed that one myself as I didn't actually bother to do the math fully. edit again. Once I did the math I realised that the commenter above confused me. The formula is correct with a -1 and is exactly what the other poster has too.

Edit Extra hint. Consider where each element of your original set can show up in the (for now ordered) pair of disjoint subsets. It can be in the first set (call that state 1) or in the second subset (call that state -1) or in neither of the subsets (call that state 0). Now think of the function that maps each element to its state in a given (ordered) pair of disjoint subsets.

$\endgroup$
10
  • $\begingroup$ can you please derive the formula? I really don't understand what to do, other than knowing (gut feeling :P) it has to do with combinations, not permutations...I will really appreciate it. $\endgroup$
    – GRrocks
    Apr 18 '15 at 15:18
  • $\begingroup$ @GRrocks it has very little to do with permutations and combinations on the face of it. The derived formula is given in the link by juantheron if you want it. But it is not that hard to come up with. I will add one more hint in the answer. $\endgroup$
    – DRF
    Apr 18 '15 at 15:21
  • $\begingroup$ I found this derivation - meritnation.com/ask-answer/question/… but I am not sure if this is the one your hints suggest....i don't understand it fully though...any help? $\endgroup$
    – GRrocks
    Apr 18 '15 at 15:32
  • $\begingroup$ I dont get the "no. of subsets of size n of a set of size m" term part $\endgroup$
    – GRrocks
    Apr 18 '15 at 15:35
  • $\begingroup$ @GRrocks I'm not registered at the site so I can only see glimpses of that proof, but from what I can see no that's not it. The trick I'm proposing is instead of counting subsets (which is fairly hard) you only get to count functions from the original set $S=\{1,2,3,4\}$ to the set $\{-1,0,1\}$ which turns out to be much easier. You can also think of it as counting the number of sequences of $\{-1,0,1\}$ of length 4. $\endgroup$
    – DRF
    Apr 18 '15 at 15:41
1
$\begingroup$

As @DRF mentioned in the above answer, there are 3 possibilities for any element. Either it is in First subset or in second or it is in neither of them. This gives us 3 raised to n possibilities. However, these possibilities would also include duplicates. Consider an example of this set {1,2,3} now in this set, the 9 possibilities also contain these two possibilities First Set={1}, Second Set={2} and {3} is in neither of the sets. Another one is first set={2}, Second set={1} and {3} is in neither. These are duplicates as we need unordered pairs. We can extend this logic and conclude that there is a duplicate for all the possibilities. Hence the number of distinct possibilities are 3 raised to n divided by 2. As far as (+1) is concerned in the numerator, I do not have much idea about it.

$\endgroup$
1
  • $\begingroup$ the $3^n$ possibilities also include the $\{\}^n=\{\}$ case, that is the empty set. This is not duplicated. If you exclude it then you have $(3^n-1)/2$ unordered pairs. If in these you include also the empty set = empty pair, then you have $(3^n-1)/2+1=(3^n+1)/2$. $\endgroup$
    – G Cab
    Jan 24 '17 at 15:12
1
$\begingroup$

As Dhiren Navani explained, we get duplicate cases for each possible case except for the one when both sets are null sets. So in order to divide the result by 2 we have to first add one extra duplicate case for both empty sets before dividing and so we get +1 in the numerator..

$\endgroup$
1
  • $\begingroup$ I would encourage you to use TeX markup on this site, no matter how trivial it seems. Additionally, it seems you've not answered the full question. Answers should fully answer all parts of a question, regardless of what other answers say. $\endgroup$
    – The Count
    Jan 2 '17 at 18:31

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.