Question

In how many ways can 25 identical donuts be distributed to four police officers so that each officer gets at least three but no more than seven donuts?

Short answer

There are then 20 ways to give 25 donuts to four police officers.

Step-by-step solution

Use Generating Function:

Generating function for the sequence\({a_0},{a_1}, \ldots ,{a_k}, \ldots \)of real numbers is the infinite series;

\(G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\)

Extended binomial theorem

\({(1 + x)^u} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}u\\k\end{array}} \right)} {x^k}\)

Each police officer receives at least 3 but at most 7 donuts each, the series representing one child should then contain only terms with a power of at least 3 and at most 7:

\({x^3} + {x^4} + {x^5} + {x^6} + {x^7}\)

There are four police officers is given by:

\[\begin{array}{c}{\left( {{x^3} + {x^4} + {x^5} + {x^6} + {x^7}} \right)^4} = {\left( {{x^3}} \right)^4}{\left( {1 + x + {x^2} + {x^3} + {x^4}} \right)^4}\\ = {x^{12}} \cdot {\left( {\sum\limits_{k = 0}^4 {{x^k}} } \right)^4}\\ = {x^{12}} \cdot {\left( {\frac{{1 - {x^5}}}{{1 - x}}} \right)^4}\\ = {x^{12}} \cdot \frac{{{{\left( {1 - {x^5}} \right)}^4}}}{{{{(1 - x)}^4}}}\\ = {x^{12}} \cdot {\left( {1 + \left( { - {x^5}} \right)} \right)^4} \cdot {(1 + ( - x))^{ - 4}}\end{array}\]

By further simplification:

\(\begin{array}{c} = {x^{12}} \cdot \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}4\\m\end{array}} \right)} {\left( { - {x^5}} \right)^m} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{ - 4}\\k\end{array}} \right)} {( - x)^k}\\ = {x^{12}} \cdot \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}4\\m\end{array}} \right)} {( - 1)^m}{x^{5m}} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{ - 4}\\k\end{array}} \right)} {( - 1)^k}{x^k}\\ = {x^{12}} \cdot \sum\limits_{m = 0}^{ + \infty } {{b_m}} {x^{5m}} \cdot \sum\limits_{k = 0}^{ + \infty } {{c_k}} {x^k}\end{array}\)

Let \({b_m} = \left( {\begin{array}{*{20}{c}}4\\m\end{array}} \right){( - 1)^m}\) and \({c_k} = \left( {\begin{array}{*{20}{c}}{ - 6}\\k\end{array}} \right){( - 1)^k}\)

The coefficient of \({x^{25}}\) which is obtained if  \(12 + 5m + k = 25\).

Since \(m\) and \(k\) are non-negative:

\(\begin{array}{c}m = 0,k = 13{\rm{ }}\\{\rm{or }}m = 1,k = 8\\{\rm{ or }}m = 2,k = 3\end{array}\)

The coefficient of \({x^{25}}\) is then the sum of the coefficients for each possible combination of \(m\) and\(k\):

\(\begin{array}{c}{a_{25}} = {b_0}{c_{13}} + {b_1}{c_8} + {b_2}{c_3}\\ = \left( {\begin{array}{*{20}{l}}4\\0\end{array}} \right){( - 1)^0}\left( {\begin{array}{*{20}{c}}{ - 4}\\{13}\end{array}} \right){( - 1)^{13}} + \left( {\begin{array}{*{20}{l}}4\\1\end{array}} \right){( - 1)^1}\left( {\begin{array}{*{20}{c}}{ - 4}\\8\end{array}} \right){( - 1)^8} + \left( {\begin{array}{*{20}{l}}4\\2\end{array}} \right){( - 1)^2}\left( {\begin{array}{*{20}{c}}{ - 4}\\3\end{array}} \right){( - 1)^3}\\ = 560 - 660 + 120\\ = 20\end{array}\)

Thus, there are then 20 ways to give 25 donuts to four police officers.