Sticks and Stones

An easy way to calculate distributions

Imagine I have 10 cookies. I share them with just myself (I eat them all). There is exactly one way to do that. But if I have a friend come over, I could give myself no cookies, 1 cookie or 2 cookies or more. All in all, there are 10 ways to split 10 cookies between myself and my friend based on how many cookies I get. But suddenly, a third friend joins in… As more friends join in, it becomes harder and harder to calculate the number of ways the cookies can be distributed. You could manually count them but there is an easier method, know as sticks and stones.

If I get 3 cookies and my friend gets 5, it can be represented using a divider:

\( o o o | o o o o o \)

The cookies on the left side are mine and the ones on the left are for my friend. If another friend comes in, I add another divider. If I have 4 friends and 10 cookies that I want to divide among my self and my friends (5 people), I could represent 0 cookies for me, 3 cookies for friend A, 2 cookies for friend B, 4 cookies for friend C and 1 cookie for friend D as:

\(|ooo|oo|oooo|o\)

As you can see, there is nothing before the first divider which indicates I get 0 cookies.

Now lets try to figure out how many ways the cookies can be distributed.

In the diagram above, there are 10 slots for cookies and 4 slots for dividers. There are a total of 14 slots. Out of those, any 4 can be replaced by dividers to create a specific distribution. So we need to choose any 4 slots out of 14 to be dividers.

\(\text{Therefore there are } \binom{14}{4} = 1001 \text{ ways to distribute 10 cookies between 5 people.}\)

Imagine if we had to count that manually!

We can work out a formula from here. If n was the number of cookies and r was the number of people, we know that there are (r-1) dividers. So our formula is :

\(\binom{n+(r-1)}{r-1}\)

Oh, and did I forget to mention that this formula works on other things, not just cookies…