Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Basically you ask how many total divisions are possible, and then you divide by how many times you counted each option. Say the team (123)(45678)(9,10) is the same as (132)(57648)(10,9). So you divide by the number of permutations of each group, which is $k!$ and $(n-k)!$ for the binomial case. –  TMM Sep 26 '11 at 1:39
    
How can the same question have different answers? (It is true that $3-4-3$ has different shape than $3-5-2$.) –  André Nicolas Sep 26 '11 at 4:34
add comment

2 Answers

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

share|improve this answer
add comment

Think about it as if you have $n$ unique items that you want to 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 among $n-k_1$ number of 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!}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.