Power Series and Generating Functions (IV) – Exponential Generating Functions

Note: this article is noticeably more difficult than the previous instalments. The reader is advised to be completely comfortable with generating functions before proceeding.

We’ve already seen how generating functions can be used to solve some combinatorial problems. The nice thing is that even if a sequence has no nice closed form, generating functions allow us to efficiently compute a large number of terms in the sequence. With modern computers, such computations are often a cakewalk.

Here, we shall look at a different type of generating functions. Given a sequence a_0, a_1, a_2, \dots, let us define:

f(x) = a_0 + \frac{a_1}{1!}x + \frac{a_2}{2!}x^2 + \frac{a_3}{3!}x^3 + \dots.

This is called the exponential generating function (EGF) of the sequence an. Here’re some easy examples.

  • The EGF for an = 1 is given by 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x; that’s why there’s an “exponential” attached to the name.
  • The EGF for ann! is given by 1 + x + x^2 + \dots = (1-x)^{-1}.
  • The EGF for anrn is given by 1 + rx + \frac{(rx)^2}{2!} + \frac{(rx)^3}{3!} + \dots = e^{rx}.

When do we use this and not the standard generating function? Generally speaking, the EGF is useful for counting the number of combinatorial objects for a labeled set, while the standard generating function is useful for an unlabeled set. Here’s why, roughly.

  • Suppose, to get a structure A on n identical balls, we need to split the set of n balls into two disjoint subsets and impose structure B on the first subset, and structure C on the second subset. Under this assumption, if an (resp. bncn) denotes the number of structures of type A (resp. BC) on the set of n balls, then we have a_n = b_0 c_n + b_1 c_{n-1} + \dots + b_{n-1} c_1 + b_n c_0, since we need to consider the case where the first subset has 0, 1, 2, …, or n balls.
  • Now consider the same problem, except that the n identical balls are replaced by the set {1, 2, …, n}. To count an, suppose we choose a k-subset S \subset \{1,2,\dots,n\}; there are C(n, k) = \frac{n!}{k!(n-k)!} possible choices for S. Then we impose a structure B on S; there are bk ways of doing this. And finally, we choose a structure C on the remaining \{1,2,\dots,n\} - S; there are cn-k ways of doing this. This gives a_n = \sum_{k=0}^n C(n,k) b_k c_{n-k}, or \frac{a_n}{n!} = \sum_{k=0}^n \frac{b_k}{k!} \cdot \frac{c_{n-k}}{(n-k)!}thus their EGFs multiply to give the final EGF.

Without further delay, let’s look at some concrete examples.

Problem 1. Find the number of functions f : {1, 2, …, n} → {1, 2, …, r}.

Solution. Any beginning student of combinatorics knows the solution: rn. But let’s derive this using EGF. Corresponding to each f, we take the inverse image f^{-1}(1), f^{-1}(2), \dots, f^{-1}(r) which are subsets of {1, 2, …, n}. Let S_i = f^{-1}(i); then we get a partition of {1, 2, …, n} into r disjoint subsets:

\{1, 2, \dots, n\} = S_1 \cup S_2 \cup \dots \cup S_r.

Hence, to find a function f, we only need to state an ordered partition into r subsets (“ordered” here means that swapping S1 and S2 changes the partition). If r is fixed, and an denotes the number of f, then the EGF for (an) is the product of r copies of the sequence (1,  1, 1, … ):

EGF(a_n) = \overbrace{e^x \times e^x \times \dots \times e^x}^{r\ \text{copies}} = e^{rx}.

But the coefficient of x^n in e^{rx} is \frac{r^n}{n!}, so we get the result a_n = r^n as expected. ♦

Problem 2. Find the number of surjections : {1, 2, …, n} → {1, 2, …, r}, where r ≤ n.

Solution. We now have the partition \{1, 2, \dots, n\} = S_1 \cup S_2 \cup \dots \cup S_rwhere each S_i is non-empty. So the corresponding EGF for each term is now the EGF of (0, 1, 1, 1, …), which is

x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x - 1.

Hence, if we fix r and let an denote the number of surjections f, then the EGF for an is (e^x - 1)^r. ♦

Let’s consider small values of r:

  • r = 2 : EGF = e^{2x} - 2e^x + 1, so a_n = 2^n - 2.
  • r = 3 : EGF = e^{3x} - 3e^{2x} + 3e^x - 1, so a_n = 3^n - 3\cdot 2^n + 3.
  • r = 4 : a_n = 4^n - 4\cdot 3^n + 6 \cdot 2^n - 4.

Now the astute reader can easily write down the general formula.

