2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.)

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

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*}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – BrianW Apr 2 '16 at 21:17
  • $\begingroup$ @BrianW: Correct. $\endgroup$ – Markus Scheuer Apr 2 '16 at 21:19
  • $\begingroup$ Can you explain why your function has values of $x^7$ and Brian Scott's does not? $\endgroup$ – BrianW Apr 2 '16 at 21:35
  • $\begingroup$ @BrianW: Look at the last term $\frac{x^3y^4}{24}$ in Brians answer. What do you think ...? $\endgroup$ – Markus Scheuer Apr 2 '16 at 21:39
  • 1
    $\begingroup$ @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! $\endgroup$ – BrianW Apr 2 '16 at 22:49

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.