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

  • $\begingroup$ 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. $\endgroup$ – Graphth Apr 1 '11 at 13:38
  • $\begingroup$ Yes, too many typos and formatting errors. Should be $\frac{x^k}{(1-x)^k}, for example. $\endgroup$ – Thomas Andrews Apr 2 '11 at 19:29

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.

  • $\begingroup$ 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 $\endgroup$ – yoyo Apr 1 '11 at 15:15
  • $\begingroup$ @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!) $\endgroup$ – Anirbit Apr 2 '11 at 15:09
  • $\begingroup$ @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. $\endgroup$ – Anirbit Apr 2 '11 at 15:13
  • $\begingroup$ @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$. $\endgroup$ – Jonas Kibelbek Apr 2 '11 at 19:28
  • $\begingroup$ @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? $\endgroup$ – Anirbit Apr 6 '11 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.