Problem 3. Consider all possible functions f : {1, 2, …, n} → {1, 2, …, s}. What is the expected size of the image of f ?

Solution. Fix n and s. Let b_r be the number of f whose image has size r. If we consider the case im(f) = {1, 2, …, r}, then the number of such f is n! times the coefficient of x^n in (e^x - 1)^r. Hence, b_r is exactly s\choose r times this number. So we need to look at:

b_1 + 2b_2 + 3b_3 + \dots = n! \times \text{coeff. of } x^n \text{ in } \sum_{r=0}^s r{s\choose r} (e^x - 1)^r. (*)

Thus it really suffices to simplify \sum_r r {s\choose r} y^r. This can be achieved by differentiating the binomial expansion:

{s\choose 0} + {s\choose 1} y + {s\choose 2}y^2 + \dots + {s\choose s}y^s = (1+y)^s

\frac{d}{dy} \implies {s\choose 1} + 2{s\choose 2}y + \dots + s{s\choose s}y^{s-1} = s(1+y)^{s-1}.

So our sum simplifies to \sum_r r {s\choose r} y^r = sy(1+y)^{s-1}. Upon substituting y = e^x - 1, the sum (*) simplifies to s e^{(s-1)x}(e^x - 1) = s (e^{sx} - e^{(s-1)x}). This gives b_r = s^{n+1} - s(s-1)^n. Dividing by the total number of possible functions (s^n), the mean image size is s - \left(\frac{s-1}s\right)^n, which is very close to s-1 for large s. ♦

Exercise 1. Find the number of r-letter words you can form with the letters ‘a’, ‘b’ and ‘c’, where ‘a’ occurs an odd number of times and ‘b’ occurs an even number of times.

Exercise 2. The Stirling number of the second kind S^{(r)}_n is the number of partitions of {1, 2, …, n} into r disjoint non-empty subsets. Write down an expression for S^{(r)}_n by computing its EGF or otherwise. Also write down an expression for the Bell number B_n, which is the number of partitions of {1, 2, …, n}. [ Note: the partitions here are unordered, i.e. \{1,2\} \cup \{3\} and \{3\} \cup \{1,2\} are considered identical partitions. ]

Exercise 3. (Comtet’s square). Let a_n be the number of ways to partition {1, 2, …, n} such that (i) the number of parts is X; and (ii) the size of each part is Y, where XY are elements of {“unrestrained”, “even”, “odd”}. Find the EGF for a_n. Since there’re 9 possible ordered pairs for (XY), you should get 9 answers in all.

Throughout this section, we shall require the reader to be somewhat acquainted with the concept of permutations. A permutation of order n is a bijective map from {1, 2, …, n} to itself. For example, we can express a permutation of order 9 via the following diagram:

Such a permutation p would map 1 to 3, 2 to 5, 3 to 9, … . Or one can also express the same permutation in the form of cycles:

which is clearer and one immediately knows how the successive powers p^2, p^3, \dots act on the numbers 1, …, 9. For example, since the three cycles have lengths 1, 3, and 5, the smallest n for which p^n = id is n = lcm(1,3,5) = 15. We say that the order of the permutation is 15.

An element i for which p(i) = i is called a fixed point of the permutation p. In the above example, the only fixed point is 4.

Problem 4. Let a_n be the number of permutations p of {1, 2, …, n} such that p^2 = id. [ Such a permutation is called an involution. ] Find the exponential generating function of a_n.

Proof. If we write p as a product of cycles as above, then p is an involution iff all the cycles have lengths 1 or 2. If there are exactly r cycles (where r is fixed), then the number of permutations has exponential generating function in n given by: \left(x + \frac{x^2} 2\right)^r, right?

No! Since swapping the cycles has no discernible effect on the permutation (e.g. (1, 2)(4, 5)3 = (1, 2)3(4, 5)), we should divide it by r!. Hence, we should look at \frac 1 {r!} \left(x + \frac{x^2} 2\right)^r instead. Summing over all r, we get:

\sum_{r=0}^\infty \frac 1 {r!} \left(x + \frac{x^2} 2\right)^r = \exp\left(x + \frac{x^2}2\right) = \exp(x)\exp(x^2/2).

This allows us to express a_n as a sum:

a_n = \sum_{k=0}^{[n/2]} \frac{n!}{2^k k! (n-2k)!}. ♦

Problem 5. Find the number a_n of permutations p of {1, 2, …, n}, where p is a product of an even number of disjoint cycles.

Solution. As in the previous problem, we consider the case of r cycles. Given the set {1, 2, …, s}, how many cycles p of length s can we form? To answer that, for any such cycle we can start from 1 and obtain a unique sequence of s-1 numbers via p(1), p(p(1)), p(p(p(1))), \dots which is a permutation of {2, 3, …, s}. Hence the number is (s-1)!, which gives the EGF:

