# What is the number of ordered pairs of unordered pairs of a set $S$ that share one element?

Question:

Let $S = \{1,2, \dots ,n \}$. I want to count how many ordered pairs of unordered pairs (sets of the form $( \{ i,j\}, \{k,\ell \} | i,j,k,\ell \in S )$, where $( \{1,2 \}, \{2,3 \} ) \ne ( \{2,3 \}, \{1,2 \} )$ ). I can find such that $|\{i,j\}\cap\{k,\ell\}| = 1$

My attempt:

If I fix a pair $\{i,j \}$, then I can find $(n-1)(n-2)$ other pairs that have one element in common with it. First, I choose the $(n-1)$ remaining elements that are different from $i$, then I choose the $(n-2)$ remaining elements that are different from $j,i$.

But now if I let the pair $\{i,j \}$ vary, I can't find a way to add all the pairs of pairs up without double counting.

The solution is supposed to be $n (n-1) (n-2)$ if I have not mis-phrased the question.

• You should write $( \{1,2 \}, \{2,3 \} )$ instead of $\{ \{1,2 \}, \{2,3 \} \}$.
– Aqua
Apr 4 '18 at 19:57
• @ChristianF Oh how dumb of me, of course I can't write what I did. Apr 4 '18 at 20:23

We need to make an ordered selection of two two-element subsets of $\{1, 2, 3, \ldots, n\}$ that share a single element. There are $\binom{n}{2}$ two-element subsets which we could place in the first entry in the ordered pair. For each such choice, there are $2$ ways to choose which element of the subset will also appear in the two-element subset that appears in the second entry and $n - 2$ ways to choose the other element of that subset, as it must be different from both elements of the subset that appears in the first entry. Hence, there are $$\binom{n}{2} \cdot 2(n - 2) = \frac{n!}{2!(n - 2)!} \cdot 2(n - 2) = \frac{n(n - 1)}{2} \cdot 2 \cdot (n - 2) = n(n - 1)(n - 2)$$ ways to select ordered pairs of two-element subsets that share a single element.