0
$\begingroup$

I was solving the following problem, "Given a collection of 10 identical objects calculate the number of ways in which these objects can be partitioned into 2 groups of 6 and 4 objects each" - for this I calculate the answer as $\binom{10}{6}$ or $\binom{10}{4}$ and this answer turns out to be correct, but the next question asked to calculate the number of ways to partition into 2 groups of 5 each for which the answer is $\binom{10}{5}/2$, but I am not able to understand why is this the case?

Also can some explain such problems generally i.e taking the case of partitioning n identical objects into r different group equally that is when $n = k*r$. How do you solve such a problem?

$\endgroup$
  • 2
    $\begingroup$ I don't understand the significance of the word "identical" in the question. The number of ways you can partition a collection of $10$ different objects into a group of $6$ and a group of $4$ is $\binom{10}6=\binom{10}4=210$. For a collection of $10$ identical objects, why isn't the answer just $1$? If the objects are identical, what makes one partition different from another? $\endgroup$ – bof Sep 22 '14 at 23:01
1
$\begingroup$

Try this much smaller example: partition a set of $2$ items into two sets of $1$ item each.

The number of ways to choose the contents of the first subset is $\binom{2}{1} = 2.$ But in fact there is only one way to partition the set into two subsets of one item each: each item goes in its own subset.

The difference is that if one subset has six items and the other has four, then no partition that puts the first item into the subset of six can be the same as any partition that puts that same item into the subset of four. But if the subsets are of equal size, we can put the first item into either subset and still finish with the same partition; there is nothing to distinguish the two subsets except which items are in them.

$\endgroup$
1
$\begingroup$

The division by $2$ is due to the fact that since $\binom{10}{5}$ counts the number of subsets $A$ with $5$ elements from a base set $B$ with $10$ elements, so it defines the partition $B\simeq(A,A^c)$. On the other hand this partition is also found via $A^c$ since $(A^c,(A^c)^c)=(A^c,A)$ so each partitioning is counted twice.


Regarding the general case of partitioning $n=k\cdot r$ objects into $r$ groups of size $k$, that contains more details. One way to do it is to:

  1. line up a random permutation of the $n$ objects (this gives $n!$)
  2. divide it into $r$ parts in the given order
  3. divide by the number of ways to permute within each group (this gives $(k!)^r$ to divide by)
  4. divide by the number of ways to have essentially identical setups where the groups have just been permuted (this gives $r!$ to divide by)

So we have a figure that is $$ G(n,r,k)=\frac{n!}{(k!)^r r!}=\binom{n}{\underbrace{k,k,...,k}_{r\text{ times}}}/r! $$ The notation given in the last part uses the so-called multinomial coefficients which for $r=2$ becomes a binomial coefficient. In particular we have $$ G(10,2,5)=\frac{10!}{(5!)^2 2!}=\binom{10}{5}/2 $$

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