5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Does order matter? Are $2+2+3$ and $2+3+2$ different splittings of $7$ into $3$ parts? $\endgroup$ – André Nicolas May 31 '15 at 16:22
  • 2
    $\begingroup$ 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. $\endgroup$ – eloiprime May 31 '15 at 16:30
  • $\begingroup$ Also, are parts positive integers, or will zero parts be allowed? $\endgroup$ – hardmath May 31 '15 at 20:14
  • $\begingroup$ 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. $\endgroup$ – lapin Jun 1 '15 at 10:54
  • 1
    $\begingroup$ 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). $\endgroup$ – lapin Jun 1 '15 at 13:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you give an explanation ? The formula works but I don't know how. $\endgroup$ – lapin Jun 1 '15 at 13:29
  • $\begingroup$ 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. $\endgroup$ – Rus May Jun 2 '15 at 21:20
  • $\begingroup$ Thanks i got it, after reading william feller's book on probability. $\endgroup$ – lapin Jun 4 '15 at 8:27
3
$\begingroup$

When summands are allowed to be zero, these are known as weak compositions of integer $n$ having $m$ parts.

They are readily counted by the "stars-and-bars" technique, as Rus May indicated. This is a frequently-asked-question here.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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