\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section8.2Another look at distributing apples or folders

A recurring problem so far in this book has been to consider problems that ask about distributing indistinguishable objects (say apples) to distinct entities (say children). We started in Chapter 2 by asking how many ways there were to distribute \(40\) apples to \(5\) children so that each child is guaranteed to get at least one apple and saw that the answer was \(C(39,4)\). We even saw how to restrict the situation so that one of the children was limited and could receive at most \(10\) apples. In Chapter 7, we learned how to extend the restrictions so that more than one child had restrictions on the number of apples allowed by taking advantage of the Principle of Inclusion-Exclusion. Before moving on to see how generating functions can allow us to get even more creative with our restrictions, let's take a moment to see how generating functions would allow us to solve the most basic problem at hand.

Example8.4

We already know that the number of ways to distribute \(n\) apples to \(5\) children so that each child gets at least one apple is \(C(n-1,4)\), but it will be instructive to see how we can derive this result using generating functions. Let's start with an even simpler problem: how many ways are there to distribute \(n\) apples to one child so that each child receives at least one apple? Well, this isn't too hard, there's only one way to do it—give all the apples to the lucky kid! Thus the sequence that enumerates the number of ways to do this is \(\{a_n\colon n\geq 1\}\) with \(a_n=1\) for all \(n\geq 1\). Then the generating function for this sequence is \begin{equation*} x+x^2+x^3+\cdots = x(1+x+x^2+x^3+\cdots) = \frac{x}{1-x}. \end{equation*} How can we get from this fact to the question of five children? Notice what happens when we multiply \begin{equation*} (x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots) (x+x^2+\cdots). \end{equation*}

To see what this product represents, first consider how many ways can we get an \(x^6\)? We could use the \(x^2\) from the first factor and \(x\) from each of the other four, or \(x^2\) from the second factor and \(x\) from each of the other four, etc., meaning that the coefficient on \(x^6\) is \(5 = C(5,4)\). More generally, what's the coefficient on \(x^n\) in the product? In the expansion, we get an \(x^n\) for every product of the form \(x^{k_1}x^{k_2}x^{k_3}x^{k_4}x^{k_5}\) where \(k_1+k_2+k_3+k_4+k_5 = n\). Returning to the general question here, we're really dealing with distributing \(n\) apples to \(5\) children, and since \(k_i> 0\) for \(i=1,2,\dots,5\), we also have the guarantee that each child receives at least one apple, so the product of the generating function for one child gives the generating function for five children.

Let's pretend for a minute that we didn't know that the coefficients must be \(C(n-1,4)\). How could we figure out the coefficients just from the generating function? The generating function we're interested in is \(x^5/(1-x)^5\), which you should be able to pretty quickly see satisfies \begin{align*} \frac{x^5}{(1-x)^5} \amp = \frac{x^5}{4!}\frac{d^4}{dx^4}\left(\frac{1}{1-x}\right) = \frac{x^5}{4!}\sum_{n=0}^\infty n(n-1)(n-2)(n-3)x^{n-4}\\ \amp =\sum_{n=0}^\infty \frac{n(n-1)(n-2)(n-3)}{4!}x^{n+1} = \sum_{n=0}^\infty \binom{n}{4}x^{n+1}. \end{align*} The coefficient on \(x^n\) in this series \(C(n-1,4)\), just as we expected.

We could revisit an example from Chapter 7 to see that if we wanted to limit a child to receive at most \(4\) apples, we would use \((x+x^2+x^3+x^4)\) as its generating function instead of \(x/(1-x)\), but rather than belabor that here, let's try something a bit more exotic.

Example8.5

A grocery store is preparing holiday fruit baskets for sale. Each fruit basket will have \(20\) pieces of fruit in it, chosen from apples, pears, oranges, and grapefruit. How many different ways can such a basket be prepared if there must be at least one apple in a basket, a basket cannot contain more than three pears, and the number of oranges must be a multiple of four?

Solution
Example8.6

Find the number of integer solutions to the equation \begin{equation*} x_1 + x_2 + x_3 = n \end{equation*} (\(n\geq 0\) an integer) with \(x_1 \geq 0\) even, \(x_2\geq 0\), and \(0\leq x_3\leq 2\).

Solution