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?
Best Answer
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.)