5
$\begingroup$

In 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm May 28 '16 at 23:48
  • $\begingroup$ 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. $\endgroup$ – svsring May 29 '16 at 5:32
1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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"). $\endgroup$ – Henning Makholm May 28 '16 at 23:45
  • $\begingroup$ @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)!$. $\endgroup$ – Moataz Elmasry May 28 '16 at 23:55
0
$\begingroup$

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}$.

$\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.