transforming ordinary generating function into exponential generating function

Question

I have seen a post here that says that you can convert an exponential generating function into an ordinary one with the aid of the Laplace transform. Is it possible to do the reverse transformation? i.e. I want to convert an ordinary generating function into an exponential one.

Answer 1

There may be some cases where complex variables, the residue theorem and the residue at infinity are helpful. Suppose your OGF is $f(z)$ and the desired EGF is $g(w).$ Then we have

$$g(w) = \sum_{n\ge 0} \frac{w^n}{n!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} f(z) \; dz.$$

This will simplify together with some conditions on convergence to give $$g(w) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{f(z)}{z} \sum_{n\ge 0} \frac{1}{n!} \frac{w^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{f(z)}{z} \exp(w/z) \; dz.$$

Example I. Suppose $$f(z) = \frac{1}{1-z},$$ which yields $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{1}{z} \exp(w/z) \; dz.$$

Now for $z=R\exp(i\theta)$ with $R$ going to infinity we have $$2\pi R\times \frac{1}{R^2} \times \exp(|w|/R) \rightarrow 0$$ as $R\rightarrow \infty$ so this integral is $$- \mathrm{Res}_{z=1} \frac{1}{1-z} \frac{1}{z} \exp(w/z)$$ and we get $$g(w) = \exp(w)$$ which is the correct answer.

Example II. This time suppose that $$f(z) = \frac{z}{(1-z)^2}$$ so that we should get $$g(w) = \sum_{n\ge 1} n \frac{w^n}{n!} = w \sum_{n\ge 1} \frac{w^{n-1}}{(n-1)!} = w\exp(w).$$

The integral formula yields $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z}{(1-z)^2} \frac{1}{z} \exp(w/z) \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^2} \exp(w/z) \; dz.$$

The residue at infinity is zero as before and we have $$\exp(w/z) = \sum_{n\ge 0} \left. (\exp(w/z))^{(n)}\right|_{z=1} \frac{(z-1)^n}{n!}$$

The coefficient on $(z-1)$ is $$\left. -\frac{1}{z^2} w\exp(w/z)\right|_{z=1} = - w\exp(w)$$

which is the correct answer taking into account the sign flip due to $z=1$ not being inside the contour.

Remark. Good news. The sum in the integral converges everywhere.

Addendum: somewhat more involved example. The OGF of Stirling numbers of the second kind for set partitions into $k$ non-empty sets is

$$\sum_{n\ge 0} {n\brace k} z^n = \prod_{q=1}^k \frac{z}{1-qz}.$$

We thus have that $$g(w) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \exp(w/z) \prod_{q=1}^k \frac{z}{1-qz} \; dz \\ = \frac{(-1)^k}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \exp(w/z) \prod_{q=1}^k \frac{z}{qz-1} \; dz \\ = \frac{(-1)^k}{k! \times 2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \exp(w/z) \prod_{q=1}^k \frac{z}{z-1/q} \; dz.$$

Computing the sum of the residues at the finite poles not including zero we get $$\frac{(-1)^k}{k!} \sum_{q=1}^k q\exp(qw) \times \frac{1}{q} \prod_{m=1}^{q-1} \frac{1/q}{1/q-1/m} \prod_{m=q+1}^k \frac{1/q}{1/q-1/m} \\ = \frac{(-1)^k}{k!} \sum_{q=1}^k \exp(qw) \prod_{m=1}^{q-1} \frac{m}{m-q} \prod_{m=q+1}^k \frac{m}{m-q} \\ = \frac{(-1)^k}{k!} \sum_{q=1}^k \exp(qw) \frac{k!}{q} \prod_{m=1}^{q-1} \frac{1}{m-q} \prod_{m=q+1}^k \frac{1}{m-q} \\ = \frac{(-1)^k}{k!} \sum_{q=1}^k \exp(qw) \frac{k!}{q} \frac{(-1)^{q-1}}{(q-1)!} \frac{1}{(k-q)!} \\ = - \frac{1}{k!} \sum_{q=1}^k \exp(qw) (-1)^{k-q} {k\choose q} \\ = -\left(\frac{(\exp(w)-1)^k}{k!} - \frac{(-1)^k}{k!}\right).$$

This is a case where the residue at infinity is not zero. We have the formula for the residue at infinity $$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

This yields for the present case $$- \mathrm{Res}_{z=0} \frac{1}{z^2} z \exp(wz) \prod_{q=1}^k \frac{1/z}{1-q/z} = - \mathrm{Res}_{z=0} \frac{1}{z} \exp(wz) \prod_{q=1}^k \frac{1}{z-q} \\ = - \frac{1}{k!} \mathrm{Res}_{z=0} \frac{1}{z} \exp(wz) \prod_{q=1}^k \frac{1}{z/q-1} \\ = - \frac{(-1)^k}{k!} \mathrm{Res}_{z=0} \frac{1}{z} \exp(wz) \prod_{q=1}^k \frac{1}{1-z/q} = - \frac{(-1)^k}{k!}.$$

Adding the residue at infinity to the residues from the poles at $z=1/q$ we finally obtain $$-\left(\frac{(\exp(w)-1)^k}{k!} - \frac{(-1)^k}{k!}\right) - \frac{(-1)^k}{k!} = - \frac{(\exp(w)-1)^k}{k!}.$$

Taking into account the sign flip we have indeed computed the EGF of the Stirling numbers of the second kind $$\sum_{n\ge 0} {n\brace k} \frac{z^n}{n!}$$ as can be seen from the combinatorial class equation $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge 1}(\mathcal{Z}))$$ which gives the bivariate generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$

Answer 2

Let $f(z)$ be the ordinary generating function and $\mathcal{L}$ be the Laplace transform. Then the EGF $g(z)$ has the form $$ g(z)=\mathcal{L}^{-1}\left(\frac{1}{z} f(z)\Big |_{z=\frac{1}{z}}\right) $$