The Stars and Bars Formula

How many ways can you put n identical items into m bins?

Three stars are separated into three groups by two bars. (Created by the author with the help of Midjourney).

The Stars and Bars formula lets you calculate how many ways you can separate n identical items into m bins. The stars represent identical items, and the bars are placed between them to group them into bins.

For illustration purposes, imagine we have 10 stars and 3 bins. We can arrange the stars in a line:

10 identical stars lined up and ready to be sorted. (Image created by the author).

Now, say we separate the stars so that 2 are in bin 1, 5 are in bin 2, and 3 are in bin 3. We can put some space between our 10 stars to show the groups:

10 identical stars lined up and split into three groups. (Image created by the author).

The space is where our bars go. In this case, we only need two to separate the three groups.

10 identical stars split into three groups by vertical bars. (Image created by the author).

This is one combination, but all three bin groups can be represented with a different order of stars and bars. All we have to do to get a different…