7
$\begingroup$

I want to find out the number of possible combinations of $x$ numbers that sum to $y$. For example, I want to calculate all combination of 5 numbers, which their sum equals to 10.

An asymptotic approixmation is also useful. This question seems to be very close to number partitioning, with the difference that a number can be 0. See:

https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Asymptotics

All possible partitions for sum 10 and 3 positions that can be zero, are 63 possiblities: (numbers shown as 3 digits)

019 028 037 046 055 064 073 082 091 109 118 127 136 145 154 163 172 181 190 208 217 226 235 244 253 262 271 280 307 316 325 334 343 352 361 370 406 415 424 433 442 451 460 505 514 523 532 541 550 604 613 622 631 640 703 712 721 730 802 811 820 901 910

$\endgroup$
17
$\begingroup$

This problem is equivalent to finding the number of integer solutions to $a+b+c+d+e=10$.

If you imagine your $10$ as a line of $10$ stars then you can insert $4$ "+" signs in between the stars to get a solution, for example $+\star\star+\star\star\star\star+\star+\star\star\star$ represent the solution $0+2+4+1+3$.

Since every permutation of stars and "+" signs represents a solution the total number of solutions is given by the possible permutations of this $14$ symbols, that is $\frac{14!}{10!4!}$. The same method, which is usually called stars and bars can be used for similar problems with other numbers involved.

Edit: in the case of $3$ numbers adding up to $10$ stars and bars gives $\frac{12!}{10!2!}=66$ as answer, you have $63$ because you didn't count the $3$ triplets with $2$ zeros and a ten, was that intended?

$\endgroup$
  • $\begingroup$ Seems correct to me. Thanks. $\endgroup$ – Ho1 Oct 3 '15 at 8:15
  • $\begingroup$ is there a way to do this when the numbers being added are between two values, say 1-26.. for example, how many ways can 7 numbers being between 1 and 26 inclusive add up to 55 $\endgroup$ – 0TTT0 Dec 21 '17 at 2:41
2
$\begingroup$

The answer from Alessandro Codenotti about 66 and three extra $(0,0,10), (0,10,0), (10,0,0)$ is correct. In general, let $n$ is a positive integer to partition, $k$ is the number of non-negative parts (zeros are included), the order of parts matters. Then, the total number of decompositions is the binomial coefficient $C(n+k-1,k-1)=\frac{(n+k-1)!}{(k-1)!n!}$.

This result is well known. For $n=10$, $k=3$, $C(10+3-1,3-1)=\frac{12!}{2!10!}=\frac{11\cdot 12}{2}=66$. For $n=10$, $k=5$, $C(10+5-1,5-1)=\frac{14!}{4!10!}=\frac{11 \cdot 12 \cdot 13 \cdot 14}{2 \cdot 3 \cdot 4}=77 \cdot 13=1001$. In both cases, one decides, if $k$ must be subtracted from the result to remove $k$ decompositions, where $n$ itself is in one of $k$ positions and accompanied by $k - 1$ zeros.

$\endgroup$
  • $\begingroup$ Just in case. Alessandro's reasoning is good. Another way to get confidence in the answer is to view the positive integer n as n indistinguishable balls, which supposed to be placed into k distinguishable boxes so that some boxes can remain empty. By "well known", I mean, for instance, Riordan, John. An Introduction to Combinatorial Analysis. Princeton, New Jersey: Princeton University Press, 1978. pp. 92 - 94, Section 3. Like Objects and Unlike Cells. Best Regards, Valerii Salov $\endgroup$ – Valerii Salov Jul 16 '18 at 16:29
  • $\begingroup$ Do you like Latex? Also we. :-) Just type $5 \cdot 5$ and you get $5 \cdot 5$. Welcome on the MathSE! :-) $\endgroup$ – peterh - Reinstate Monica Jul 17 '18 at 21:21
  • $\begingroup$ Hi 'peterh'. Thank you for pointing that Latex is accepted and for the trick with multiplication. Yes, I do use Latex and will apply it on messages for this nice site. Best Regards, Valerii $\endgroup$ – Valerii Salov Jul 18 '18 at 14:07
0
$\begingroup$

if there is a range like the example given by @OTTTO in comments then you can simply use the stars and bar method and for range purpose you can make a cluster of those starts before or after the range. in other words just apply bars in range and outside range make a cluster of stars.

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