# How many ways to add to $50$ with $1, 4$ and $6$

So I get how to find the number of ways of getting a number with $2$ sets of numbers (ex: using $1$s and $2$s to get $10$). But I have no clue where to start to figure out how many ways to get a number using $3$ sets of numbers:

How many ways can you add to $50$ by using $1$s, $4$s, and $6$s?

Order matters and they count as a way ($1+4$ and $4+1$ is $2$ ways), but all $1$s or all $2$s in different orders count as one way ($1+1$ and $1+1$ is $1$ way).

Is there like a formula that I could use to figure this out? Thanks.

I tried using brute force with 2 numbers and found a pattern where the next number of ways = number of ways now + previous number of ways. But using brute force with 3 numbers I'm cant seem to find a pattern.

• It would be good if you show us how you do it with sets of 2 numbers. Probably, there is a way to reuse this technique.
– Surb
Mar 13, 2018 at 20:45
• I tried using brute force with 2 numbers and found a pattern where the next number of ways = number of ways now + previous number of ways. But using brute force with 3 numbers I'm cant seem to find a pattern. Mar 13, 2018 at 20:49
• And also I can't find a formula for the 2 ways (I tried), I kinda have to brute force, which I dont want. Mar 13, 2018 at 20:50
• Hey think about the 2-case. it’s divide and conquer to get all partitions, and then it’s combinatorics to get all the partitions counting order. And indeed as @surb said, it generalises (same method applies for 3 numbers), but it can be generalised using generating functions to any arbitrary sized set. I forget the details of the conditions on the set, but surb is right. Mar 13, 2018 at 20:51
• Assume you use 0 ones. How many ways can you make 50 out of sums of $6,4.$ Assume 1 one, can't do it, you must have an even number of ones. 2 ones, 4 ones, etc.. find a pattern, justify why the pattern holds. Mar 13, 2018 at 20:52

You can write a recurrence. You can get $50$ by getting $49$ and adding $1$, by getting $46$ and adding $4$, or by getting $44$ and adding $6$. If $A(n)$ is the number of ways to get $n$ you have $$A(n)=A(n-1)+A(n-4)+A(n-6)\\A(0)=1\\A(n)=0 \quad n \lt 0$$ Unfortunately, the polynomial that comes out of this, $x^6-x^5-x^2-1,$ cannot be factored easily except for the factor $x+1$ so you are into using numeric approximations for the roots.

Added: to do it with a calculator you make a column for $n$ with the numbers from $0$ to $50$ and a column for $A(n)$. Start from the top, putting $A(0)=1$ because there is one way to add to $0$-don't add anything. Then for each $n$ compute the sum of the lines $1, 4, \text {and} 6$ above. The result up to $n=20$ is shown below. For example, you get $A(9)=A(8)+A(5)+A(3)=10+3+1=14$ and keep going. The image is from Excel, where I could just copy the formula down.

• Adding also $50$ times $1$?. Is this valid? Mar 13, 2018 at 21:27
• I don't understand please. ($2^5\gt 2^4+2^2+1$ so the only real root of this polynomial is less than $2$). Regards. Mar 13, 2018 at 21:34
• @Piquito: Adding $50$ times $1$ is valid. It falls under the "get $49$ and add $1$" group. Yes, the only real root is about $1.57$ It is easy to program the recurrence in a spreadsheet. I get $A(50)=9266038$. If you could get the roots you could do a formula like Binet's for the Fibonacci numbers. $A(n)$ would be expressed as a sum of the $n^{th}$ powers of the roots times coefficients to match the initial conditions. Mar 13, 2018 at 21:40
• Thanks you, @Ross. So it is not necessary that $1,4$ and $6$ appeared simultaneously like $(6-1)(6+4)$? Mar 13, 2018 at 21:46
• @Piquito: I don't understand what you are getting at with the last. We are adding $1$s, $4$s, and $6$s. Where do products and subtraction come from? Your expression evaluates to $50$ but is not part of this problem. Mar 13, 2018 at 22:00

Hint:

Let $f(n)$ be the number of sums that evaluate to $n.$ So $f(5)=3$ because $$5=1+1+1+1+1=1+4=4+1$$

The sums that evaluate to $50$ can be splittet into $3$ groups

• the group of sums that starts with $1$
• the group of sums that starts with $4$
• the group of sums that starts with $6$

How can the size of these groups be expressed by $f$?

How can this be used to express $f(50)?$

Finally, calculate $f(50)$ but try to avoid to calculate values you have already calculated otherwise the number of calculations will explode.

• I have no clue where to start, i don't get this and I really need help. Can you show me how to get lets say 20 with 1,4,6. Maybe I could use the technique and find for 50 Mar 15, 2018 at 20:37