<s>[INST] 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.)  
 [/INST] 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.
</s>