Stars & Bars Method For Counting Problems [Math]

12 days ago

Hi there. In this math post I cover this Stars & Bars Method for counting and arrangement problems. This is something I came across while helping out a student. My permutations & combinations knowledge is okay but it is not my main specialty. I did manage to learn this fast to help out someone.

Image Source

Food Question

Here is the question I had from the student. There are 3 oranges, 4 apples and 5 bananas available to choose from. You choose three fruits from the 12 available. How many combinations are possible from choosing three fruits?

The scenario and the question seems simple. However getting the answer is not that easy. From the 3 fruits you can have all 3 fruits being oranges. That is one way. If you have one orange then you can have two apples OAA or one orange and two bananas OBB. There is also one orange, one apple and one banana.

Listing all the combinations is one way to do this. The thing is that it takes long. A more mathematical approach is faster and more preferred.

Image Source

Stars & Bars Method For Solution

There is this method called the Stars & Bars method when it comes to organized counting. In the fruits problem we have 3 types of fruits. With the stars and bars method we would have two bars. The setup would be Oranges|Apples|Bananas. The bars separate the fruit types.

As the question mentions choosing 3 fruits you would have 3 stars. If you have the case of all 3 fruits being oranges, the stars and bars representation would be:

***| |

The stars represent the fruits in the oranges section. In the middle it is blank as we did not choose any apples. The blank on the right represents no bananas chosen.

For the case of one orange, one apple and one banana the representation would be

*|*|*

One star is in each group.

If you have one banana and two apples you have this representation.

|**|*

Connecting Stars & Bars With Choose Notation

You can connect stars & bars with the choose notation. What I mean by choose is something like 3C2 or 3 Choose 2.

In the stars and bars method we have 2 bars and 3 stars. This is a total of 5. With choose here think of it as how many ways of placing 3 stars out of 5 spots. This is 5 choose 3 which is: