2
$\begingroup$

Let me first give a few examples:

How many ways are there to select 25 toys from 7 types with between 2 to 6 of each type.

How many ways can we distribute 25 identical balls to 7 boxes where the first box can have at most 10 balls.

There seems to be a method to solve this sort of question using generating functions. The set up for the second question is as follows: $(1+t+...+t^{10})(1+t+...) = \frac{1}{(1-t)^7} - \frac{t^4}{(1-t)^7}$ and from here I get confused as to how we obtain our answer.

I would love some clarification on this concept and some help to finish the example started above!

Thank you! :)

$\endgroup$
2
$\begingroup$

In order to obtain the coefficient it is convenient to use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ in a series.

We consider the second example and obtain \begin{align*} \color{blue}{[t^{25}]}&\color{blue}{(1+t+t^2+\cdots+t^{10})(1+t+t^2+\cdots)^6}\\ &=[t^{25}]\frac{1-t^{11}}{1-t}\left(\frac{1}{1-t}\right)^6\tag{1}\\ &=\left([t^{25}]-[t^{14}]\right)\frac{1}{(1-t)^7}\tag{2}\\ &=\left([t^{25}]-[t^{14}]\right)\sum_{j=0}^\infty \binom{-7}{j}(-t)^j\tag{3}\\ &=\left([t^{25}]-[t^{14}]\right)\sum_{j=0}^\infty \binom{j+6}{6}t^j\tag{4}\\ &\,\,\color{blue}{=\binom{31}{6}-\binom{20}{6}=697\,521}\tag{5}\\ \end{align*} in accordance with the result given by Wolfram Alpha.

Comment:

  • In (1) we apply the geometric series formula.

  • In (2) we use the linearity of the coefficient of operator and apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$.

  • In (3) we apply the binomial series formula.

  • In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

  • In (5) we select the coefficients accordingly.

$\endgroup$
2
$\begingroup$

You have it started correctly

We want the coefficient of $t^{25}$ of the expanded function: $$(1+t+t^2 +\cdots + t^9+t^{10})(1+t+t^2+\cdots)^6$$

This is because the first box is allowed to have up to $10$ balls in it, while there are no restrictions for the other $6$ boxes.

WolframAlpha shows this to be $697521$ ways for $25$ balls.

To see that this generating function is set up right, lets take a step back and check for a smaller number, like having the same number of boxes and the same constraint for the first box, but now lets say we only have $2$ balls. (Yes the constraint doesn't apply here but we can still check that the generating function gives the appropriate result)

The balls can either both be in the same box, or be in separate boxes, so that would be: $$\binom72 + 7 = 28 $$

The coefficient of the generating function for $t^2$ is indeed $28$, so this confirms that our generating function is set up correctly.

$\endgroup$
  • $\begingroup$ Why are we interested in the coefficient for $t^{25}$? How would I efficiently find it in the example above? $\endgroup$ – rannoudanames Feb 22 '18 at 21:18
  • $\begingroup$ @rannoudanames Are you asking for Wolfram Alpha's syntax? $\endgroup$ – Antoni Parellada Feb 22 '18 at 21:20
  • $\begingroup$ The specific command would be, SeriesCoefficient[(1+x+x^2+x^3+...)^6 * (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^10),[x,0,25]. If I didn't misunderstand you, I went through the same question (the coding) here. +1 to WaveX. $\endgroup$ – Antoni Parellada Feb 22 '18 at 21:23
  • $\begingroup$ @AntoniParellada no, more so how would one obtain that using pen and paper. $\endgroup$ – rannoudanames Feb 22 '18 at 21:23
  • 1
    $\begingroup$ If our series is "simple" in the fact that there aren't any parts of it that extend infinitely, then all we need to do is expand the function. Obviously with larger sized functions like this, it isn't necessarily something you would want to do on pen and paper. When they do extend infinitely, however, like this example, then we would need to use Power Series from calculus to expand the function, which again may or may not be easy to do by hand. Sometimes it's better off to just let the technology do the work :) $\endgroup$ – WaveX Feb 22 '18 at 21: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.