Number of Ways of Writing $n$ as Sum I have a general question about numbers:

How many ways can we write $n$ as the sum of the numbers $1$,$2$ and $3$?

I know that we start with the following functions: $$\frac{1}{1-z} = 1+z+z^2+ \dots$$ $$\frac{1}{1-z^2} = 1+z^2+ z^4+ z^6 + \dots$$ $$\frac{1}{1-z^3} = 1+ z^3+ z^{6}+ z^{9} + \dots$$ 
Multiplying these together we get $$\sum C(n) z^n = \frac{1}{(1-z)(1-z^2)(1-z^3)}$$ where $C(n)$ is our answer. In other words, by multiplying out the polynomials and looking at the coefficients, I can verify that I get the answer. But how do I know that this gives me the answer? How would I get an explicit formula for $C(n)$? I think I have to do something with partial fractions. So $$\frac{1}{(1-z)(1-z^2)(1-z^3)} = \frac{A}{1-z} + \frac{B}{1-z^2}+ \frac{C}{1-z^3}$$ and we have to solve for $A$, $B$ and $C$? 
 A: Read any book on generating functions to understand why $1/(1-z)(1-z^2)(1-z^3)$ is the correct generating function. 
The partial fraction decomposition is more complicated than what you describe. First we need to find all the roots in the denominator and their multiplicities. These are $1$ (multiplicity $3$), $-1$ and $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$ (each appearing with multiplicity $1$). Therefore the partial fraction decomposition is of the form
$$ \frac{A}{1-z} + \frac{B}{(1-z)^2} + \frac{C}{(1-z)^3} + \frac{D}{1+z} + \frac{E}{1 + z + z^2}. $$
The last term incorporates both roots $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$. Once you find $A,B,C,D,E$, you need to find the formulas for all these generating functions, and then you'll get a formula for $C(n)$.
A: Since I have it worked out, and it hasn't been posted, here is the explicit decomposition of the partial fractions.  We have
$$\frac{1}{(1-z)(1-z^{2})(1-z^{3})}$$ $$=\frac{z+2}{9\left(z^{2}+z+1\right)}-\frac{17}{72}\frac{1}{\left(z-1\right)}+\frac{1}{8(z+1)}+\frac{1}{4(z-1)^{2}}-\frac{1}{6(z-1)^{3}}.$$
Personally, I don't know the generating series for $\frac{1}{z^{2}+z+1}$, but I do know it for $\frac{1}{\omega-z}$ and $\frac{1}{\overline{\omega}-z}$, so lets go one step further.  We can derive
$$\frac{z+2}{9\left(z^{2}+z+1\right)}=\frac{1}{9}\left(\frac{\omega}{\omega-z}+\frac{\overline{\omega}}{\overline{\omega}-z}\right).$$
Since we know the expansion 
$$\frac{1}{\left(a-z\right)^{k+1}}=\frac{1}{a^{k+1}\left(1-\frac{z}{a}\right)^{k+1}}=\frac{1}{a^{k+1}}\sum_{n=0}^{\infty}\tbinom{n+k}{k}\frac{z^{n}}{a^{n}},$$
we can sum all of these to get the explicit formula for $C_{n}$.
Hope that helps,
A: You can write down a relativity explicit formula for $C(n)$.  First of all, write
$$
\frac{1}{1-z}=1+z+z^2+\cdots =\sum _{n=0}^\infty a_nz^n
$$
$$
\frac{1}{1-z^2}=1+z^2+z^4+\cdots =\sum _{n=0}^\infty b_nz^n
$$
$$
\frac{1}{1-z^3}=1+z^3+z^4+\cdots =\sum _{n=0}^\infty c_nz^n.
$$
Then, we see that
$$
C(n)=\sum _{i+j+k=n}a_ib_jc_kz
$$
Thus, you are summing over all positives ways of adding $i$, $j$, and $k$, to get $n$.  However, $b_j$ is nonzero iff $j$ is a multiple of $2$, in which case $b_j=1$, and similiary $c_k$ is nonzero iff $k$ is a multiple of $3$, in which case $c_k=1$.  It follows that the term $a_ib_jc_k$ is nonzero, in which case it evaluates to just $1$, iff $j$ is a multiple of $2$ and $k$ is a multiple of $3$, so that $n=i+j+k$ is a sum of $i$ ones, $j$ twos, and $k$ threes.  You can check that, given such a decomposition of $n$ into $i$ ones, $j$ twos, and $k$ threes, there exists a corresponding term in the above sum that evaulates to $1$, and conversely, every such term corresponds to exactly one such decomposition.  Thus, you are indeed summing a $1$ for each possibly way of writing $n$ as a sum of ones, twos, and threes, and hence $C(n)$ is the desired result.
Hope that helps.  I think it might be a little confusing the first time you read it.  Let me know if you have any questions about what I meant.
A: For the first part of the question: As Yuval points out, this is a typical use of generating functions, you are supposed to read about them to understand why $C(n)$ can be expressed in that way. 
A (slightly marginal) way of seeing it, in case you are familiar with discrete sequences (signals), convolutions and Fourier transforms: 
Say $C_1(n)$ gives us, for each $n$ the number of ways of expressing the number $n$ as a sum of ones; and  $C_2(n)$ the same, as a sum of twos.
Say we want to compute $C_{12}(n)$, number of ways of expressing the number $n$ as a sum of 1's and 2's.  We can partition $n = n_1 + n_2$, with $n_1$ being the sum of 1's, etc; for that particular partition, the total number of ways would be $C_1(n_1) C_2(n_2)$. But we must count all possible partitions, so that 
$$C_{12}(n) = \sum_{n_1+n_2=n} C_1(n_1) C_2(n_2) = \sum_{n_1=0}^n C_1(n_1) C_2(n-n_1) $$
You might recognize this a convolution of sequences, and recall that a convolution translates as product in the Fourier transform domain (or the Laplace transform, or the Z transform - basically the same as the generating function). But $C_1(n)$ and $C_2(n)$ are easy to find out, as well as its generating functions, so it's also easy to find out the generating function of $C_{12}$, as their product. And there you go.
A: Denote by $N_3=\{1,2,3\}\,$ then your question can be reformulated:
Find the number of partitions of natural number n in parts over set $N_3$ that number we denote
$p(n,N_3)$, $n=6k+l$, where $ k\in \{0,1,2,...\}$,and $ l\in \{0,1,2,3,4,5\}\,$
Using recurrences (no generating functions) I find that exact solution is. 
[1]  $p(6k,N_3)=3k^2+3k+1$
[2] $p(6k+1,N_3)=3k^2+4k+1$
[3] $p(6k+2,N_3)=3k^2+5k+2$
[4] $p(6k+3,N_3)=3k^2+6k+3$
[5] $p(6k+4,N_3)=3k^2+7k+4$
[6] $p(6k+5,N_3)=3k^2+8k+5$
To explain each formula is needed a lot of introduction
example: $p(10,N_3)=14$ because
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,1,3]
[1,1,1,1,1,1,2,2]
[1,1,1,1,1,2,3]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[1,1,1,1,3,3]
[1,1,1,2,2,3]
[1,1,2,2,2,2]
[1,2,2,2,3]
[2,2,2,2,2]
[1,3,3,3]
[2,2,3,3]
From our formulas we have
$p(10,N_3)=p(6\times 1+4)=3\times 1^2+7\times 1+4=14$ there $k=1$ 