x + \frac{1!x^2}{2!} + \frac{2!x^3}{3!} + \frac{3!x^4}{4!} + \dots= \sum_{r=1}^\infty \frac{x^r}{r} = -\log(1-x).

To find the number of p where p is a product of r cycles, we have to take n! times the coefficient of x^n in \frac 1 {r!}(-\log(1-x))^r. [ As before, the factor of \frac 1 {r!} is included since swapping cycles does not change the permutation. ] Hence to find the EGF for a_n, we sum over all even r:

\sum_{i=0}^\infty \frac 1 {(2i)!} (-\log(1-x))^{2i} = \cosh(-\log(1-x)),

where \cosh z = \frac{e^z + e^{-z}} 2 is the hyperbolic cosine function. Hence the above simplifies to \frac 1 2((1-x) + (1-x)^{-1}) = 1 + \frac 1 2 (x^2 + x^3 + \dots). In conclusion:

  • When n = 0, a_n = 1.
  • When n = 1, a_n = 0 (obviously!).
  • When n ≥ 2, a_n = \frac{n!}2.  ♦

Note : considering how nice the answer is, one naturally wonders if there is a nice combinatorial argument for this. There is, actually. If p is any permutation of {1, 2, …, n}, where n\ge 2, we compose it with (1, 2) to give q = p\circ (1,2). If 1 and 2 belong to the same cycle of p, the composed permutation q would split them up into two cycles; conversely, if 1 and 2 belong to disjoint cycles, then q merges the two cycles into one. The proof is left as an exercise.

But that’s how things are; one often discovers such patterns through heavy machinery before finding a simpler combinatorial proof.

Exercise 4. A derangement is a permutation without a fixed point (i.e. for all ip(i) ≠ i). Prove that the number of derangements of {1, 2, …, n} is n!(1 - \frac 1 {1!} + \frac 1 {2!} - \dots + (-1)^n \frac 1 {n!}).

Exercise 5. Prove that the number of permutations p of {1, 2, …, 2n} having only even cycle lengths, is given by 1^2 \times 3^2 \times \dots \times (2n-1)^2.

Exercise 6. Generalise the above two problems as follows. Let A, B \subseteq \mathbb{N} be two subsets. We wish to enumerate the number a_n of permutations of {1, 2, …, n} for which

  • the number of cycles is an element of B; and
  • the length of each cycle is an element of A.

Prove that the EGF of the sequence a_n can be expressed in the form \beta(\alpha(x)), where α(x) (resp. β(x)) is a power series which depends solely on A (resp. B). Find these power series.

Exercise 7. Prove that the number of permutations of {1, 2, …, n} containing an even number of even-length cycles is exactly \frac{n!}2 when n ≥ 2. For extra challenge, go for two proofs: one combinatorial and one via EGF.

Exercise 8. Prove that the expected number of cycles of a random permutation of {1, 2, …, n} is given by 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 n, which is very close to log(n).

Exercise 9. (New: bonus question)* A permutations p of {1, 2, …, n} is said to be alternating if p(1) < p(2), p(2) > p(3), p(3) < p(4), p(4) > p(5), etc. If f(x) denotes the EGF of the number of alternating permutations of {1, 2, …, n}, find a relation between f(x) and its derivative f’(x). Hence prove that f(x) = tan(x).

This concludes our discussion of EGF. Though the article is rather long, we’ve barely scratched the surface of what generating functions are capable of. In particular, one can look at combinatorial species, where an equality not only establishes that a_n = b_n, but an actual bijection between the associated combinatorial structures. The best way to understand this is via category theory, but that’s really another story for another day.

This entry was posted in Notes and tagged , , , , , . Bookmark the permalink.

3 Responses to Power Series and Generating Functions (IV) – Exponential Generating Functions

  1. Sukun Tarachandani says:

    Can you explain this a bit more:
    Problem1:

    If r is fixed, and an denotes the number of f, then the EGF for (an) is the product of r copies of the sequence (1, 1, 1, … ):

    • limsup says:

      Hi. I know there appears to be a huge step there, but refer to the earlier explanation where we’re trying to count the number of ways to impose a structure A on a set S. In problem 1, the structure is simply the “empty structure”, i.e. present S as it is. Hence for each set, there’s exactly one way to impose such a structure, which accounts for (1, 1, 1, …).

      For the second problem, the structure is to “throw the set away if it’s empty, otherwise present the set as it is”. So the corresponding sequence is (0, 1, 1, … ).

  2. mike says:

    great 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s