1
$\begingroup$

I've been introduced in my last lectures. And for the following problem:

Having 3 different types of books $a,b,c$ in how many ways can we take four different books putting them in a shelf such that the book $a$ can only be taken at most $1$ time, $b$ can be taken at most $3$ times and $c$ can only be taken at most $2$ times?

The ordinary generating function for this problem is:

$\quad \quad \quad \quad \quad \quad \quad $enter image description here

Looking at the exponential generating function of the same problem, the only part of interest is the coefficient of $x^4$, which is:

$$\left(\frac{ab^3}{1!3!}+\frac{b^3c}{3!1!}+\frac{ab^2c}{1!2!1!}+\frac{b^2c^2}{2!2!}+\frac{abc^2}{1!1!2!}\right)$$ And then multiply it by $4!/4!$. But why do I need an exponential generating function? Isn't only needed to take the coefficient of $x^4$, divide each term of it by $a_1!a_2!\dots a_n!$ with $a_n=\text{power of a,b,c,}\dots$ and then multiply it by $4!4!$? It's not clear why such complication is needed.

By complication I mean to expand that generating function with the factorials, I could expand the ordinary generating function and then artificially add the factorials.

$\endgroup$
4
$\begingroup$

The most blatant reason why exponential generating functions are useful (for infinite sequences) is that the ordinary power series might not converge. If $a_n = n!$, for example, the ordinary generating function does not exist as any kind of analytic object.

But the deeper reason why exponential generating functions are so common is that they have interesting product and composition formulas. If we have a sequence $c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}$, then the exponential generating function for the $c_n$ is the product of the egf for $a_n$ and the egf for $b_n$. In other words, sequences defined by a sum of choices have a tendency to possess nice exponential generating functions.

For example, suppose that we want to compute the number of subsets of an $n$-element set. By the product formula, this has egf $e^x \cdot e^x = e^{2x}$, so the answer is $2^n$. To count the number of surjective functions from a set of $n$ elements to a set of $m$ elements, we can work with the egf $(e^x-1)^m$, and so on.

With a bit more finesse, we can make sense of the composition of exponential generating functions as well. For example, the Bell numbers $B_n$, which count partitions, have exponential generating function $e^{e^x - 1}$, which follows from very general theory. Try doing that with ordinary generating functions.

$\endgroup$
  • $\begingroup$ So I suppose that the EGF exist as an analytic object (my professor told me that it's radius of convergence is bigger than the radius of convergence of OGF's), what does these analytic properties tell about the EGF? Does it always tell something fixed or it indicates something different on different applications? $\endgroup$ – Billy Rubina Feb 7 '15 at 1:41
  • 1
    $\begingroup$ @Vÿska That's a very general question, but one concrete thing that a generating function gives you is asymptotic information about its associated sequence. The radius of convergence, for example, gives excellent first-order information about asymptotic growth, and one can even deduce things like Stirling's approximation with a more nuanced approach. $\endgroup$ – Slade Feb 7 '15 at 7:52
  • 1
    $\begingroup$ @Slade: Thank you for your input. Could you please explain the reasoning behind using $$e^x . e^x$$ to calculate the number of subsets? $\endgroup$ – Vectorizer Jul 13 '15 at 14:39
  • 1
    $\begingroup$ @Vectorizer I basically explained this in the previous paragraph. Intuitively, the product is counting the number of ways of coloring a set using two colors, while each $e^x$ is counting the number of ways of coloring a set with one color (namely, $1$). $\endgroup$ – Slade Jul 13 '15 at 22:23
  • $\begingroup$ There is a nice example fooling around with the formal series $\sum_{n \ge 0} n! z^n$, which converges just for $z = 0$, so convergence isn't necessary. To get a "nice" function allows you to use calculus, which is a tremendous bonus, though. $\endgroup$ – vonbrand Aug 9 '15 at 2:03
1
$\begingroup$

Wilf's book "generatingfunctionology" explains why exponential generating functions are useful. Another view, much more mathematically demanding, is explained by Flajolet and Sedgewick's "Analytic Combinatorics", the approach is summarized by Wikipedia.

$\endgroup$

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.