# Split a number into parts

In how many ways can a natural number $n$ be split into $m$ natural numbers (parts) where each part is less than $n$, the parts don't necessarily have to be equal, and all of them add up to $n$?

• Does order matter? Are $2+2+3$ and $2+3+2$ different splittings of $7$ into $3$ parts? – André Nicolas May 31 '15 at 16:22
• If the order matters, as @AndréNicolas mentioned, then the problem is pretty simple. Otherwise, this problem is extremely non-trivial, and there are entire books devoted to the subject. – eloiprime May 31 '15 at 16:30
• Also, are parts positive integers, or will zero parts be allowed? – hardmath May 31 '15 at 20:14
• Yes the order matters and zero is also allowed but the sum of all m numbers should be n, and no repititions allowed, ex 7 cannot have more than one of 2+2+3. Also @eloiPrime could you tell me what that particular non-trivial problem is called. – lapin Jun 1 '15 at 10:54
• I apologise for not being able to explain properly. For example in case of 7, one of the ways can be (2,2,3) the parts can be equal so here we have 2 parts with 2 but it cannot have another (2,2,3). It can and must have permutations of (2,2,3). – lapin Jun 1 '15 at 13:27

This is the "stars and bars" problem: $n$ stars, $m-1$ bars, so $\binom{n+m-1}n$ ways to split $n$ up into $m$ parts.
• It'd be hard to improve on the article about stars and bars in Wikipedia (link below in hardmath's post). In a nutshell, you think of $n$ as stars and the $m$ parts divided by $m-1$ bars. Then, there's a one-to-one correspondence between the partitions and the combinations. – Rus May Jun 2 '15 at 21:20
When summands are allowed to be zero, these are known as weak compositions of integer $n$ having $m$ parts.
The expressions where we are required to discount summations that differ only in regard to the order of otherwise the same summands are called partitions of integer $n$ having at most $m$ parts. For these there are no simple binomial coefficient counting formulas, although work by Ramanujan and others led eventually to a "closed form" of sorts. Therefore the counting of integer partitions is more difficult than of integer compositions, despite the overall similarity of problems.