5
$\begingroup$

If you want to divide a team of 10 people into teams A, B, and C of sizes 3,5, and 2, how many divisions are possible?

If you want to divide them into just teams of sizes 3,5, and 2, how many arrangements are possible?

I know that you use multinomial coefficients such that for part 1, the number of divisions is 10!/(3!5!2!) and for part 2, the number of divisions is 10!/(3!5!2!)/2!. I don't know why this is the case intuitively. Also, I can understand the formula for combinations as (n choose k) = (n*n-1*..n-k+1)/(k!) more clearly than (n!)/(k!)(n-k)!. I can't seem to interpret the second form of of the formula for combinations(or multinomials).

  • 0
    How can the same question have different answers? (It is true that $3-4-3$ has different shape than $3-5-2$.)2011-09-26

2 Answers 2

4

Think about it as if you have $n$ unique items that you want to divide between $m$ bins/groups of people/etc. - each size $k_1,k_2,\cdots,k_m$. Obviously the first gets $k_1$ items in $\binom{n}{k_1}$ number of ways. Obviously, the second one has to select from ($n-k_1$) items, which is $\binom{n-k_1}{k_2}$ and so on. Now take the product of these binomial coefficients and cancel out some terms to obtain $\binom{n}{k_1 k_2 \cdots k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$

2

You have $n$ objects that you want to partition into groups of sizes $k_1$, $k_2$, $\ldots$, $k_m$. You already know that there are $n!$ permutations of these objects, ie $n!$ ways to order them, ie $n!$ to enumerate them.

Given of permutation of these objects, say the first $k_1$ objects will be put in the first group, the following $k_2$ in the second, and so on. In order not to count two equivalent partitions, you need to divide by the number of permutations of the objects in each group.

Simply put, the number of partitions is the number of permutations of all the objects divided by the number of permutations that will give the same partition, and this number is the products of the number of permutations of each group: ${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$