# Generating Functions for Fruits

Find a generating function $(x_1, x_2, ..., x_m)$ whose coefficients of $x_1^{r_1} x_2^{r_2}\ldots x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ fruits of type $1$, $r_2$ fruits of type $2$, ... $r_m$ fruits of type $m$ if:

Person $i$ picks up to $i$ fruits of exactly one type.

Workings:

I'm going to simplify down first and give the answer in general later.

So suppose that $n = 3$ and $m = 4$

So Person 1 can pick 1 fruit from the 4 different types of fruit but only from the one type

This is the generating function

$(1+x)(1+x)(1+x)(1+x)$

Person 2 can pick 2 fruits from the 4 different types of fruits but can not mix the types of fruits

$(1+x^2)(1+x^2)(1+x^2)(1+x^2)$

Person 3 can pick 3 fruits from the 4 different types of fruits but can not mix the types of fruits

$(1+x^3)(1+x^3)(1+x^3)(1+x^3)$

These are picked independently so can combined to one generating function:

$(1+x)(1+x)(1+x)(1+x)(1+x^2)(1+x^2)(1+x^2)(1+x^2)(1+x^3)(1+x^3)(1+x^3)(1+x^3)$

And rearranged for each type of fruit:

$[(1+x)(1+x^2)(1+x^3)][(1+x)(1+x^2)(1+x^3)][(1+x)(1+x^2)(1+x^3)][(1+x)(1+x^2)(1+x^3)]$

Now I'm not to sure on what to do.

Any help will be appreciated.

• Do you mean $x_1^{r_1},x_2^{r_2},\dots,x_m^{r_m}$? – Thomas Andrews Jan 27 '15 at 23:40
• @ThomasAndrews Yes I do. Sorry about that. – ineedanewnames Jan 27 '15 at 23:48

Since you have to keep track of the $m$ kinds of fruit separately, you should not be using a single indeterminate $x$: as the problem says, you should have indeterminates $x_1,x_2,\ldots,x_m$, one for each kind of fruit.

Let’s look at the $i$-th person. That person can pick $i$ of type $1$: that’s represented by $x_1^i$. Or the $i$-th person can pick $i$ of type $2$: that’s represented by $x_2^i$. In fact, for each type $k$, the $i$-th person can pick $i$ of that type, an outcome represented by $x_k^i$. Any one of these outcomes is possible, and nothing else, so the $i$-th person’s generating function is simply $x_1^i+x_2^i+\ldots+x_m^i$. Notice that there is no $1$ term: that would be $1x_1^0x_2^0\ldots x_m^0$, representing a choice of no type $1$ fruits, no type $2$ fruits, ..., and no type $m$ fruits, and that’s not a possible choice for any of the people involved.

Now you need to combine the generating functions for the $n$ individuals into a single one. Their choices are independent: no matter which kind of fruit person $i$ chooses, person $j$ can choose any of the $m$ types. Suppose that we had just two people; I claim that the product

$$(x_1+x_2+\ldots+x_m)(x_1^2+x_2^2+\ldots+x_m^2)$$

of their generating functions describes the possible outcomes of their choices. If you multiply it out, you’ll see that you get $x_k^3$ for $k=1,\ldots,m$, and you get all of the possible terms $x_kx_\ell^2$ with $k\ne\ell$. A term $x_k$ indicates that $3$ fruits of type $k$ have been taken; that’s the outcome when person $1$ and person $2$ both choose type $k$, and it comes from multiplying their individual terms $x_k$ and $x_k^2$. When $k\ne\ell$ the term $x_kx_\ell^2$ indicates that one fruit of type $k$ and $2$ of type $\ell$ were chosen, obviously by person $1$ and person $2$, respectively; it comes from multiplying their individual terms $x_k$ and $x_\ell^2$.

Can you see how to generalize this to $n$ people to get the generating function that you want?

• Would that mean the generating function would be $(x_1 + x_2 + + ... + x_m)(x_1^2 + x_2^2 + ... x_m^2)...(x_1^n + x_2^n + ... + x_m^n)$ – ineedanewnames Jan 27 '15 at 23:58
• @ineedanewnames: It would indeed. Or for short, $$\prod_{i=1}^n\sum_{j=1}^mx_j^i\;.$$ – Brian M. Scott Jan 28 '15 at 0:11
• Aah I would have wrote it that way if I remembered how to write it LaTeX. Thanks :) – ineedanewnames Jan 28 '15 at 0:38
• @ineedanewnames: You’re welcome. – Brian M. Scott Jan 28 '15 at 0:39