X is a set of n distinct elements. In how many ways can two subsets be chosen such that their intersection is a singleton set? $X=\{ a_1,a_2,a_3,...,a_n\}$. We have to choose $A,B \subseteq X \ni A \cap B$ is a singleton set.
I proceeded with the following approach but my answer is incorrect:
We have to choose A and B such that they have only one element in common.
Say the subset A has this fixed element from n choices then, for rest of the n-1 positions, there are n-1 candidates and each candidate can either be present in A or be absent. i.e., choices for A will look like n.2.2...2 (total n positions)
Then, for the subset B, the previously chosen element is fixed but for the rest n-1 positions, every element will behave opposite to how it behaved in A. i.e, if $a_i$ was present in A then it will be absent in B, so, there only one way in which every element can behave. i.e., choices for B will be 1.1.1...1 (n times).
So, by this faulty logic, total choices become $n2^{n-1}$ . Where did I go wrong?
The correct answer is $n3^{n-1}$
 A: "Then, for the subset $B$... every element will behave opposite to how it behaved in $A$"  False.  If $a_i$ was present in $A$ then it will be absent in $B$, yes that is true... but what if $a_i$ was not present in $A$?  Then it may or may not be present in $B$.  There was no requirement that $A\cup B = X$ here
So... for each of the elements of $X$ different than the initially selected element... we have three options.  It is in $A$ and not in $B$, it is in $B$ and not in $A$, or it is in neither.  This an answer of gives $n\cdot 3^{n-1}$ as expected.
A: You can assume $X=\{1,2,\,\ldots, n\}$.
Suppose $A,B \subset X$ are such that $A \cap B = \{1\}$.
Then $A' = A -\{1\}$ and $ B' = B -\{1\}$ and $C' =  X - A \cup B$ form a partition of $X' = \{2,3,\ldots, n\}$.
It can be seen the choices for $A',B',C'$ are in bijection with the functions $X' \to \{a,b,c\}$.
How many such functions are there?
How can the above reasoning be extended to when $A \cap B \ne \{1\}$?.
A: Here's another approach, obtained by conditioning on $i=|A \setminus B|$ and $j=|B \setminus A|$ and applying the binomial theorem twice:
\begin{align}
\sum_{i=0}^{n-1} \binom{n}{i}\binom{n-i}{1} \sum_{j=0}^{n-i-1} \binom{n-i-1}{j}
&=\sum_{i=0}^{n-1} \binom{n}{i}(n-i) 2^{n-i-1} \\
&=n \sum_{i=0}^{n-1} \binom{n-1}{i} 2^{n-i-1} \\
&=n 3^{n-1}
\end{align}
