# Thread: Confused on Exponential Generating function

1. ## Confused on Exponential Generating function

Given the following notation: $\displaystyle \left[\left[f(x)\right]\right]_{x^{k}}$ = the coefficient of $\displaystyle x^{k}$ in f(x).

Also for an exponential generating function $\displaystyle \left[\left[e^{x}\right]\right]_{\frac{x^{k}}{k!}}$=$\displaystyle \left[\left[\sum_{k\geq0}\frac{x^{k}}{k!}\right]\right]_{\frac{x^{k}}{k!}}=1$.

We have an example in Combinatorics A Guided Tour by David R. Mazur p. 129-130 as follows:

Find a formula for the n-th term of the sequence $\displaystyle \{d_{n}\}_{n\geq0}$ defined by $\displaystyle d_{0}=1\,\, d_{n}=nd_{n-1}+1\,\,\, n\geq1$.

After a short derivation we have $\displaystyle d_{n}=\left[\left[e^{x}*\frac{1}{1-x}\right]\right]_{\frac{x^{n}}{n!}}$=$\displaystyle \sum_{j=0}^{n}\left({n\atop j}\right)1*(n-j)!$=$\displaystyle \sum_{j=0}^{n}\left({n\atop j}\right)(n-j)!$

I am familiar with $\displaystyle (1+x)^{n}=\sum_{k\geq0}\left({n\atop k}\right)x^{k}$. Also I know $\displaystyle \frac{1}{1-x}=\sum_{k\geq0}k!\frac{x^{k}}{k!}$. But I just do not see how the binomial fits into the above summation.

I have been working almost nonstop on this course and applied statistics this summer. Any help with how the binomial gets into the above summation would be greatly appreciated. By the way, this is the most fascinating course I have ever taken even though I seem to be struggling just a little.

2. In this case you can use the cauchy product of the series

Given two series $\displaystyle \sum\limits^{\infty}_{k=0}a_{k}$

and $\displaystyle \sum\limits^{\infty}_{k=0}b_{k}$ , the Cauchy product is

$\displaystyle \sum\limits^{\infty}_{k=0}c_{k}$

where

$\displaystyle c_{n}= \sum\limits^{n}_{k=0}a_{k}b_{n-k}\;\;n \in N.$

3. Hi oldguynewstudent,

I think the theorem you need is that if
$\displaystyle f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n$
and
$\displaystyle g(x) = \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n$
then the coefficient of $\displaystyle \frac{x^n}{n!}$ in $\displaystyle f(x) \cdot g(x)$
is
$\displaystyle \sum_r \binom{n}{r} a_r b_{n-r}$

4. Originally Posted by awkward
Hi oldguynewstudent,

I think the theorem you need is that if
$\displaystyle f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n$
and
$\displaystyle g(x) = \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n$
then the coefficient of $\displaystyle \frac{x^n}{n!}$ in $\displaystyle f(x) \cdot g(x)$
is
$\displaystyle \sum_r \binom{n}{r} a_r b_{n-r}$
Yes, that is what I was looking for!