Generating functions in combinatorics

Question

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.)

Answer 1

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.