How to Count…Better


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 12 \cdot 16 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 12 \cdot 16 boxes.  This method generalizes to more than 2 things; there are 12 \cdot 16 \cdot 8 = 1536 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 20 \cdot 19 \cdot 18 = 6840 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 \frac{6840}{6}=1140 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.

Advertisements

3 responses to this post.

  1. 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.

    Reply

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

    Reply

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

    Reply

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: