19
$\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$
1
  • 3
    $\begingroup$ In your example you did not count the possibilities $0|0|10$ and $0|10|0$ and $10|0|0$. So there are $66$ possibilities. This agrees with stars and bars since $\binom{10+2}2=66$. $\endgroup$
    – Vera
    Commented May 11, 2022 at 8:58

3 Answers 3

Reset to default
38
$\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$ "|" (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?

$\endgroup$
2
  • 1
    $\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
    Commented Dec 21, 2017 at 2:41
  • 1
    $\begingroup$ @0TTT0 Integer solutions are essentially the problem of distributing identical units into distinct boxes, and these are well-studied. Some constraints have closed solutions (lower bounds can be solved easily, upper bounds can be solved with inclusion/exclusion), while other seemingly similar constraints have no closed solutions, and are best solved with generating functions (or numerically). $\endgroup$
    – While I Am
    Commented Jan 25, 2021 at 17:13
5
$\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$
4
  • 1
    $\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
    Commented Jul 16, 2018 at 16:29
  • 1
    $\begingroup$ Do you like Latex? Also we. :-) Just type $5 \cdot 5$ and you get $5 \cdot 5$. Welcome on the MathSE! :-) $\endgroup$
    – peterh
    Commented Jul 17, 2018 at 21:21
  • 2
    $\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
    Commented Jul 18, 2018 at 14:07
  • $\begingroup$ @ValeriiSalov, Where can I find the proof? $\endgroup$
    – DSPinfinity
    Commented Jan 14 at 21:44
2
$\begingroup$

The answers above are incorrect, because they count the same numbers in different sequence as distinct combinations of numbers. In the above example, the given combination is 0+2+4+1+3, but 2+0+4+1+3 is counted as a distinct combination even though it is not. In total, 5! permutations of those numbers will be counted as distinct combinations.

However, dividing the result by 5! does not yield the right answer either.

$\endgroup$
1
  • 1
    $\begingroup$ From the example given by the OP in the question we may conclude that order matters. $\endgroup$
    – Vera
    Commented May 11, 2022 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .