GMAT Combinatorics 1.0: Introduction

This is an introductory post on combinatorics - the art of counting. Combinatorics is one of the most difficult parts of the GMAT because it is not part of the standard American high school curriculum. With many other troubling types of problems, such as rate questions, fraction / decimal / percent problems, etc., a bit of review and a lot of practice will do the trick, but, in general, to get a handle on combinatorics problems students have to learn something new.

My approach to combinatorics is to emphasize a fundamental concept that can be used, with a bit of creativity of course, to solve just about any combinatorics problem. However, if you've had some course-work in basic probability and have some vague memory of the difference between combinations and permutations, then this may not be the most efficient approach for you. I'll try to note standard procedures and formulas alongside my more unorthodox approach. In later posts I'll also provide some examples of the links between combinatorics and probability.

The Fundamental Principle of Counting

Suppose that some task involves a sequence of choices. For example, I'm at a cafe. Before I started writing this post, my 'task' was ordering a drink. To order the drink, I had to make a series of choices. Hot or cold. Coffee or tea. Small, medium, or large. Latte, cappuccino, macchiato, etc. Whole, two-percent, or skim. The medium skim latte (with an extra shot) represents one of many possible drinks... How many drinks are possible?

The fundamental principle of counting states that if a task requires k choices where choice one can be made among [latex]n_1[/latex] options, choice two among [latex]n_2[/latex] options, choice three among [latex]n_3[/latex] options, and so on up to choice k made among [latex]n_k[/latex] options, the the total number of outcomes for the task is:

[latex]n_1\times n_2 \times n_3 \times \cdot \cdot \cdot \times n_k[/latex]

If the notation is confusing, fear not. I have a bunch of examples which should clarify things:

Eample 1: Sam has to choose an outfit to where to his first day of school. He has four pairs of jeans, 3 shirts, 5 pairs of shoes, and 2 jackets. If an outfit consists of a pair of jeans, a shirt, a pair of shoes, and a jacket, how many outfits can Sam choose among?

Choice [latex]n_1[/latex]  is choosing one of the four pairs of jeans, so [latex]n_1=4[/latex]

Choice [latex]n_2[/latex] is choosing one of the three shirts, so [latex]n_2=3[/latex]

Choice [latex]n_3[/latex] is choosing one of the five pairs of shoes, so [latex]n_3=5[/latex]

Choice [latex]n_4[/latex] is choosing one of the two jackets, so [latex]n_4=2[/latex]

[latex]n_1 \times n_2 \times n_3 \times n_4 = 4 \times 3 \times 5 \times 2 = 120[/latex]

Example 2: Sally is choosing an outfit for her first day of school. Sally's outfit consists of a skirt or a pair of pants, a blouse, a pair of shoes, and a jacket. She has 3 skirts, 5 pairs of pants, 7 blouses, 4 pairs of shoes, and 3 jackets.

This is a bit different from example 1 as the choice of whether to wear a skirt or a pair of pants is an exclusive choice - Sally can't wear both. In combinatorics a good rule of thumb is the follwing: AND choices get multiplied, OR choices get added. We can rephrase Sally's task of choosing an outfit like this:

Sally must choose a pair of pants AND a blouse AND a pair of shoes AND a jacket OR she must choose a skirt AND a blouse AND a pair of shoes AND a jacket.

If she chooses to wear a skirt then she has [latex]3 \times 7 \times 4 \times 3 = 252[/latex] choices. If she chooses to wear pants, then she has [latex]5 \times 7 \times 4 \times 3 = 420[/latex] choices. Because these two sets of choices are mutually exclusive, we add them to get the  total number of choices:

[latex](3 \times 7 \times 4 \times 3)+(5 \times 7 \times 4 \times 3)=252+420=672[/latex]

Example 3: Sam and Sally have a sexless alien sibling names Xanthar. Xanthar doesn't go to school because he comes from an advanced civilization. He loves data sufficiency and opera. Since no one else in the family likes data sufficiency, they decide to take Xanthar to Don Giovanni for his birthday. They have seats 101 to 105. How many ways can the family be seated if each member of the family occupies only one seat.

The first choice in our task is choosing a member of the family to sit in seat 101. The second choice is choosing one of the remaining members of the family to sit in seat 102, and so on until there is only one member of the family left and he or she must sit in seat 105.

Choice one can be taken in 5 ways, choice two in 4 ways, choice three in 3 ways, choice four in two ways, and choice five in only 1 way. So, the total number of arrangements is -

[latex] 5 \times 4 \times 3 \times 2 \times 1 = 120 [/latex]

Technically, this is called a 'Permutation', but as you can see we can handle it easily with the fundamental principle of counting.

Example 4: Sam and Sally's parents are still in the salad days of their marriage. They want to make the most of the romantic opportunity that the opera provides, so they insist on sitting together. Now, how many ways can the family be arranged in seats 101 to 105?

There are a couple of ways to do this problem. We could count the number of ways the parents could be arranged, and then the number of ways the kids could be arranged in the remaining seats, and then... nevermind. Suffice it to say that there's only one good way to do the problem. Since Sam and Sally's parents are joined at the lips, we treat them as one object, and we treat the two seats they will occupy as one seat.

If you're thinking "Wait a second - you're leaving something out!", then good for you. If you think everything looks peachy, just pause a minute and see if you can find out what's missing.

The missing piece of the puzzle is this: how do we know which order the parents sit in? We don't. We have to account for both possibilities. We'll get to that in a second.

Last time, I chose a person for a seat. This time, I'm going to choose a seat for a person - the way the assignment gets made doesn't affect the answer. Remember that there are only 4 places and four objects as the parents are inseperable. Thus, there are 4 places to put the parents (just in case you're unconvinced they can be seated in 101-2, 102-3, 103-4, or 104-5). There remain 3 places to put Sally, then 2 for Sam, and one for Xanthar (who already knows the answer to this question and the follow up question). So, the number of possible arrangements is almost:

[latex]4 \times 3 \times 2 \times 1 \times = 24[/latex]

Now, given that we don't know how Sally's parents are arranged, we have to multiply by 2 to account for the two possible arrangements (Man / Wife or Wife / Man). [latex]24 \times 2 = 48[/latex] is the final answer.

As a follow up question, what if Sam Sally and Xanthar had to be seated together? Post your answers in the comments!

Example 4: Alas, the salad days are over for Sam and Sally's parents and they refuse to be seated next to each other. Again there are several ways to do this problems, but only on efficient way. This idea has many names and is often used in finding the probability of certain events. I'll call it the 'complement method.' The idea works like this, supposed you're asked to count or calculate the probability of a complicated event, E. Often the number of ways that E does not happen, or the probability that E does not happen is easier to calculate.

In this case, we know that the total number of arrangements is 120, and the number of arrangements where Sam and Sally's parents do sit together is 48. So, the number of arrangements where Sam and Sally's parents don't sit together must be 120 - 48 =72.

I'll follow up on this post with some problems that can be solved using the methods we've discussed here.

Please feel free to post questions in the comments. Also, see the GMAT page of our website to learn about our quality tutors and prep packages.