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.

I know that if $n$ is a positive integer and $n_1,n_2,...n_k$ are positive integers such that $n=n_1+n_2+...+n_k$. Then the number of ways to partition $n$ objects into k boxes is:

If $n_1=n_2=....=n_k$ and the boxes are unlabeled, then it is equal to $\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}$

But what if $n_j$'s are not necessarily the same? I could not find a formula for that. Can you give me a hand?

share|improve this question
1  
Exactly the formula you give, it doesn't depend on the $n_i$s being the same. –  vonbrand Feb 26 '13 at 2:18
    
If the boxes are unlabeled, what (if anything) do the summands $n_i$ have to do with the boxes? Also you need to specify whether the objects are distinguishable (assuming the boxes are not distinguishable in your problem). –  hardmath Feb 26 '13 at 4:47

1 Answer 1

up vote 2 down vote accepted

I’m assuming that the $n$ objects are distinguishable and that $n_1,\dots,n_k$ are the specified sizes of the pieces of the partition. The number of such partitions is

$$\frac{n!}{n_1!n_2!\dots n_k!}$$

regardless of whether the $n_i$’s are the same or different. This number is a multinomial coefficient, a generalization of the more familiar binomial coefficient; it can be written

$$\binom{n}{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\dots n_k!}\;.$$

share|improve this answer
    
The one thorn is where the OP says "the boxes are unlabeled", which seems more or less to ask for partitions having specified sizes rather than (ordered) selections (mappings to $k$ labelled boxes) with the specified sizes. However as OP asserts the multinomial gives the right answer for equal summands $n_i$, the natural extension is worth stating (as also @vonbrand commented). –  hardmath Feb 26 '13 at 16:05

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.