3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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.

$\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.