3
$\begingroup$

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.

From the comments:

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.

$\endgroup$
9
  • 3
    $\begingroup$ 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. $\endgroup$
    – Surb
    Mar 13, 2018 at 20:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Scooby
    Mar 13, 2018 at 20:49
  • $\begingroup$ And also I can't find a formula for the 2 ways (I tried), I kinda have to brute force, which I dont want. $\endgroup$
    – Scooby
    Mar 13, 2018 at 20:50
  • $\begingroup$ 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. $\endgroup$
    – mdave16
    Mar 13, 2018 at 20:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Doug M
    Mar 13, 2018 at 20:52

2 Answers 2

3
$\begingroup$

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.

enter image description here

$\endgroup$
19
  • $\begingroup$ Adding also $50$ times $1$?. Is this valid? $\endgroup$
    – Piquito
    Mar 13, 2018 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – Piquito
    Mar 13, 2018 at 21:34
  • $\begingroup$ @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. $\endgroup$ Mar 13, 2018 at 21:40
  • $\begingroup$ Thanks you, @Ross. So it is not necessary that $1,4$ and $6$ appeared simultaneously like $(6-1)(6+4)$? $\endgroup$
    – Piquito
    Mar 13, 2018 at 21:46
  • $\begingroup$ @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. $\endgroup$ Mar 13, 2018 at 22:00
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Scooby
    Mar 15, 2018 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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