0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.