# How many ways can 2m objects be paired and assigned to m boxes?

In that post the questioner claims that there are $\frac{(2m)!}{2^m}$ to pair $2m$ and assign them to $m$ boxes.

My attempt :-

First we need to find number of ways to pair $2m$ objects.

That is $\frac{(2m)!}{2! * (2m-2)!}$ = $\frac{2m * (2m - 1)}{2}$ = $m * (2m - 1)$

After pairing there are $m$ objects left, and there are $m!$ to permute them in $m$ boxes

Thus the answer should be $m! * m * (2m -1)$ ways.

Which is wrong. what i am doing incorrectly, please anyone correct me.

• The right answer is $\frac{(2m)!}{2^m}$, not $\frac{2m!}{2^m}$. Apart from that, though, how on earth do you get $\frac{2m!}{2!(2m-2)!}$? That seems to be neither here nor there. With $(2m)!$ in the numerator it would have been the number of ways to pick one unordered pair from among the $2m$ original, ones, but you seem to pretend it's the number to divide them into $m$ unordered pairs. – Henning Makholm May 28 '16 at 23:48
• The ratio $(2m)! / (2! (2m-2)!) = {{2m} \choose 2}$ is the number of ways to choose 2 elements from $2m$ elements for the first box. You need to find the number of ways for the remaining boxes also, and then multiply these numbers to get the total number of ways. – svsring May 29 '16 at 5:32

Line up the $m$ boxes in some order from left to right. We choose two of the $2m$ objects to place in the first box, choose two of the remaining $2m - 2$ boxes in the second box, choose two of the remaining $2m - 4$ boxes in the third box, and so forth until we place the final two objects in the $m$th box. We can do this in \begin{align*} \binom{2m}{2}&\binom{2m - 2}{2}\binom{2m - 4}{2} \cdots \binom{2}{2}\\ & = \frac{(2m)!}{2!(2m - 2)!} \cdot \frac{(2m - 2)!}{2!(2m - 4)!} \cdot \frac{(2m - 4)!}{2!(2m - 6)!} \cdots \frac{2!}{2!0!}\\ & = \frac{(2m)!}{2^m} \end{align*} ways.

The number $\binom{2m}{2}$ is the number of ways to choose a particular pair of the $2m$ objects to place in a box. It is not the number of ways to pair the objects. To do that, we can line up the objects in a row. There are $2m - 1$ ways we can choose an object to pair with the first object in line. This leaves us with $2m - 2$ unpaired objects. We have $2m - 3$ ways to choose an object to pair with the first unpaired object remaining in the line. This leaves us with $2m - 4$ unpaired objects. We have $2m - 5$ ways to choose an object to pair with the first unpaired object remaining in the line. Continuing in this way, we obtain $$(2m - 1)(2m - 3)(2m - 5) \cdots 1$$ ways of placing the $2m$ objects in $m$ pairs.

Multiplying the expression for the number of pairs by $m!$ yields \begin{align*} (2m - 1)&(2m - 3)(2m - 5) \cdots 1 \cdot m!\\ & = (2m - 1)(2m - 3)(2m - 5) \cdots 1 \cdot m! \cdot \frac{2^m}{2^m}\\ & = (2m - 1)(2m - 3)(2m - 5) \cdots 1 \cdot \frac{(2m)(2m - 2)(2m - 4) \cdots 2}{2^m}\\ & = \frac{(2m)!}{2^m} \end{align*}
which is the number of ways of placing the pairs in $m$ boxes.

• Thanks. What i was trying to do is pick a pair and put it in one of the box. – A---B May 29 '16 at 4:44

The number of ways that $2m$ objects can be grouped into $m$ boxes where each box contains 2 objects is:

$$\binom{2m}{2_{b1}, 2_{b2} ... 2_{bm}} = \frac{(2m)!}{2_{b1}!2_{b2}! ... 2_{bm}!} = \frac{(2m)!}{2^m}$$

where $b1$ is the first box, and $bm$ is the last box.

• That should be $(2m)!$ in the numerator, not $2m!$. (And it is pretty clear that the OP already knows that -- the question is not "what is the right count", but "what is the wrong thing in this calculation"). – Henning Makholm May 28 '16 at 23:45
• @HenningMakholm Sorry, missed the brackets. I disagree though, OP was making an attempt at coming up with the $\frac{(2m)!}{2^m}$, and one way to help OP with regards to what is wrong with his calculation is by providing the "right count". Also, the missing brackets is a visual mistake as from the answer you can already see he is aware that it is $(2m)!$. – Moataz Elmasry May 28 '16 at 23:55

The wrong point in your think is that the number of ways to paired $2m$ objects is not $\frac{(2m)!}{2!(m-2)!}$, this number is for chose a pair of $2m$ objects.

In fact, the number of ways to paired $2m$ objects is: Put all $2m$ on a row, that is $(2m)!$ ways. Now, each 2 objects, makes a pair, but how the order of the pairs doesn't mater we divided by $m!$ (because we have $m$ pairs). But the order of the objects in each pair doesn't mater, so we divided by 2 in each pair.

The final number is: $\frac{(2m)!}{m!2^m}$.