0
$\begingroup$

In my Discrete Math textbook there's the following problem: "How many possibilities there exist to distribute 25 objects of the same kind into 7 different bins, if in the first bin there can be no more than 10 objects?"

A solution using generating functions must be found. The solution uses the following generating function:

$$(1+x+x^2+x^3+x^4+...+x^{10})(1+x+x^2+x^3+...)^6$$

The textbook then goes on suggest this formal power series in order to find the coefficient of $x^{25}$: $$f(x)=\frac{1-x^{11}}{1-x}*\frac{1}{1-x^6}$$

I understand completely the first part:

$$\frac{1-x^{11}}{1-x}$$

I don't understand why this series

$$\frac{1}{1-x^6}$$ was chosen for the other 6 bins. The amount of objects can't be over 25 so we need to choose a power series which works for finite number of objects (the solution needs to be a natural number (including $0$)) which is again this:

$$\sum_{i=0}^n x^i = \frac{1-x^{n+1}}{1-x}$$

Can you please explain why?

$\endgroup$
  • 2
    $\begingroup$ The second factor should be $\left(\frac1{1-x}\right)^6=\frac1{(1-x)^6}$; the exponent is in the wrong place. $\endgroup$ – Brian M. Scott Aug 1 '16 at 20:43
2
$\begingroup$

The second factor should be $\left(\frac1{1-x}\right)^6=\frac1{(1-x)^6}$; the exponent is in the wrong place.

We want a generating function such that the coefficient of $x^n$ is the number of possibilities for distributing $n$ objects of the same kind into $7$ bins, with a limit of $10$ in the first bin. Thus, we need to allow for any number of objects, not just $25$. Each of the six bins whose contents are not limited can therefore contain any non-negative number of objects up to $n$ for any given $n$, and we have to allow for all of these possibilities. Of course when we compute the coefficient of $x^{25}$ in order to answer the specific question for $25$ objects, the terms in $x^k$ with $k>25$ won’t contribute anything.

$\endgroup$

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.