How do I calculate the number of ways I can make up number a from the numbers b and c, with n additions of b and/or c?

Question

Say I have a number a: How do I calculate the number of ways I can make up number a from the numbers b and c, with of n additions of b and/or c?

For example: a = 4, b = 1, c = 2, n = 3

If I write it out I get the following valid solutions

1 + 1 + 2
1 + 2 + 1
2 + 1 + 1

These are however not valid solutions

1 + 1 + 1 + 1 
2 + 2

So the answer for these a, b, c and n should equal 3

Now it's very easy to calculate this manually, but I need a formula for it because I need this outcome in Excel for varying parameters.

Answer 1

If $b=c$ there is either a unique solution, or none.

Now note that even if $b \neq c$, $kb + (n-k)c$ is a different number for each value of $k$, so if for a given $a$ and $n$ there is a solution $k$, it is unique.

Then all you are doing is permuting the summands, so you are counting permutations, which (since you have $k$ and $n-k$ identical elements in the sum) add up to the binomial coefficient $${n \choose k} = \frac{n!}{k!(n-k)!}$$

Answer 2

@AnalysisStudent0414,has shown how many solutions there are, providing such solutions exist at all. To determine when this is the case we can prove the following result.

Let $a,b\le c$ and $n$ be positive integers and let the result of applying the Euclidean Algorithm to find the greatest common divisor, $g$, of $b$ and $c$ be $$g=\lambda b+\mu c,$$ for integers $\lambda$ and $\mu$. Then $a$ can be formed by $n$ additions of $b$ and/or $c$ if and only if

(i)$ \,\,\,\,\,a\le nc$

(ii)$ \,\,\, g$ is a factor of $a$

(iii) $c-b$ is a factor of $ng-a(\lambda +\mu)$

For $a$ to be formed by $n$ additions of $b$ and/or $c\ge b$ the first two conditions are obviously necessary.

Let $a=rb+(n-r)c$ and let $a',b',c'$ denote $\frac{a}{g},\frac{b}{g},\frac{c}{g}$. Then $$rb'+(n-r)c'=a'(\lambda b'+\mu c')$$ $$(r-\lambda a')b'=(a'\mu+r-n)c'.$$ Now $b'$ and $c'$ are coprime and so there is an integer $t$ such that $r-\lambda a'=tc'$ and $a'\mu+r-n=tb'$.

Then $t(c'-b')=n-a'(\lambda +\mu)$ and $c-b$ is a factor of $ng-a(\lambda +\mu)$.

Conversely, suppose all three conditions are satisfied. Then $a=rb+sc$ for integers $r=\lambda a'$ and $s=\mu a'$.

Condition (iii) says that $c-b$ is a factor of $g(n-(r+s))$. Let $n=r+s+t(c'-b')$ for some integer $t$. Then $$a=(r+tc')b+(s-tb')c$$ where the multiples of $b$ and $c$ are now non-negative and add to $n$.