2
$\begingroup$

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

  • 0
    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.2011-04-28

2 Answers 2

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.

0

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.

  • 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 ( http://en.wikipedia.org/wiki/Ferrers_diagram#Ferrers_diagram ).2011-04-29