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

• It's \sum and \prod, not \Sum and \Prod. And, you appear to have many other typos, altogether making it hard to tell what you're saying. – Graphth Apr 1 '11 at 13:38
• Yes, too many typos and formatting errors. Should be $\frac{x^k}{(1-x)^k}, for example. – Thomas Andrews Apr 2 '11 at 19:29 ## 1 Answer 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 eachx^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. • choose how many partitions of size 1 you want (1 for zero,$x$for 1,$x^2$for 2,...) then how many partition of size 2 you want (1 for zero,$x^2$for 2,$x^4$for 2,...) etc – yoyo Apr 1 '11 at 15:15 • @Jonas I think my question framing was not clear enough. I do know about the GPs! What I want to know is how does one see that$c_k(x)$is that series raised to the power$k$? Similarly for$P(x)$. (Like what is yoyo saying...its not clear to me!) – Anirbit Apr 2 '11 at 15:09 • @yoyo Can you kindly explain in more details what you are saying? What is the mapping you have in mind between sizes of partitions and powers of$x$....didn't understand you. – Anirbit Apr 2 '11 at 15:13 • @Anirbit: I added an edit explaining how to expand the product and see that the coefficient of$x^n$in$c_k(x)$is the number of solutions to$a_1 + a_2 + \ldots a_k=n\$. – Jonas Kibelbek Apr 2 '11 at 19:28
• @Jonas I can see what you are saying. I had also done these "experimental" checks on the formula and seen that it works. The point is how does one "derive" these generating functions? Is there a systematic way to get them or are they just an intelligent guess? – Anirbit Apr 6 '11 at 8:48