Generating functions in combinatorics I am not very familiar with how generating functions are used but for something I was needing I ran into the following constructions, 


*

*Let $c_{nk}$ be the number of solutions in $\{1,2,3,4...,\}$ for the equation $x_1+x_2+x_3+...+x_k = n$. Then one can easily show that $c_{nk} = ^{n-1}C_{k-1}$ But the following is not clear to me..one defines a "generating function" $c_k(x)$ as, $c_k(x) = \sum_{n=k}^{\infty} c_{nk} x^n$. Then one claims that the following is true,


$c_k(x) = (x+x^2+x^3+...)^k = x^k(1-x)^k$
I can't see from where the above came!
From the above it follows that, $\sum_{k=1} ^\infty c_k(x) = \frac{x}{1-2x}$ 
The idea seems to be that from the above one can read off that $\sum {k=1} ^n c_{nk} = 2^{n-1}$. (This was obvious from the initial formula given for $c_{nk}$) But this way of getting that result is not clear to me. 


*

*Let $p(n)$ be the number of unordered partitions of $n$ (a positive integer). Then clearly $p(n)$ is the number of solutions to the equation, $x_1+x_2+x_3+...+x_n = n$ with $x_1\geq x_2 \geq x_3 ...x_n > 0$ After appropriate variable redefinition one can see that $p(n)$ is the number of solutions of $y_1 + 2y_2 + 3y_3 + ... + ny_n = n$ with $y_i \geq 0$ for all $i$. Now apparently $p(n)$ can be given through a generating function $P(x)$ defined as, 


$P(x) = \sum _{n=0} ^\infty p(n)x^n$
Now I can't see how it follows that, 
$P(x) = \prod _{k=1} ^\infty \frac{1}{(1-x^k)}$ 
(apparently the above can somehow be mapped to the familiar question of number of ways in which $n$ balls can be arranged in a line where $r_i$ of them are of the colour $i$ ($\sum r_i = n$). This is equal to the coefficient of $\prod _i x_{i}^{r_i}$ in $\prod _i (1+x_i + x_i^2 + x_i ^3 + ...)$. But the connection between this question and the generating function for unordered partitions of an integer is not cleat to me.)  

In both cases, the key is to recognize the power series identity (which should be familiar if you know about geometric series) 
$$ 1+y+y^2+y^3+ \ldots = \sum_{i=0}^\infty y^i = \frac{1}{1-y}. $$
In your formula for $c_k(x)$, the last exponent should certainly be negative, so we have $c_k(x) = x^k(1-x)^{-k}$.  Then applying the power series identity shows that $\frac{x}{1-x} = x(1-x)^{-1} = x +x^2 +x^3 + \ldots$.
For the partitions generating function, we use the same identity many times, with $y = x^k$ for all integers $k\geq 1$.  Think of how to find the coefficient of $x^n$ in 
$$(1+x+x^2 + x^3 + \ldots) (1+x^2+x^4+x^6 +\ldots) (1+x^3+x^6+x^9+ \ldots)\cdots$$
and you'll see that it gives you precisely the number of partitions of $n$.

EDIT:
Okay, think about the case $k=2$ for $c_k(x)$.  The claim is that 
$$c_2(x) = (x+x^2+x^3+\ldots)^2.$$
Just look at what happens when we expand this, using the distributive property:
\begin{align*}
c_2(x) &= (x+x^2+x^3+\ldots)(x+x^2+x^3+\ldots) \\
&=x(x+x^2+x^3+\ldots)+x^2(x+x^2+x^3+\ldots)+x^3(x+x^2+x^3+\ldots)+ \ldots \\
&=(x^{1+1}+x^{1+2}+x^{1+3}+\ldots)+(x^{2+1}+x^{2+2}+x^{2+3}+\ldots)+(x^{3+1}+x^{3+2}+x^{3+3}+\ldots)+ \ldots \\
&=(x^{1+1})+(x^{1+2}+x^{2+1})+(x^{1+3}+x^{2+2}+x^{3+1})+\ldots \\
&=x^2 + 2x^3 + 3x^4 + \ldots
\end{align*}
You see that to get each $x^n$ term, we simply need a solution to $a_1 + a_2 = n$ with $a_i \geq 1$.  In the same way, if you have $c_k(x) = (x+x^2+x^3+\ldots)^k$, to get each $x^n$ term, we simply need a solution to $a_1 + a_2 + \ldots + a_k = n$ with $a_i \geq 1$.  Do you see how it works?
Try expanding the partition generating function in the same way-- it's basically the same idea.
