# Find the number of combinations such that sum of N numbers equals to M [duplicate]

Here is the problem:

Let M (the sum) be 10 and N (the number of numbers) be 4.

Some possible combinations are are (10, 0, 0, 0), (5, 3, 2, 0), (8, 1, 1, 0), (8, 2, 0, 0), (6, 2, 1, 1), etc.

How do I calculate the number of possible combinations?

Thanks for the help.

## marked as duplicate by Claude Leibovici, user91500, Shailesh, RGS, John BNov 23 '16 at 10:49

• Do you know what partitions are? – Saketh Malyala Nov 23 '16 at 1:15
• This is a standard application of a stars-and-bars computation. – hardmath Nov 23 '16 at 1:24
• Just had a quick read about it from: en.wikipedia.org/wiki/…, but I am unsure how to apply the formula – paperpin Nov 23 '16 at 1:25
• The link I gave you is to a previous Question at Math.SE about how to apply its logic. – hardmath Nov 23 '16 at 1:26
• @SakethMalyala: You ask about (integer) partitions, in which the order of summands is ignored, but I have interpreted the problem as concerning compositions, in which order of summands matters. We may get some clarification from the OP. – hardmath Nov 23 '16 at 1:36

As covered in the previous Question as well as the Wikipedia article, the number of such summations (order is important, so weak compositions rather than partitions) is $\binom{M+N-1}{N-1}$.
The example $M=10$ and $N=4$ of the OP then yields $\binom{13}{3} = 286$.
If instead we wanted to disregard order of summands, this is an overcount (since $6 + 1 + 1 + 0 = 0 + 1 + 1 + 6$, etc.). The number of integer partitions of $10$ with at most $4$ parts (zeros omitted, or padded out with zeros to give exactly four summands) is only $23$.
length(integer_partitions(10,4));