# Fixed sum of combinations

When you have combinations where numbers are $0,1,2,\dots,m$, meaning we have $n=m+1$ and $k$, is there a way to see how $k$ of them sum up to a given number?

For the sake of simplicity I have the numbers $0,1,2...,7$ (so $n=8$), and $k=3$. I need to find how much of these combinations with repetition sum up to $7$. By sum up, I mean the sum of all $3$ digits in each combination needs to be equal to $7$. Is there a formula for this?

-

## 2 Answers

In other words you ask for number of compositions of natural number $k$ into $m$ parts no greater than $s-1$ $${\binom{m}{k}}_{s}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+k-si-1}{m-1}\,$$ For $m=3,k=s-1=7$ we have $${\binom{3}{7}}_{8}=\sum_{i=0}^{8}(-1)^{i}\binom{3}{i}\binom{9-8i}{2}=\binom{3}{0}\binom{9}{2}-\binom{3}{1}\binom{1}{2}=36-0=36$$ we can write all of $$007,070,700$$ $$016,061,106,160,601,610$$ $$025,052,205,250,502,520$$ $$034,043,304,340,403,430$$ $$115,151,511$$ $$124,142,214,241,412,421$$ $$133,313,331$$ $$223,232,322$$

-
This is variations as I can see. Plus, shouldn't (5,1,1),(1,5,1),(1,1,5) be in there also? – Martin V Nov 29 '13 at 17:44
@Martin V. I edit my answer. – Adi Dani Nov 29 '13 at 19:24
One more question, is there a way to see the number of combinations of the above? Here it's 8 (number of rows), but is there a formula for this too? – Martin V Nov 30 '13 at 9:13

Write $m$ as $$\underbrace{1 + 1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m 1s}}$$ This isn't the only sum, however. Other possible sums are $$3 + 3 + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-6 1s}}$$ or $$2 + 1 + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-5 1s}} + 2$$ Notice, however, if we decompose all our non-unit integers into ones, they all end up as $$\underbrace{1 + 1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m 1s}}$$ In other words, we can represent $3 + 3 + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-6 1s}}$ as $$(1 + 1 + 1) + (1 + 1 + 1) + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-6 1s}}$$ and $2 + 1 + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-5 1s}} + 2$ as $$(1 + 1) + (1) + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-5 1s}} + (1 + 1)$$ Instead of using parenthesis, let us re-write this as $$1 + 1 \ \Big\vert \ + 1 \ \Big\vert + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-5 1s}} \ \Big\vert + 1 + 1$$ and re-write the other sum as $$1 + 1 + 1 \ \Big\vert + 1 + 1 + 1 \ \Big\vert + \underbrace{1 + 1 + 1 + 1 + \cdots + 1 + 1}_{\text{m-6 1s}}$$ Notice that every single sum can be represented with such "bar notation". For sums with zeroes, such as $3 + 0 + 2 + 5$, we could write $$1 + 1 + 1 \ \Big\vert \ \Big\vert + 1 + 1 \ \Big\vert + 1 + 1 + 1 + 1 + 1$$ (there are no ones in between the first two bars) and for sums such as $0 + 0 + 0 + 1 + 1 + 2 + 3$ we could do $$\ \Big\vert \ \Big\vert \ \Big\vert 1 \ \Big\vert + 1 \ \Big\vert + 1 + 1 \ \Big\vert + 1 + 1 + 1$$ as there is nothing to the left of the first divider, representing the first zero, nothing in between the first two dividers, and nothing in between the second and third dividers.

So suppose we have $k$ summands. This would require $k-1$ bars, just as $1 \ \Big\vert + 1 \ \Big\vert + 1$ requires two bars instead of three. There are $m$ ones, which must be arranged with the $k-1$ bars. Therefore, in total, there are $\dbinom{m + k - 1}{m}$ ways to do the arrangement.

-