Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes

Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes when $b_1<b_2\le 4$, where $b_1,b_2$ are the numbers of objects in boxes $1$ and $2$, respectively.

I understand that boxes $3, 4$, and $5$ will all just have the fundamental exponential generating function and that their combined generating function will be $e^{3x}$. What I don't understand is the first two boxes with the equality parameter given.

Can someone explain how to do this?

2 Answers

Here is a very painstaking approach that may help you to see exactly what’s going on.

The possible values of $b_1$ are $0,1,2$, and $3$, so far starters we try

$$1+x+\frac{x^2}2+\frac{x^3}6$$

to account for $b_1$. Similarly, the possible values of $b_2$ are $1,2,3$, and $4$, so we try

$$y+\frac{y^2}2+\frac{y^3}6+\frac{y^4}{24}$$

to account for $b_2$. I’m using different indeterminates for now, because at this point I still need to keep the $b_1$ and $b_2$ contributions separate.

The product of these polynomials is

\begin{align*} &y+\frac{y^2}2+\frac{y^3}6+\frac{y^4}{24}+\\ &xy+\frac{xy^2}2+\frac{xy^3}6+\frac{xy^4}{24}+\\ &\frac{x^2y}2+\frac{x^2y^2}4+\frac{x^2y^3}{12}+\frac{x^2y^4}{48}+\\ &\frac{x^3y}6+\frac{x^3y^2}{12}+\frac{x^3y^3}{36}+\frac{x^3y^4}{144}\;; \end{align*}

however, we don’t want the terms in $x^ky\ell$ with $k\ge\ell$, since they correspond to having $b_1\ge b_2$. After we throw them away, we have

$$y+\frac{y^2}2+\frac{y^3}6+\frac{y^4}{24}+\frac{xy^2}2+\frac{xy^3}6+\frac{xy^4}{24}+\frac{x^2y^3}{12}+\frac{x^2y^4}{48}+\frac{x^3y^4}{144}\;.$$

Now replace $y$ by $x$, collect terms, and adjust the denominators to match the exponents to get

$$\frac{x}{1!}+\frac{x^2}{2!}+\frac{4x^3}{3!}+\frac{5x^4}{4!}+\frac{15x^5}{5!}+\frac{15x^6}{6!}+\frac{35x^7}{7!}\;,$$

which is the egf for boxes $1$ and $2$ combined. Multiply this by $e^{3x}$, and you’re done.

(And now that I’ve written this, I see that Markus has given you the abbreviated version of it.)

• Nonetheless +1 for your answer. I appreciate the thoughtfully and helpful explanations you typically provide. – Markus Scheuer Apr 2 '16 at 21:29
• thanks for the detailed explanation. My reputation score isn't high enough yet for my upvote to show. – BrianW Apr 2 '16 at 21:32
• @BrianW: You’re welcome. – Brian M. Scott Apr 2 '16 at 21:34
• @Markus: Arrgh! I sure did. Thanks. – Brian M. Scott Apr 2 '16 at 22:18
• @Markus: Thanks! Yes, they both look good now. – Brian M. Scott Apr 2 '16 at 22:43

Three boxes have no restrictions with respect to the objects which results in $e^{3x}$. The restriction $b_1<b_2\leq 4$ of the other objects together with the objects of the three boxes is encoded as \begin{align*} e^{3x}&\left(\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\right)+x\left(\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\right)\right.\\ &\quad+\left.\frac{x^2}{2!}\left(\frac{x^3}{3!}+\frac{x^4}{4!}\right) +\frac{x^3}{3!}\left(\frac{x^4}{4!}\right)\right)\\ &=e^{3x}\left(\frac{x}{1!}+\frac{x^2}{2!}+\frac{4x^3}{3!}+\frac{5x^4}{4!}+ \frac{15x^5}{5!}+\frac{15x^6}{6!}+\frac{35x^7}{7!}\right) \end{align*}

• It looks like you broke it into cases of what box 1 could contain, specifically 0, 1, 2, or 3 objects. From there you took all possible sizes of box 2 given the different sizes of box 1. Is this correct? For example, $(1+x)$ means there is either 0 or 1 object in box one? – BrianW Apr 2 '16 at 21:17
• @BrianW: Correct. – Markus Scheuer Apr 2 '16 at 21:19
• Can you explain why your function has values of $x^7$ and Brian Scott's does not? – BrianW Apr 2 '16 at 21:35
• @BrianW: Look at the last term $\frac{x^3y^4}{24}$ in Brians answer. What do you think ...? – Markus Scheuer Apr 2 '16 at 21:39
• @BrianM.Scott and Markus, I checked your final answers to what I came up with doing simple combinatorical arguments and I came up with the answers you now have. Thanks again for your help! – BrianW Apr 2 '16 at 22:49