How many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie?

And now for some solutions to the cookie distribution problem. I’m actually going to describe four different methods of solution, and thereby (re)discover some nice combinatorial identities along the way. This is what I love about combinatorics—you discover all this rich structure just by coming up with different ways to count things!

Solution 1: Cookies and Fences

The first solution, as described in a comment by Mike, consists in considering permutations of cookies and fences.

If we set up the cookies in a row, we can use four fences to separate them into five sections; the first student will get the first section of cookies, the second student will get the second section, and so on. In the example above, student A gets one cookie, student B gets two, student C doesn’t get any, and students D and E get three and four, respectively. It’s easy to see that every distribution of cookies corresponds to an arrangement of fences, and vice versa. So, how many ways are there to arrange the fences? Think of it this way: we have fourteen “slots”, and into each slot we can put either a cookie or a fence. Choosing a distribution is just choosing in which of the fourteen slots to put the four fences, and there are ways to choose four out of fourteen slots. (If you don’t know about binomial coefficients, you can read about them here.) Incidentally, this is also the number of ways to distribute four fences to eleven students; just use the cookies to divide the fences into eleven sections (most of which will, of course, be empty). Although I have no idea why students would want fences.

This can be easily generalized: the above argument shows that there are ways to distribute c cookies to s students.

So, the problem is solved, right? What more can there be to say about it?

…plenty! This is a nice elegant solution, but it takes some cleverness (and/or luck, and/or experience with this sort of problem) to see it, and in fact it isn’t the first solution I came up with. Looking at some different methods of solution will also illuminate some of the rich structure of binomial coefficients.

Solution 2: Don’t Be So Mean

It seems mean that sometimes some students don’t get any cookies at all. Wouldn’t it be much nicer if every student got at least one cookie (even if they still might be distributed unevenly)? The key insight, as pointed out by Jonathan, is this: the number of ways to distribute ten cookies to five students is the same as the number of ways to distribute fifteen cookies to five students in such a way that each student gets at least one cookie.

Why is this? Well, suppose you have distributed fifteen cookies to five students so that each student has at least one. Now take one cookie away from each student—and you have now distributed ten cookies to five students. Conversely, if you have distributed ten cookies to five students somehow, if you now give each student an extra cookie, you have distributed fifteen cookies and each student has at least one. Each distribution of ten cookies corresponds to precisely one distribution of fifteen cookies where each student gets at least one, and vice versa, so counting one is the same as counting the other. Now, how many ways are there to distribute fifteen cookies like this? We can line the cookies up and imagine choosing points at which to divide them; to divide them into five groups, we have to choose exactly four out of the fourteen possible places to divide the cookies. (There is at least one cookie between any two dividing points, which means that each student has to get at least one cookie.)

The above illustration shows a distribution in which students A, B, C, D, and E get two, three, one, four, and five cookies respectively. Note that this is the distribution of fifteen cookies that corresponds to the distribution of ten cookies illustrated with the fences previously.

So, the number of ways to distribute fifteen cookies to five students so that each gets at least one is ; more generally, the number of ways to distribute c cookies to s students so each gets at least one is . Also, the total number of ways to distribute c cookies to s students is the same as the number of ways to distribute c+s cookies to s students so that each gets at least one.

Solution 3: One at a time, please!

Another way of approaching the problem comes courtesy of meichenl. To distribute cookies to s students, we first have to give some number of cookies to the first student; we can give her anywhere from zero to ten cookies. If we give her k cookies, there are c – k cookies left to distribute to the other s – 1 students. If we let stand for the number of ways of Distributing c cookies to s students, we can write this observation as

That is, we split the distribution up into cases based on how many cookies we give to the first student; in each case we’ve reduced the problem to a simpler distribution problem. Adding everything up, we get the above recurrence—we’ve defined recursively, that is, in terms of itself. This definition actually gets off the ground because we can identify some base cases, that is, simple situations in which we know the answer without breaking things down further. In particular, for any s (there’s only one way to distribute zero cookies—namely, to give zero cookies to each student), and for any c (there’s only one way to distribute cookies to a single lucky student!).

So, once we have this recurrence, what do we do with it? We can use it for direct calculation, as Mark James apparently did; he also used the recurrence in a computer program to print all the distributions. As observed by Daniel Klein, this sort of recurrence is also perfectly suited for a programming technique called dynamic programming; it’s easy to turn this recurrence into a computer program to compute for any values of c and s (although in this particular case, as we’ve seen, there are more efficient ways to compute ).

But here’s another interesting thing: we already know what is, from solutions 1 and 2: it’s So if we substitute this into the above recurrence, we get

If we substitute d + 1 in place of s – 1 everywhere, we can make this a little nicer without changing anything (d is just a new variable I made up, it doesn’t stand for anything in particular):

We’ve discovered an identity involving sums of binomial coefficients! Neat! Now, you might think, “OK, let’s prove this by induction.” But we need do no such thing. We have already argued that the expression on the left and the expression on the right count the same things—so they must be equal! This is the epitome of a combinatorial proof: to show that two things are equal, just show that they represent two different ways of counting the same thing.

Solution 4: How mean do you want to be?

The last solution (at least, the last solution I will discuss in this post!) comes courtesy of Dave. Instead of breaking the distribution into cases according to how many cookies we give to the first student (as in the previous solution), we can break it into cases according to how many students get any cookies: we can give all the cookies to one student, or give them all to two students, or three, and so on.

The first case is easy: if we give all the cookies to one student, there are 5 ways to choose which student to give the cookies to, and only one way to give them the cookies. What if we give all the cookies to two students? Well, there are ways to choose which two students get cookies. Now we want to distribute the ten cookies to these two students in such a way that each student gets at least one cookie (otherwise we are back in the first case). As previously noted in solution 2, there are ways to do this. If three students get cookies, there are ways to choose the three students, and ways to distribute the cookies, and so on. Generalizing, we see that

Egads! We’ve discovered another combinatorial identity, this one involving a sum of products of binomial coefficients!

There’s yet another method of solution I’m aware of—the theory of combinatorial species and generating functions—but that can wait for another post, I think we’ve had quite enough combinatorial goodness for one day!

39.953605 -75.213937