Total number of unordered pairs of disjoint subsets of S

Let $S = \{1, 2, 3, 4\}$. Find the total number of unordered pairs of disjoint subsets of $S$.

I know the answer is $41$ since it's solved in the book as the expression

$$\frac{3^4 -1}{2!} +1 \ .$$

I couldn't get through the solution above, I have solved it by making pair of sets. Please help me to understand the way by which the question has been solved in the book.

Solution 1:

A pair of disjoint subsets is formed by examining each element of $S$ in turn and deciding whether to put it into one subset, into the other subset, or into neither.   Three choices for each of 4 elements gives us the term $3^4$ as the count of all possible ordered pairs of disjoint subsets that can be formed.

To count only unordered pairs, we need to determine how to group every ordered pair into equivalence classes.   Now, each pair is one of $2!$ permutations, except the pair $\langle \varnothing, \varnothing\rangle$.  ( The null set is disjoint with itself, as $\varnothing \cap \varnothing =\varnothing$ )

Hence the count of unordered pairs of disjoint subsets of $S$ is : $\dfrac {3^4-1}{2!}+1$

Solution 2:

Assuming, $\large\color{maroon}{\text{S}}$ = $\left \{ 1,2,3 \right \}$ , then following is the required Relation. $$\begin{align*} \text{Z} = \left \{ \left ( R,T \right ) \;\; | \; \; \text{R,T} \subseteq \; \text{S ,} R \cap T = \phi \right \} \end{align*}$$

The pair $(R,T)$ is a disjoint subset pair of $S$.

$Z$ in matrix representation, $\\$

First we will count the cardinality of $Z$ based on ordered pair $(R,T)$.

example :

• first green circle means $\left \{ 2 \right \}$ and $\left \{ 3 \right \}$ is one pair $\left ( \left \{ 2 \right \},\left \{3  \right \} \right )$ in the relation $Z$. And because, we are considering ordered pairs ,then $\left ( \left \{ 3 \right \},\left \{2  \right \} \right )$ will also be a pair in relation $Z$.
• Second green circle means $\left \{ 2,3 \right \}$ and $\left \{ 1 \right \}$ is one pair $\left ( \left \{ 2,3 \right \},\left \{1  \right \} \right )$ in the relation $Z$. And we are considering ordered pairs, then $\left ( \left \{ 1 \right \},\left \{2,3  \right \} \right )$ will also be a pair in relation $Z$.

Now,

No of such ordered pairs in relation $Z$ =  No of $1$'s in the matrix representation.

Counting procedure:

one example:

1. 2nd row of matrix, which is related to set $\left \{ 1 \right \}$. No of subsets that $\left \{ 1 \right \}$ will be related to are the subsets of $\left \{ 2,3 \right \}$.
2. How many subsets of $\left \{ 2,3 \right \}$ ? . = $2^{3-1}$ .(because $1$ is missing here).
3. Similarly for subsets $\left \{ 2 \right \}$ and $\left \{ 3 \right \}$ ,, i.e. 3rd and 4th row of the matrix.
4. So total $1$'s for these $\binom{3}{1} = 3$ ,  one element subsets $\left ( \left \{ 1 \right \},\left \{ 2 \right \},\left \{ 3 \right \} \right )$ , is = $\binom{3}{1}*2^{3-1}$. (Or, total no of 1's in 2nd,3rd,4th rows of the matrix)

Doing in the same way, will arrive in the follwoing series,

$$\begin{align*} &=\binom{3}{0}*2^{3-0} + \binom{3}{1}*2^{3-1} + \binom{3}{2}*2^{3-2} + \binom{3}{3}*2^{3-3} \\ &=\binom{3}{0}*1^0*2^{3-0} + \binom{3}{1}*1^1*2^{3-1} + \binom{3}{2}*1^2*2^{3-2} + \binom{3}{3}*1^3*2^{3-3} \\ &=\sum_{r=0}^{3}\binom{3}{r}1^{r}.2^{3-r} \\ &= (1+2)^{3} \\ &=3^3 \end{align*}$$ 

If we assume $\large\color{maroon}{\text{S}}$ = $\left \{ 1,2,3,4,5,6....n \right \}$

Then this above value will be $\large\color{red}{3^n}$

Now, how many unordered ?

1. This relation Z is symmetric with only one self-loop at $\phi$..
2. Whenever we need only unordered pairs $(R,T)$ then, we will only count off-diagonal $1$'s and one $(\phi,\phi)$ pair.

No of unordered $(R,T)$ pairs =  $\begin{align*} \frac{3^n -1}{2} +1 \end{align*}$

Solution 3:

If S contain 4 elements then any element of S has got three possibilities either in A or B or none.thus each has 3 choices for 4 elements we have 81 choices.They are choices for ordered pair (A,B). Only one pair is counted twice (¤,@).The no. Of an ordered pairs=81-1/2+1=41.