Find the number of collections of $16$ distinct subsets of $\{1,2,3,4,5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \not= \emptyset$
Solution given:
Denote by $\mathcal C$ a collection of 16 distinct subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$. Denote $N = \min \left\{ |S|: S \in \mathcal C \right\}$.
Case 1: $N = 0$.
This entails $\emptyset \in \mathcal C$. Hence, for any other set $A \in \mathcal C$, we have $\emptyset \cap A = \emptyset$. This is infeasible.
Case 2: $N = 1$.
Let $\{a_1\} \in \mathcal C$. To get $\{a_1\} \cap A \neq \emptyset$ for all $A \in \mathcal C$. We must have $a_1 \in \mathcal A$.
The total number of subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain $a_1$ is $2^4 = 16$. Because $\mathcal C$ contains 16 subsets. We must have $\mathcal C = \left\{ \{a_1\} \cup A : \forall \ A \subseteq \left\{ 1, 2, 3, 4, 5 \right\} \backslash \left\{a_1 \right\} \right\}$. Therefore, for any $X, Y \in \mathcal C$, we must have $X \cap Y \supseteq \{a_1\}$. So this is feasible.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $a_1$. Therefore, the number of solutions is 5.
Case 3: $N = 2$.
Case 3.1: There is exactly one subset in $\mathcal C$ that contains 2 elements.
Denote this subset as $\left\{ a_1, a_2 \right\}$. We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$. Therefore, the number of solutions is $\binom{5}{2} = 10$.
Case 3.2: There are exactly two subsets in $\mathcal C$ that contain 2 elements.
They must take the form $\left\{ a_1, a_2 \right\}$ and $\left\{ a_1, a_3 \right\}$.
We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$ and $\left\{ a_2, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$ and $\left\{ a_1, a_3 \right\}$. Therefore, the number of solutions is $5 \cdot \binom{4}{2} = 30$.
Case 3.3: There are exactly three subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$.
We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_2, a_3, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$. Therefore, the number of solutions is $5 \cdot \binom{4}{3} = 20$.
Case 3.4: There are exactly three subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_2, a_3 \right\}$.
We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_1, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_2, a_3 \right\}$. Therefore, the number of solutions is $\binom{5}{3} = 10$.
Case 3.5: There are exactly four subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$, $\left\{ a_1, a_5 \right\}$.
We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_1, a_4, a_5 \right\}$, $\left\{ a_2, a_3, a_4 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.
Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$, $\left\{ a_1, a_5 \right\}$. Therefore, the number of solutions is 5.
Putting all subcases together, the number of solutions is this case is $10 + 30 + 20 + 10 + 5 = 75$.
Case 4: $N \geq 3$.
The number of subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements is $\sum_{i=3}^5 \binom{5}{3} = 16$. Because $\mathcal C$ has 16 elements, we must select all such subsets into $\mathcal C$. Therefore, the number of solutions in this case is 1.
Putting all cases together, the total number of $\mathcal C$ is $5 + 75 + 1 = \boxed{\textbf{(081) }}$.
Though I Did same approach to reach the solution but I want to know is there any general way to solve this problem. (recursion or Some other)
Since Given set contains only Five elements so I think author of problem wants us to make cases.
Best Answer
Let $[n] = \{1, 2, 3, \ldots, n\}$. If we consider the problem of counting collections of $2^{n - 1}$ distinct subsets of $[n]$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \ne \varnothing$, then the answer would be a sum with exponentially (of $n$) many summands, or may be even superexponentially many. (The answer will be superexponential of $n$ and I can prove this statement if needed.) This means that there is likely no simple way to solve such problems without considering many cases. Less cases you have, the better your solution is.
Below I provide a very similar, but a bit simplified and more rigorous solution. Also it unites $4$ subcases in $2$.
Note that for each subset $S \subseteq [5]$ the subset $\overline{S} = [5] \setminus S$ can't present in $\mathcal C$ together with $S$. Thus we have $16$ pairs of incompatible subsets. This means that $\mathcal C$ contains exactly one subset from each pair.
The next observation is that by pigeon-hole principle if $S, T \subseteq [5]$, $|S| \ge 3$ and $|T| \ge 3$ then $S \cap T \ne \varnothing$. This implies that the only $\mathcal C$ consisting of all subsets of $3$ and more elements is valid. (BTW the provided solution lacks such validity checks.)
Note that empty subset can't be in $\mathcal C$ in any case. And $1$-element subset requires all other subsets to contain the same element. There are exactly $16$ such subsets which gives us (up to the choice of the $1$-element subset) $5$ more sets $\mathcal C$, each of which is obviously valid. Now we have to consider only case when we have at least one $2$-element subset (let call it pair), but no subset of less than $2$ elements.
Also, by the same pigeon-hole principle if $S, T \subseteq [5]$, $|S| = 2$ and $|T| \ge 3$ then $S \cap T \ne \varnothing$ iff $S \ne \overline{T}$. This implies that we can have any number of pairs, just any two of them should have a common element to make a valid $\mathcal C$. There are two essentially different options for pairs: there are three of them with no common element (for all three) or all pairs contain the same element. The first case gives us $\binom{5}{3} = 10$ sets $\mathcal C$.
The second one is more tricky. We can choose any of $5$ elements and any of $15$ non-empty subsets of the set of $4$ pairs containing this element. Note that we count each case with at least two pairs exactly once, but case with one pair exactly twice: firstly for one element of the pair and then for the other element of the pair. Therefore we should subtract the number $\binom{5}{2}$ of pairs.
Totally we have $1 + 5 + 10 + 75 - 10 = 81$.