Constrained combinatorial question using generating functions

Question

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

Answer 1

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.

Answer 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.