What is wrong with this derivation?

55 Views Asked by At

There are $n$ distinct sets, and each sets has many similar objects. I have to choose $r$ objects from these sets. Any number (including all $r$) of objects can be picked up from any set. My solution goes like this:

  1. Take $r$ objects from each of the $n$ sets and put them together. So now we have a set with $nr$ objects with $r$ objects of each kind.

  2. Choose $r$ objects from this set. This can be done in $\dfrac{{}^{nr}C_r}{(r!)^n}$ ways. The denominator is there to make for the equivalence of $n$ sets of $r$ objects.

This derivation is wrong as can be verified with a small example. According to a book the correct answer is ${}^{n+r-1}C_r$. This formula gives the correct answer.

What is wrong with this derivation and how can the correct answer be derived?

1

There are 1 best solutions below

2
On BEST ANSWER

What is wrong is your symmetry factor. You should only divide by the factorial of the objects used which is a varying number.

One way to obtain the correct answer is to place the $r$ objects in a line and then distribute $n-1$ separators between them. Objects between two separators will then come from the same set. It remains to count the ways to mix $r$ objects and $n-1$ separators which is the binomial coefficient.