choosing two pairs from a set such that the pairs are not the same thing

259 Views Asked by At

Given a set $A=\left\{1,2,3,4,5\right\}$, how many ways are there to choose a subset of size $4$ of this set and then choose two pairs of numbers from the subset such that there does not exist two pairs with the same element?

I think the number of choosing such subsets is $\binom{5}{4}$ , but how we can pick those two pairs such that they are not the same thing?

1

There are 1 best solutions below

8
On

If you want to label the pairs as "the first pair" and "the second pair" and order within the pairs themselves doesn't matter... then this is effectively going to be the same as arranging the letters of the word FFSSN, where an F in a spot corresponds to the corresponding number for the index appearing in the first pair, an S corresponds to the corresponding number being in the second pair, and the N for the corresponding number appearing in neither.

To count, you can use this interpretation and use multinomial coefficients to jump to the answer of $\binom{5}{2,2,1}=\frac{5!}{2!2!1!}$

Alternatively, you can do the same by first choosing the four elements for the 4-element subset, then choosing two of the elements from those chosen to form the "first" 2-element subset, leaving the remaining two to form the second, giving a total of $\binom{5}{4}\times\binom{4}{2}$, which you will find is equal to what we had before.


Now... if instead you don't care which pair was "first", you could make a division by symmetry argument, and say that of the arrangements described above, we doublecounted everything... once when a particular pair was the "first" pair and another the "second" pair, and again when those labels were reversed. Dividing by two will correct the count.

If you want to avoid division by symmetry arguments, then instead begin as we had by first choosing which four elements are in the 4-element subset. Then... among those elements, whatever they happened to be, one of them will happen to be the "smallest." Choose what other element will be paired with it. The remaining elements will form the other pair.

This gives a total of $\binom{5}{4}\times 3$, which you will see is equal to half of the answer from the first interpretation.