Wednesday, September 28, 2016

Bridge between Generating functions

I've always wondered about the question of going from OGF to the EGF or vice versa. Turns out this is not too complicated, though it needs some precise mathematical justification. That aside, I find the 'transition' between the generating functions very useful in some cases and very beautiful in others. Anyways, that will be discussion in this post. First, the simpler case of moving from EGF to OGF.

Note that these are just simple manipulations which anyone can do and I do it here just for the fun of doing it.

Let $f_e(x)$ be the EGF of a sequence. That is, 

$f_e(x)=\displaystyle a_0+a_1\frac{x}{1!}+a_2\frac{x^2}{2!}+a_3\frac{x^3}{3!}+\cdots$

Now using the definition of the Gamma integral, one can easily see that,

$f_o(x)=\displaystyle\int\limits_{0}^{\infty}e^{-t}f_e(tx)\, dt$

Technically, we should say that this equality holds provided either the sum on the LHS or the integral on the RHS converges.

For the simplest non-trivial sequence of $a_k=1, k \geq 0$, we know that $f_e(x)=e^x$ and $f_o(x)=1/(1-x)$ which readily satisfies the above equation.


Now for the opposite direction, we make use of the inverse Laplace transform of $t^n$. That is,
$\displaystyle\mathcal{L}^{-1}\left\{\frac{1}{s^{n+1}}\right\}=\frac{t^n}{n!}$

Again simple manipulations yield, $\displaystyle\mathcal{L}^{-1}\left\{\frac{1}{s}f_o\left(\frac{1}{s}\right)\right\}=f_e(t)$

Here again, the trivial case can be seen to work well here. However, we can one another nice application. Consider the OGF of the number of ways to partition a number $n$ with each part atmost $3$. That is,

$f_o(x)=\displaystyle\frac{1}{(1-x)(1-x^2)(1-x^3)}$

This generating function by itself does not help us in finding the number of partitions directly. Let's find the EGF of the same and see how useful it is.

$\displaystyle\frac{1}{s}f_o\left(\frac{1}{s}\right)=\frac{s^5}{(s-1)(s^2-1)(s^3-1)}$

Using Wolfram Alpha to compute the Inverse Laplace Transform of the above we get,

$f_e(t)=\displaystyle \frac{1}{12}t^2e^t+\frac{7}{12}te^t+\frac{47}{72}e^t+\frac{2}{9}Re[e^{\omega t}]+\frac{1}{8}e^{-t}$

where $\omega$ is the cubic root of unity. Knowing that $n![t^n]t^ke^t=n(n-1)\cdots(n-k+1)$, we have

$n![t^n]f_e(t)=\displaystyle \frac{n(n-1)}{12}+\frac{7n}{12}+\frac{47}{72}+\frac{2}{9}Re[\omega^n]+\frac{(-1)^n}{8}$

This already is a cool closed form expression for partition of $n$ with each part atmost $3$. If we also note that $Re[\omega^n]$ is periodic with period $3$, we now have an expression which can also be shown to count the number of triangles with perimeter $n$.

Hope you enjoyed this. I've a couple of ideas for my next post.


Until then
Yours Aye
Me