An introductory stars and bars problem

Yesterday a counting problem from my son’s math team homework gave him a little trouble. The problem went something like this:

There are 5 different types of fasteners and you need to buy 10 total. If you need to buy at least one of each, how many different ways can you do it?

First we talked about the problem and got their initial thoughts. Then I introduced the stars and bars counting idea:

Next I tried to go through a few more examples by changing the numbers a little. The main ideas seemed a little confusing to the boys and I’d hoped a few extra examples would help. Unfortunately things weren’t going so well.

The last example in the prior video confused my younger son, so I moved on to the next video to talk about that example in more detail. By the end of this example I hoped that the general idea had sunk in, but there was still a little confusion.

So, we talked through the problem a few more times. Now the ideas seemed to be sinking in. IF you have N groups of objects (in the original problem 5 fasteners) and you have to pick M total objects (in the original problem we were trying to pick 5 fasteners) you can represent the problem with M stars and N – 1 bars. So the total number of different ways to make the selections are (M + N – 1) “choose” M or, alternately, (M + N – 1) choose (N – 1).

Not all of our projects go super well. Here my mistake was thinking that I could introduce an advanced concept and the boys would immediately understand it. I feel like the ideas here are definitely within their grasp and will probably spend a bit more time this weekend covering the concept. Hopefully a few more examples will do the trick. Stars and Bars.jpg

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s