Skip to main content
\(\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)\text{.}\) 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)\text{,}\) 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\text{.}\) 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\text{?}\) 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)\text{.}\) 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\text{.}\) 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\text{,}\) 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)\text{.}\) 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\text{,}\) 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)\text{,}\) 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)\text{,}\) 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

The compact form of the solution to Example 8.5 suggests that perhaps there is a way to come up with this answer without the use of generating functions. Thinking about such an approach would be a good way to solidify your understanding of a variety of the enumerative topics we have already covered.

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\text{,}\) and \(0\leq x_3\leq 2\text{.}\)

Solution

The invocation of partial fractions in Example 8.6 is powerful, but solving the necessary system of equations and then hoping that the resulting formal power series have expansions we immediately recognize can be a challenge. If Example 8.6 had not asked about the general case with \(n\) on the right-hand side of the equation but instead asked specifically about \(n=30\text{,}\) you might be wondering if it would just be faster to write some Python code to generate all the solutions or more interesting to huddle up and devise some clever strategy to count them. Fortunately, technology can help us out when working with generating functions. In SageMath, we can use the series() method to get the power series expansion of a given function. The two arguments to series are the variable and the degree of the terms you want to truncate. In the cell below, we ask SageMath to expand the generating function from Example 8.6 by giving us all the terms of degree at most 30 and then collapsing the rest of the series into its form of big-Oh notation, which we discard by storing the output from series() in a polynomial f(x).

If all we really want is the coefficient on a specific term, we can use the list() method to turn the polyomial into a list of its coefficients and then index into that list using standard SageMath or Python syntax:

Let's see that the answer agrees with what our formula in the solution to Example 8.6 gives us for \(n=30\text{:}\)

That's a relief, and so long as we only need a single coefficient, we're now in good shape. But what if we really need a formula for the coefficient on \(x^n\) in general? Let's see how we can use SageMath to help us with some of the other steps in Example 8.6. The first thing we'll want is the partial_fraction() method:

If you don't like the way that looks, the pretty_print() function can make it easier to read:

Up to the location of a minus sign, this is what we got by hand, but we get it much faster! From this stage, it's frequently possible to use our knowledge of certain fundamental power series that appear when doing the partial fractions expansion to come up with the general form for the coefficient on an arbitrary term of the power series. To facilitate this, we close this section with an example that illustrates how we can use solutions to counting problems we have already studied in order to figure out the coefficients on generating functions.

Example8.7

Let \(n\) be a positive integer. What is the coefficient on \(x^k\) in the generating function

\begin{equation*} \frac{1}{(1-x)^n}\text{?} \end{equation*}
Solution