Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.