This post is an introduction to combinatorics, which is how to count without actually counting. For example, you have 12 pairs of shoes, 16 shirts, and 8 pairs of pants in your closet. How many different outfits can you make out of these, assuming that you have to wear a pair of shoes, a shirt, and a pair of pants (and assuming everything matches :)).

Listing out all of the combinations would be tedious! Better is to use the following method. There are 12 choices for shoes and 16 shirts. So there are shirt-pant combinations! If this is unclear, think about drawing a grid with 12 slots on one side and 16 on the other. Each box represents a different combination, and there are boxes. This method generalizes to more than 2 things; there are shoe-shirt-pant combinations. Don’t try listing that out 😛

Now suppose that there are 20 people in a class, and you need to pick a class president, vice president, and secretary. How many ways are there to do this? This is an application of our method. It doesn’t matter, but say you pick the president first. There are 20 choices for the president. Now, the vice president can be anyone except the person who you just designated as president, so there are 19 choices. Lastly, there are 18 choices for secretary. Following our method, we get that there are different combinations of people for the three positions.

Now I’ll change the problem a bit. There are 20 people in the class and you need to choose 3 class representatives from them. This may seem the same as the previous problem, except that in this case if Alison, Bob, and Charlotte are representatives that’s the same as Bob, Alison, and Charlotte being representatives, whereas in the previous problem order mattered, since Alison being president and Bob being vice president was different from Bob being president and Alison being vice president. Order is a very important factor to consider in combinatorics. So what do we do? Well, we can still use the above method, but keep in mind that we counted all arrangements of the students Alison, Bob, and Charlie as different.

How many arrangements are there? Well, there’s 1. A,B,C 2. A,C,B 3. B,A,C 4. B,C,A, 5. C,A,B 6. C,B,A. So 6 arrangements. Therefore, if we take our answer from before and *divide* by 6, that will correct for our over-counting. So there are ways to choose 3 representatives!

Being able to count things in this way is essential for calculating the probability of events happening, which is extremely useful in playing games and analyzing real-world events. Lastly, if you like this and want to see more, this and much more is covered in the Art of Problem Solving’s Introduction to Counting and Probability textbook. See the resource page on the left side for a link to the Art of Problem Solving website and more.

Posted by Ravi Boppana on September 19, 2010 at 9:31 am

Besides their book on Counting, the Art of Problem Solving

has a cool online system called Alcumus for learning how to solve Counting problems. It’s free! Here is the web site:

http://www.artofproblemsolving.com/Alcumus/Introduction.php.

You’ll need to register and be logged in to use Alcumus.

Posted by meenamathgirl on September 19, 2010 at 10:14 am

Right I totally forgot about that. Adding it to the resource page now.

Posted by 2010 in review « The Power of Proofs on January 2, 2011 at 10:04 am

[…] How to Count…Better September 2010 2 comments and 1 Like on WordPress.com, 5 […]