# Thread: Writing n as a sum of integers

1. ## Writing n as a sum of integers

Hey,

I have been given a problem that at first seemed quite trivial but on further inspection seems to be quite hard. If n is a non-negative integer, in how many ways is it possible to write

n=a+2b+3c

for non-negative integers a, b, c.

clearly, if i fix some 0<c<floor(n/3), then i have n-3c choices for a and b, but i'm not sure how to proceed. I also thought it could be calculated using a recurrence relation, but I'm particularly rusty in that area of combinatorics. Any help would be greatly appreciated.

2. Originally Posted by hairymclairy
I have been given a problem that at first seemed quite trivial but on further inspection seems to be quite hard. If n is a non-negative integer, in how many ways is it possible to write
n=a+2b+3c for non-negative integers a, b, c.
This is not a simple formula. It can be done with generating functions.
Expand the following: $\displaystyle \left( {\sum\limits_{k = 0}^n {x^k } } \right)\left( {\sum\limits_{k = 0}^n {x^{2k} } } \right)\left( {\sum\limits_{k = 0}^n {x^{3k} } } \right).$
The coefficient of the $\displaystyle x^n$ answers your question.
Working with a computer algebra system that is doable.
With a CAS you could let $\displaystyle f(x)= \left( {\sum\limits_{k = 0}^n {x^k } } \right)\left( {\sum\limits_{k = 0}^n {x^{2k} } } \right)\left( {\sum\limits_{k = 0}^n {x^{3k} } } \right)$ then $\displaystyle \displaystyle\frac{1}{{n!}}\frac{{d^n f}}{{dx^n }}(0)$ will give you the same answer.