Calculate all possible combinations of 1, 2 & 3 which equal 67 My son (a third grader) was given this problem to solve. Is states that:
In a basketball game, one of the teams scored 67 points. If baskets can be worth 1 point for a free throw, 2 points for a field shot or 3 points for a 3 pointer, how did the team reach 67 points? How can you know that you have found all possibilities.
We can easily start out by doing 1 x 67 times, and then adding a 2 into the mix until we had mostly 2 and then starting with 3 and rounding that pattern back to introducing 1. We got up to 77 possible combinations when applying this simple pattern based solution. But that doesn't account for all the other combinations where any of the 3 numbers could be used which still equal 67.
It seems stars and bars may be a good way to deal with this problem, but I'm unclear on how to apply it. Would anyone be able to explain this? I'm not looking for the answer, but keen to understand how to calculate how many combinations there could be for any 3 sets of numbers to equal any given number.
Much appreciated!
 A: To summarize part of the discussion in the comments:
Personally, I think it is more tractable if the order does matter.  In that case we can work recursively.  Letting $a_n$ denote the answer with a total of $n$ we remark that, for $n>3$, we must have $$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$
since the last score must be one of $1,2$ or $3$.  This resembles one standard interpretation of the Fibonacci numbers, where $F_n$ is defined as the number of ways to get a sum of $n$ using an ordered sequence of $1's$ and $2's$.  That is to say, the same problem only without the $3$ point shot.
That recursion is easily implemented in Excel, or whatever (you'll have to work out $a_1, a_2, a_3$ but that is not hard).  Of course, the terms grow very rapidly.
If order does not matter:
Then we are counting triples of non-negative integers $(a,b,c)$ with $3a+2b+c=67$.  We remark that $a\in \{0,\cdots,  22\}$.  For a fixed $a$ we are now trying to write $67-3a$ as $2b+c$.  How many ways are there for that?  Well, since $67-3a-c$ is even we can work out the parity of $c$ from that of $a$.  Indeed, they must have opposite parities.  It follows that the number of possible $c's$ is given by $$1+\Big \lfloor \frac{67-3a}2\Big \rfloor$$
Note:  I suggest that out by hand for several values of $a$ to convince yourself that it is correct.
That gives us the number of good triples for a fixed value $a$.  We get the answer by summing $$\sum_{a=0}^{22} \left(1+\Big \lfloor \frac{67-3a}2\Big \rfloor\right)=408$$
Should say, that is all a bit error prone.  To check, I did the computation using generating functions, here which confirms the result. (you can read off the coefficient of $x^{67}$ is $408$ If you are not used to Wolfram Alpha, you need to click "more terms" often enough to get to $x^{67}$).  Obviously that's not a useful method given the context, but I thought it was worth checking the result.
A: Here's an start (assuming order doesn’t matter).
Imagine that you want to know how many ways there are to buy a $67 candy bar from a vending machine that only accepts \$3, \$2, and \$1 coins. Since order doesn’t matter, you can count the ways you can pay using \$3 coins first, then \$2, then \$1 coins. (It’s the same problem, but sometimes making a problem involve money makes it easier to think about.)
You can use anywhere from $0$ and $22$ \$3 coins. If you use, say, exactly $7$ \$3 coins, then you have to pay the remaining \$67 - \$21 = \$46 dollars with \$2 and \$1 coins. You can do this using $0$, $1$, $2$, ... or $23$ \$2 coins (and the rest \$1 coins), for $24$ possible ways.
Can you figure out how many ways there are to finish paying after using a given number of \$3 coins, say $c$ of them (not necessarily $7$), and then (by hand is fine) add up your answers for $c=0$ through $c=22$?
