4
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.