8.2: Another look at distributing apples or folders
- Page ID
- 97908
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.
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:n \geq 1\}\) with \(a_n=1\) for all \(n \geq 1\). Then the generating function for this sequence is
\(x+x^2+x^3+ \cdot \cdot \cdot = x(1+x+x^2+x^3+ \cdot \cdot \cdot) = \dfrac{x}{1-x}\)
How can we get from this fact to the question of five children? Notice what happens when we multiply
\((x+x^2+\cdot \cdot \cdot)(x+x^2+ \cdot \cdot \cdot)(x+x^2+ \cdot \cdot \cdot)(x+x^2+\cdot \cdot \cdot)(x+x^2+\cdot \cdot \cdot)\).
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,…,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
\(\dfrac{x^5}{(1-x)^5} = \dfrac{x^5}{4!} \dfrac{d^4}{dx^4}(\dfrac{1}{1-x}) = \dfrac{x^5}{4!} \displaystyle \sum_{n=0}^{\infty} n(n-1)(n-2)(n-3)x^{n-4}\)
\(= \displaystyle \sum_{n=0}^{\infty} \dfrac{n(n-1)(n-2)(n-3)}{4!} x^{n+1} = \sum_{n=0}^{\infty} \dbinom{n}{4} x^{n+1}\)
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.
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
-
In order to get at the number of baskets consisting of 20 pieces of fruit, let's solve the more general problem where each basket has \(n\) pieces of fruit. Our method is simple: find the generating function for how to do this with each type of fruit individually and then multiply them. As in the previous example, the product will contain the term \(x^n\) for every way of assembling a basket of \(n\) pieces of fruit subject to our restrictions. The apple generating function is \(x/(1−x)\), since we only want positive powers of \(x\) (corresponding to ensuring at least one apple). The generating function for pears is \((1+x+x^2+x^3)\), since we can have only zero, one, two, or three pears in basket. For oranges we have \(1/(1−x^4)=1+x^4+x^8+ \cdot \cdot \cdot \), and the unrestricted grapefruit give us a factor of \(1/(1−x)\). Multiplying, we have
\(\dfrac{x}{1-x}(1+x+x^2+x^3) \dfrac{1}{1-x^4} \dfrac{1}{1-x} = \dfrac{x}{(1-x)^2(1-x^4)}(1+x+x^2+x^3)\)
Now we want to make use of the fact that \((1+x+x^2+x^3)=(1−x^4)/(1−x)\) (by (8.1.1)) to see that our generating function is
\(\dfrac{x}{(1-x)^3} = \dfrac{x}{2} \displaystyle \sum_{n=0}^{\infty} n(n-1)x^{n-2} = \sum_{n=0}^{\infty} \dfrac{n(n-1)}{2}x^{n-1}\)
\(= \displaystyle \sum_{n=0}^{\infty} \dbinom{n}{2}x^{n-1} = \sum_{n=0}^{\infty} \dbinom{n+1}{2}x^n\).
Thus, there are \(C(n+1,2)\) possible fruit baskets containing \(n\) pieces of fruit, meaning that the answer to the question we originally asked is \(C(21,2)=210\).
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.
Find the number of integer solutions to the equation
\(x_1+x_2+x_3=n\)
(\(n \geq 0\) an integer) with \(x_1 \geq 0\) even, \(x_2 \geq 0\), and \(0 \leq x_3 \leq 2\).
- Solution
-
Again, we want to look at the generating function we would have if each variable existed individually and take their product. For \(x_1\), we get a factor of \(1/(1−x^2)\); for \(x_2\), we have \(1/(1−x)\); and for \(x_3\) our factor is \((1+x+x^2)\). Therefore, the generating function for the number of solutions to the equation above is
\(\dfrac{1+x+x^2}{(1-x)(1-x^2)} = \dfrac{1+x+x^2}{(1+x)(1-x)^2}\).
In calculus, when we wanted to integrate a rational function of this form, we would use the method of partial fractions to write it as a sum of “simpler” rational functions whose antiderivatives we recognized. Here, our technique is the same, as we can readily recognize the formal power series for many rational functions. Our goal is to write
\(\dfrac{1+x+x^2}{(1+x)(1-x)^2} = \dfrac{A}{1+x} + \dfrac{B}{1-x} + \dfrac{C}{(1-x)^2}\)
for appropriate constants, \(A, B\), and \(C\). To find the constants, we clear the denominators, giving
\(1+x+x^2 = A(1-x)^2 + B(1-x^2) + C(1+x)\).
Equating coefficients on terms of equal degree, we have:
\(1=A+B+C\)
\(1=-2A+C\)
\(1=A-B\)
Solving the system, we find \(A=1/4\), \(B=−3/4\), and \(C=3/2\). Therefore, our generating function is
\(\dfrac{1}{4} \dfrac{1}{1+x} - \dfrac{3}{4} \dfrac{1}{1-x} + \dfrac{3}{2} \dfrac{1}{(1-x)^2}\)
\(=\dfrac{1}{4} \displaystyle \sum_{n=0}^{\infty} (-1)^n x^n - \dfrac{3}{4} \sum_{n=0}^{\infty} x^n + \dfrac{3}{2} \sum_{n=0}^{\infty} nx^{n-1}\)
The solution to our question is thus the coefficient on xn in the above generating function, which is
\(\dfrac{(-1)^n}{4} - \dfrac{3}{4} + \dfrac{3(n+1)}{2}\),
a surprising answer that would not be too easy to come up with via other methods!
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, 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).
\\ SageMath Code
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:
\\Code
Let's see that the answer agrees with what our formula in the solution to Example 8.6 gives us for \(n=30\):
\\Code
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:
\\Code
If you don't like the way that looks, the pretty_print() function can make it easier to read:
\\Code
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.
Let \(n\) be a positive integer. What is the coefficient on \(x^k\) in the generating function
\(\dfrac{1}{(1-x)^n}\)?
- Solution
-
We have already encountered the case n=5 in the midst of working on Example 8.4, but there we appealed to calculus. Let's take a look at this from the perspective of just counting. The generating function \(1/(1−x)=1+x+x^2+ \cdot \cdot \cdot \) encodes the sequence for the number of ways to distribute \(n\) apples to one child. There's only one way to do that task: give the lucky kid all the apples. Multiplying together a bunch of copies of \(1/(1−x)\) then serves to increase the number of children to whom the apples are being distributed, and since each power series being multiplied starts with 1, we are in the situation where the number of apples each child receives must be nonnegative. This is therefore a problem from Section 2.5. We have \(n\) children and the coefficient on \(x^k\) is the number of ways of distributing \(k\) apples to them. This requires \(n\) artificial apples, so we distribute \(k+n\) apples, which determine \(k+n−1\) gaps and we must choose \(n−1\) of them as the locations for dividers. Therefore, we can conclude that
\(\dfrac{1}{(1-x)^n} = \displaystyle \sum_{k=0}^{\infty} \dbinom{k+n-1}{n-1}x^k = \sum_{k=0}^{\infty} \dbinom{k+n-1}{n}x^k\).
It's possible to arrive at this conclusion using techniques from calculus, but there are a lot of factorials and −1s to monitor, so this combinatorial approach may be less error prone!