Another 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 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 , 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 . 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 could revisit an example from 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.

The compact form of the solution to 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.

The invocation of partial fractions in 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 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 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).

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

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.