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.

How many ways can one divide $n-m$ into parts of at most size $m$?

The only way I've thought of doing this is by summing up all the ways from parts of size $1$ to size $m$. The problem is that I don't know the size of $m$ relative to $n$.

share|improve this question
6  
I tried to fix the misleading word "partitions" and got: "Edits must be at least 6 characters; is there something else to improve in this post?" Whose idea is that "feature"??? –  Phira Apr 28 '11 at 17:36
    
missou: This question is a bit cryptic. Can you explicitly list the ways of dividing $n-m$ into (something) of at most size $m$ for some small numbers $n$ and $m$, so that we have a better idea of what you mean? –  Michael Lugo Apr 28 '11 at 19:47
    
I agree with Michael Lugo. Your question isn't clear. Are we looking at dividing distinguishable objects into groups? or are we looking at integer partitions with added constraints on the size of the partition? –  svenkatr Apr 28 '11 at 21:35
    
Please give an example with small $n$ and $m$, so that we can tell whether you want to take the order of the parts into account. –  Phira Apr 28 '11 at 21:40

2 Answers 2

The number of partitions of $n-m$ into parts of size at most $m$ is the coefficient of $x^{n-m}$ in $$\frac{1}{(1-x)(1-x^2)\dots(1-x^m)}.$$

Depending on the application, one might prefer a recursive definition which can be derived from the above expression.

For the application mentioned in the other answer, however, it is best to use Ferrers diagrams as mentioned in the comment to the other answer.

share|improve this answer

The original question is actually from number theory: show that the number of partitions of n into exactly m parts is equal to the number of partitions of n-m into parts of size at most m. So I guess the order does not matter.

share|improve this answer
3  
I would encourage editing your post to reflect the question you're really wondering about - showing that two things are the same is different from counting either of them. In this case, there's an easy correspondence through the Ferrers diagram ( en.wikipedia.org/wiki/Ferrers_diagram#Ferrers_diagram ). –  Steven Stadnicki Apr 29 '11 at 0:20

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.