0
$\begingroup$

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.

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

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?

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – ineedanewnames Jan 27 '15 at 23:58
  • $\begingroup$ @ineedanewnames: It would indeed. Or for short, $$\prod_{i=1}^n\sum_{j=1}^mx_j^i\;.$$ $\endgroup$ – Brian M. Scott Jan 28 '15 at 0:11
  • $\begingroup$ Aah I would have wrote it that way if I remembered how to write it LaTeX. Thanks :) $\endgroup$ – ineedanewnames Jan 28 '15 at 0:38
  • $\begingroup$ @ineedanewnames: You’re welcome. $\endgroup$ – Brian M. Scott Jan 28 '15 at 0:39

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.