cookies and coffees method for counting

author: Cory Simon

A dog 🐶, bear 🐻, and monkey 🐒 go out to eat together at a restaurant. For desert, the server generously brings five cookies (🍪’s). How many different ways can the five cookies be distributed among the three diners? The cookies are indistinguisable.

For example, one outcome is:

🐶: 🍪 🍪

🐻:

🐒: 🍪 🍪 🍪

The answer to this combinatorics problem is readily apparent once cast into the stars and bars framework. We use cookies and coffees to illustrate the idea more memorably.

To easily visualize the above distribution of cookies among the diners, the 🐶 arranges the five cookies along a line on the table

🍪 🍪 🍪 🍪 🍪

then places a coffee (☕) between each diner’s allocation of cookies, effectively partitioning the cookies into three bins:

🍪 🍪 ☕ ☕ 🍪 🍪 🍪

In this cookies and coffees representation of the distribution of cookies among the diners, the cookies:

• to the left of the left-most ☕ belong to 🐶
• between the two ☕’s belong to 🐻 (none in this instance)
• to the right of the right-most ☕ belong to 🐒

We only need two coffees to denote the partition of cookies among the three diners– one less than the number of diners.

That the order of partitions go from 🐶, 🐻, to 🐒 (left to right) is arbitrary and, for counting the possible distributions, immaterial.

Two important points are:

• each possible distribution of the cookies among the diners is uniquely represented by an arrangement of these cookies and coffees.
• each arragement of cookies and coffees represents a unique distribution of the cookies among the diners.

i.e., the mapping from an arrangement of cookies and coffees to a distribution of cookies among the diners is a bijection. Therefore, the number of ways to distribute the cookies among the diners is equal to the number of ways to arrange the cookies and coffees. Importantly, we treat the cookies as indistinguishble, and same for the coffees.

Thus, the number of possible distributions of cookies to the diners is:

$$\dfrac{7!}{5!2!}=21$$

The $(5+2)!=7!$ in the numerator is the number of ways to permute the cookies and coffees if they were distinguishable. The $5!$ and $2!$ in the denominator account for the indistinguishability of the cookies and coffees, respectively.

In general, the number of ways to distribute $c$ cookies to $d$ diners is:

$$\dfrac{(c + d-1)!}{c! (d-1)!}$$

because we need $d-1$ coffees to indicate the partitioning of the row of cookies.