Prove that taking $2$ pairs from set of pairs of elements of $[n]$ is given by: $3 \times \binom{n+1}{4}$.

55 Views Asked by At

I am modifying the problem from an mse post at: Verify that $\binom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$ for $n \geq 4$. I hope the modification keeps the problem intact.
The real issue is the inability to understand the selected answer there.


For the case of taking $2$ pairs from the set of possible pairs of element from a set of $n$ elements, have two options.
First option is to get overlapping pairs, while the second option is to get disjoint pairs.
Given a small set with $n=4 = \{A,B,C,D\}$; both options draw from the possible set of members: $AB, AC, AD, BC, BD, CD$.
The options for the overlapping pairs are:
1. $AB,BC$
2. $AB,BD$
3. $AB,AC$
4. $AB,AD$
5. $AC,CD$
6. $AC,BC$
7. $AC,AD$
8. $AD,BD$
9. $AD,CD$
10. $BC,BD$
11. $BC,CD$
12. $CD,BD$
But, the disjoint case has $3$ options :
a. $AB,CD$
b. $AC,BD$
c. $AD,BC$

I want to know how the above division in each of the two cases, for general case or for my small example is given by $3 \times \binom{n+1}{4}$.

1

There are 1 best solutions below

6
On BEST ANSWER

We want to pick $4$ elements from a total of $n+1$ elements.

We keep the first element ,$f$, apart and focus on the other $n$ elements. Call the set of $n$ elements $S$.

We consider the set of all pairs of elements in $S$, call it $P$. We can choose two pairs from $P$, call them $\{A, B\}$ and $\{C, D\}$.

The first case is if $\{A, B\}$ and $\{C, D\}$ overlaps, in that case, we pick the first element that was separated initially, $f$, as one of the $4$ elements that are chosen as well.

The second case is if $\{A, B\}$ and $\{C,D\}$ do not overlap, in that case, we do not pick the first element.

By using this procedure, we could have chosen $4$ elements from $n+1$ elements. However, we have counted elements multiple times and we have to consider that.

In the first case if we have chosen $\{f,e_1,e_2,e_3\}$. It is equally likely that the repeated element is $e_i$ where $i=1,2,3$.

In the second case, if we have selected $\{e_1,e_2, e_3, e_4\}$, $e_4$ is equally likely to have been paired with $e_i$ where $i=1,2,3$.

Hence $$\binom{n+1}4=\frac13 \binom{\binom{n}2}{2}$$

for $n \ge 4$.