# How many ways can 1's and 2's be added to equal 17 if order matters?

Question is in full in the title. I didn't think I'd be back here so quickly since most of these permutation and combination exercises aren't very difficult, but this is the second one that has me scratching my head on where to even begin. I've done some Googling for help, but I haven't found anything similar enough to this problem to help me out.

• Combined? In what way? $2-1+2-1+2-1+2-1+...$, $2-1-1+2-1-1+...+1+1+1+1+...+1$. There are infinite possibilities then – CBenni Jan 24 '13 at 14:00
• Then please include that in your post. – CBenni Jan 24 '13 at 14:04
• With some Googling I found this link which describes the solution. Su, Francis E., et al. "Domino and Square Tilings." Math Fun Facts. < math.hmc.edu/funfacts >. – Marc van Leeuwen Jan 24 '13 at 14:24

I had exactly this pop up in a real-life[1] problem I was solving just yesterday. Here's a Hint:

Start small: try making sums of 1's and 2's that add up to 1, 2, 3, 4, 5, 6. By this time you should see the pattern, which is a sequence of numbers you should recognize. Proving that the numbers actually follow this sequence is not particularly difficult. Then, find the 17th number in the sequence (also not difficult).

[1] Well, sort of real-life. It has to do with sums that arise in a covariance matrix in an autoregressive model in statistics. The number of terms in each sum is given by this problem.

• Okay, I've done that and figured out with Google that the pattern you refer to is the Fibonacci pattern. Unfortunately we haven't learned about that in our coursework, so I'm not comfortable basing my answer on it. I'm still working on the proof aspect though, since that is something I could use. – Dave Jan 24 '13 at 14:13
• I figured out the proof by staring at the numbers I put under the listings I made for each of the smaller numbers, 3-6 in this case. I realized that each number was the two numbers before it added together and worked out a formula I can use from that. Thanks a ton. =) I would vote you up if I had the rep for it. – Dave Jan 24 '13 at 14:32
• @Dave Glad to help. – Jonathan Christensen Jan 24 '13 at 14:33
• @Dave: Glad to see you work this out yourself to the completion. +1 for to both your question and Jonathan's answer. – Jyrki Lahtonen Jan 24 '13 at 14:39
• @Dave even if you didn't feel comfortable asserting that the sequence was Fibonacci's and using a formula to compute the 17th term directly, computing the first 17 terms sequentially can be easily done without knowing the sequence is anything special. – Dan is Fiddling by Firelight Jan 24 '13 at 14:47

Hint: Let $f(k)$ be the number of ways to generate a sum of $k$. Next, suppose you are trying to compute $f(n)$. How many of those combinations end with a $1$? How many end with a $2$? Add these two up to get $f(n)$. Use a recurrence relation. Look familiar? Compute $f(17)$.

• Hmm, that's not familiar from our reading. The only thing I remember seeing that seems like it would apply to this is the binomial theorem for combinatorics, but I've yet to find a way to apply it. – Dave Jan 24 '13 at 14:15
• @Dave Ok. Suppose you want to count all sequences summing to $n$, but also ending with a $1$. What does it tell you about the sum of the rest of the sequence (excluding the last 1)? That the sum of that part of the sequence will always be $n-1$. How many sequences can you generate that sum to $n-1$ (use the definition of $f(k)$). You will have exactly these many sequences that end with a $1$ and sum up to $n$. Repeat for ending with a 2. Clearer? – Paresh Jan 24 '13 at 14:21
• Yeah, that made a lot more sense, but by the time I read it I had the formula worked out. Great job in guiding me to the answer instead of just handing it over, though. I truly appreciate that. – Dave Jan 24 '13 at 14:33
• @Dave Sure, no problem! – Paresh Jan 24 '13 at 14:35

Denote by a number of 2-s and b number of 1-s then number of permutations(arrangements) of $a+b$ objects where are $a$ of first kind and $b$ of second kind is $$\frac{(a+b)!}{a!b!}$$ if $$a\cdot 2+b\cdot 1=17\Rightarrow b=17-2a,0\leq a\leq 8,a+b=17-a$$ $$\sum_{2a+b=17}\frac{(a+b)!}{a!b!}=\sum_{a=0}^{8}\frac{(17-a)!}{a!(17-2a)!}=\sum_{a=0}^{8}\binom{17-a}{a}=F_{18}=1597$$

Let $f(n)$ be the number of ways of adding $1$s and $2$s to get $n$.

$f(0) = 0$
$f(1) = 1$

As we can summing upto $n-1$ and adding $1$ or summing upto $n-2$ and adding $2$, we get,

$f(n) = f(n-1) + f(n-2)$

for $n>1$

This is the definition of the Fibonacci number sequence, which is the solution.

• Should'nt f(0) = 1, else if I do f(2), then by your base case the answer will be 1. but clearly then are 2 ways to get to 2. (1+1, and 2 itself) ? – some1fromhell Mar 14 '17 at 15:08

If you have some programming skills, you could find the answer computationally, Project Euler-style. Simply write a program that iterates over all of the possible combinations of terms, and count the number of combinations that add up to seventeen.

We know that there are at most seventeen terms (1 + 1 + 1 ... = 17), and three possible values for each term (0, 1, or 2). So we can give an upper bound on the number of iterations as 3^17 = 129140163, which is a manageable number of iterations.

Clearly this solution is no good for sums much bigger than 17, as the number of iterations required grows exponentially.

Given the more elegant mathematical answers I've seen here, this is probably akin to swatting a fly with a sledgehammer, but it is a solution nonetheless :)

I just noticed this is tagged homework, so I'm pulling the code I posted, to respect that. You can still find it in the edit history if you really want to see it. Instead, here are some hints:

• The hardest part will probably be finding a way to iterate over the possible combinations. It might help to think of the terms as digits in a trinary (base-3) number that you increment from 0 to 11111111111111111.
• Be careful of combinations that are actually the same - ...121 and ...1210, for example
• Whenever you find a combination that adds to 17, add it to a Set. The answer will be the size of the Set once you finish iterating.
• As a computer scientist, this would be a bad approach (but nonetheless valid for small $n$). Try this algorithm for $n = 1000000$, or maybe $n = 10^{100}$. I'll be getting some coffee. Or maybe getting a Master's. – Sean Allred Jan 24 '13 at 19:50
• Yep, agreed. I'll make that more explicit in the answer. – Kevin K Jan 24 '13 at 19:56