The coefficient of x^n is the number of ways that we can pick one term in each of the n factors (1+x+x^2) so that the total degree is n.
We can get a degree of n by choosing x every time. There is just one way to do that.
We could choose 1 once, x^2 once, and x the other n-2 times. There are n choices of which factor should contain the 1 we choose and then n-1 ways to choose the x^2 from a different factor.
We could choose 1 twice, x^2 twice, and x the other n-4 times. More generally, we could choose 1 r times, x^2 r times, and x the remaining n-2r times. Once we decide to use r 1s, we need to use r x^2 terms or else the total degree would not be n. The number of ways to do this is (n choose r)(n-r choose r) = (n choose r, r, n-2r) where the last is a multinomial coefficient. This simplifies to n!/(r! r! (n-2r)!).
So, the coefficient of x^n is the sum from r=0 to infinity of n!/(r!^2 (n-2r)!). We can rewrite the summand as n*(n-1)*...(n-2r+1)/(r!^2).
