# Show $e^x / (1 - x)^n$ is the exponential generating function for a specified sequence

Show that $e^x/(1-x)^n$ is the exponential generating function for the number of ways to choose some subset (possibly empty) of $r$ distinct objects and distribute them into $n$ different boxes with the order in each box counted.

I know I have to use: $f(x)=e^x=\sum x^r/r!$ and $g(x)=1/(1-x)^n= \sum C(r+n-1,r)x^r$

I'm not sure where to go from here.

## 3 Answers

Consider an exponential generating function $F(x)$. The coefficient of $\frac{x^r}{r!}$ represents the number of ways to put some structure on $r$ labeled objects.

If $F$ and $G$ are two exponential generating functions, then the coefficient of $\frac{x^r}{r!}$ in $F(x) G(x)$ conveniently counts the number of ways to split $r$ labeled objects into two groups, then to put the structure counted by $F$ on the first group and structure counted by $G$ on the second group.

In this case, you need to split $r$ objects into a first group of things that are not put into any box, and a second group of things that are put into the $n$ boxes. You should find that $e^x$ counts the first structure and $\frac{1}{(1-x)^n}$ counts the second.

To see that the coefficient of $\frac{x^r}{r!}$ in $\frac{1}{(1-x)^n}$ counts the number of ways to put $r$ objects into $n$ boxes, with the order in each box mattering, you can apply the same trick. To put $r$ labeled objects in boxes in this way, you can first split the $r$ objects into $n$ groups, and then for each group count how many ways the objects can be put in the box. There are $k!$ ways to put $k$ objects into a single box, so the generating function counting this is $\sum_{k=0}^\infty k! \frac{x^k}{k!} = \frac{1}{1-x}$. Multiply this with itself $n$ times to get the function for $n$ boxes.

By way of enrichment, here is the species specification for this problem: $$\mathfrak{P}(\mathcal{Z}) \times \mathfrak{S}_{=n}(\mathfrak{S}(\mathcal{Z})).$$ The first term represents the set of values that are exempted from being distributed into the $n$ boxes and the rest describes ordered partitions being distributed into $n$ slots. These ordered partitions are sequences which we use because the order in each box matters.

Translating to generating functions we immediately obtain $$\exp(z)\times \left(\frac{1}{1-z}\right)^n.$$

E.g. there are $n!$ different sequences on $n$ labelled objects, giving the EGF operator $$\sum_{n\ge 0} n! \frac{z^n}{n!} = \frac{1}{1-z}.$$ Alternatively, the group $E_n$ containing just the identity acting on $n$ objects consists of just one permutation, producing $n!/|E_n|$ orbits, giving again $$\sum_{n\ge 0} \frac{n!}{|E_n|} \frac{z^n}{n!} = \frac{1}{1-z}.$$

For an explanation of these operators there is the Wikipedia entry for symbolic combinatorics.

• Any chance you could elaborate on your solution? – snar Jan 4 '15 at 23:57

Read generatingfunctionology by Wilf: http://www.math.upenn.edu/~wilf/DownldGF.html

It's a free download and has lots of good stuff about (what else?) generating functions.