So my thoughts are ${10 \choose 2} * {8 \choose 2} * {6 \choose 2} * {4 \choose 2}$

if the first person , has 9 choices

9 x 7 x 5 x 3 x 1. does this work ? cause i cant really make a logical thought about overlapping in chooses

  • 4
    $\begingroup$ You're overcounting. Divide your quantity by... $\endgroup$ – David Mitra Oct 19 '13 at 21:33

Just tell your $10$ people to line up such that the first person and the second person make up the first pair, the third and fourth make up the second pair, etcetera. This gives $10!$ pairings.

However, if the first person would swap places with the second person, the pairing would be no different, though we counted it as another pairing! In fact, each pair can have its members swap places while preserving the pairings, so we counted each pairing $2^5$ times. So, that's what we have to divide by.

We're not finished yet, though: what if the first two people swap places with the third and fourth? It would once again preserve the pairings, though we counted it as a different pairing. In fact, the $5$ pairs can swap places with each other all they want, the same pairings would still be preserved. Hence we counted each pairing $5!$ times, and that's what we have to divide by as well.

In conclusion, there are $$\frac{10!}{2^5 \cdot 5!} = 945$$ pairings.


Isn't the double factorial (2m-1)!! the direct answer to this? For 2m people?

Basically, each person has 9 different other persons to choose from, and after that happens, the next pair's person has 7 other people to choose from (10 minus the first pair and himself) all the way down to the last person, that has only 1 other person to choose from.

so you have 9 * 7 * 5 * 3 * 1 = (9)!! = 945


For future reference here is an approach using combinatorial species. We treat the general case of $2m$ people and $m$ pairs. The species $\mathcal{Q}$ that we want to enumerate (using exponential generating functions) has the specification $$\mathcal{Q} = \mathfrak{P}_m(\mathcal{P}(\mathcal{Z}))$$ where $\mathcal{P}$ is the species of pairs.

But we have $$\mathcal{P}(\mathcal{Z}) = \mathfrak{P}_2(\mathcal{Z}).$$ Therefore the generating function $Q(z)$ of $\mathcal{Q}$ is given by $$Q(z) = \frac{1}{m!} \left(\frac{1}{2!} z^2\right)^m.$$ The number of pairings is $(2m)!$ times the coefficient of $z^{2m}$ of this generating function, giving $$ (2m)! [z^{2m}] \frac{1}{2^m\times m!} z^{2m} = \frac{(2m)!}{2^m\times m!}.$$

This gives the following sequence of values: $$1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075,\ldots$$ In particular we get for ten people that there are $945$ arrangements (fifth term in the sequence with $m=5$ and five pairs for 10 people in total).

This is one of the more popular sequences from the OEIS, where we find this extensive OEIS entry.


Hint: for the first two pairs, you are counting AB+CD and CD+AB as different. Shouldn't they be the same? How does this extend?

Added: Your first thought was better. There are indeed $_{10}C_2$ ways to form the first pair. The problem is that some of the other ways to make pairs will make that same pair later. For your second thought, if you pick somebody to pair, they will have $9$ choices, but you could have made that pair in the other order.

  • $\begingroup$ On your second thought (which I think is a good approach): If you always start by picking somebody to pair with the first person (in alphabetical order of names, say), you run no risk of ever making the same pair in the other order. $\endgroup$ – Steve Kass Oct 19 '13 at 21:55
  • $\begingroup$ after 10c2 , im left with 8 people . how does overlapping occurs when the two people have been removed? $\endgroup$ – cindy Oct 19 '13 at 21:59
  • $\begingroup$ Let the people be A through J. One pairing would be AB,CD,EF,GH,IJ Another would be CD,AB,GH,EF,IJ This is the same set of five pairs. How many ways would you count this pairing? $\endgroup$ – Ross Millikan Oct 19 '13 at 22:04

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.