2

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! :)

rannoudanames
  • 1,133

2 Answers2

2

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.

WaveX
  • 5,440
  • Why are we interested in the coefficient for $t^{25}$? How would I efficiently find it in the example above? – rannoudanames Feb 22 '18 at 21:18
  • @rannoudanames Are you asking for Wolfram Alpha's syntax? – Antoni Parellada Feb 22 '18 at 21:20
  • 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. – Antoni Parellada Feb 22 '18 at 21:23
  • @AntoniParellada no, more so how would one obtain that using pen and paper. – rannoudanames Feb 22 '18 at 21:23
  • @rannoudanames Here is where I got stuck in the past... You get the GF, but eventually, either you need a lot of paper, time and patience, or you end up resorting to a computer calculation. I don't mean to be provocative, and would very much like to get someone with a different take to explain, but I'm just sharing the conclusion I got to after pondering the same question. – Antoni Parellada Feb 22 '18 at 21:27
  • @AntoniParellada it does seem to be a challenging task – rannoudanames Feb 22 '18 at 21:29
  • 1
    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 :) – WaveX Feb 22 '18 at 21:39
  • @rannoudanames Interesting response... I thought your question wasn't rhetorical. Please let me know how long it took you doing it with pen and paper. I was waiting for a few long seconds on my computer (slow CPU)... :-) – Antoni Parellada Feb 22 '18 at 21:41
  • @rannoudanames Here is the output: $1 + 7 x + 28 x^2 + 84 x^3 + 210 x^4 + 462 x^5 + 924 x^6 + 1716 x^7 + 3003 x^8 + 5005 x^9 + 8008 x^{10} + 12375 x^{11} + 18557 x^{12} + 27104 x^{13} + 38676 x^{14} + 54054 x^{15} + 74151 x^{16} + 100023 x^{17} + 132880 x^{18} + 174097 x^{19} + 225225 x^{20} + 288002 x^{21} + 364364 x^{22} + 456456 x^{23} + 566643 x^{24} + 697521 x^{25}$. – Antoni Parellada Feb 22 '18 at 21:50
  • @AntoniParellada Thank you! I will continue on figuring out general methods to solve for such problems without lengthy computations. (hopefully find something interesting!) – rannoudanames Feb 22 '18 at 21:55
2

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.

Markus Scheuer
  • 108,315