Number of possible combinations of x numbers that sum to y

100.1k Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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$ "|" (bars) 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 "|" bars represents a solution the total number of solutions is given by the possible permutations of this $14$ symbols, that is $\frac{14!}{10!4!}$.

This method, actually 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?