no. of disordered pairs of disjoint subsets 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!
 A: 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.
A: 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.
A: 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..
