Help coming up with a solution to a combinatorial problem

Question

So here is the problem:

Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions.

I know this sounds confusing, but let me give an example:

Say we were trying to find the number of possible combinations to add up to the number 6 using, as stated above, only the numbers 1, 2, & 3 with exactly 2 additions.

The solution is easy:

Since we are trying to add up to 6 using exactly 2 additions with the only three numbers we are allowed to use (1, 2, & 3), we only get: {3 + 3}.

Similarly, If we were trying to find the number of possible combinations to add up to the number 4 with exactly 2 additions we get: {1 + 3} & {2 + 2}.

So, I am asking is there an algorithm out there that I can use to solve this when the numbers get bigger? Is there a clever way to solve this with code? I've been thinking about this for a while and can't seem to solve it.

Thanks!

Answer 1

One way to solve this is using generating functions. The number of ways to get the number 6 using "2 additions" of 1, 2, or 3 is the coefficient of $x^6$ in $(x+x^2+x^3)^2$. This generalizes: the number of ways to get the number $n$ using "$k$ additions" of 1, 2, or 3 is the coefficient of $x^n$ in $(x+x^2+x^3)^k$. I'll let you play with some examples to see why this is so.

Once you know this fact, you can then use polynomial multiplication and repeated squaring to compute the polynomial $(x+x^2+x^3)^k$ and then read off the answer.

See also Calculating the number of multiplications necessary to evaluate a polynomial.