GMAT Combinatorics 2.0: Permutations and Combinations

If you haven't read GMAT Combinatorics 1.0, 1.1, and 1.2, you should do that before you read any further. Even if you're familiar with some of the material, you may not be familiar with my approach. Though the subtitle of this posts suggests that I'm going to discuss permutations and combinations, I'm never going to formally define either one - that's right no formulas. Just careful application of the fundamental counting principle with a couple of modifications.

When Order Matters:

The types of combinatorics problems that you're going to encounter on the GMAT can be subdivided into three groups:

• Simple counting - A task with sub-tasks involving choices (see 1.0, 1.1, and 1.2)

• Permutations - Ordering or reordering a set or subset of things (we've already done some examples in 1.0, 1.1, and 1.2)

• Combinations - Selecting a subset of things from a larger set.

The first two are pretty much taken care of in earlier posts, though we will discuss permutations as a way to illustrate what a combination is. Permutations involve order or assignment and can be done with a simple application of the fundamental principle of counting. Combinations involved selecting a subset without regard to order, and require a simple modification of the fundamental principle of counting.

Here's are some typical applications of permutations and combinations.

Permutations:

• Selecting a president, vice president, and treasurer for a club or organization

• Casting a play

• Selecting a batting order for a baseball team

• Ranking applicants by GMAT score

• Arranging books on a shelf

Combinations:

• Selecting a subcommittee

• Picking a dodge ball team

• Selecting toppings for a pizza

• Selecting 50 MBA applicants for acceptance

• Poker Hands

So, how do we compensate for order. I'll illustrate with two examples

Example 1:

This example has two similar problems - one where order matters and one where it doesn't

(A) High School High's Spanish club is holding an election to select the President, Vice President, and Treasurer of their club. If the club has eight members, how many possible outcomes can the election have?

Solution: Here we are ordering 3 things from a set of 8 things. Each of these three things will be assigned to a particular office, so order matters and we can apply the fundamental counting principle:

[latex]8 \times 7 \times 6 = 336[/latex]

(B) High School High's Latin club will elect a ruling triumvirate. If the Latin club has 11 members, how many possible outcomes can the election have?

Solution: Here we are selecting a subset of three people from a set of eleven people. None of the three people is assigned to a specific office, consequently many elections results are equivalent. Since there are three people in the triumvirate, each one can be listed in 6 ways - it's a simple application of the fundamental principle:

[latex]3 \times 2 \times 1[/latex]

In order to compensate we need to divide by the number of ways the selection can be reordered:

[latex size="2"] \frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 165[/latex]

A note on calculation - This might seem like a difficult computation, especially without access to a calculator, but you can save yourself a lot of work if you cancel bottom terms with top terms. The calculation I actually did looked like this:

[latex size="2"] \frac{11 \times 5 \times 3}{1} = 165[/latex]

To recap: You must divide by the number of ways your selection of elements can be rearranged when order doesn't matter.

Example 2:

Again, we'll do two similar problems - one where order matters and one where it doesn't

(A) High School High is putting on a production of Shakepeare's play Antony and Cleopatra. Four girls are auditioning for Octavia or Cleopatra. Six boys are auditioning for Octavius Ceasar, Mark Antony, or Lepidus. How many ways can these five parts be cast?

Solution: Here order matters. We're assigning two of the four girls to particular parts, and three of the six boys to particular parts. In, addition the selections are linked and the total number of castings will be the product of the castings for the boys and the castings for the girls. First we'll do the boys:

[latex] 4 \times 3 = 12 [/latex]

Now the girls:

[latex] 6 \times 5\times 4 = 120 [/latex]

Now the boys and the girls:

[latex] 120 \times 12 = 1440 [/latex]

(B) At the strike party, the cast orders two pizzas. Due to terrible performances by Antony and Cleopatra, they only have enough money for three toppings for each pizza.  The available toppings are: italian sausage, pepperoni, ham, onion, green pepper, pineapple, mushrooms, ricotta, goat cheese, and parmesan cheese. How many different pairs of pizzas can be ordered?

Solution: Here order doesn't matter - pepperoni and mushrooms is the same as mushrooms and pepperoni. The three pizzas are linked like the castings for girls and boys above, so the total number will be the product of the ways of selecting each pizza. Each pizza can have one or two or three toppings. Because these three scenarios are mutually exclusive to total number of pizzas will be the sum of these three scenarios. Kinda complicated, so we'll take it one step at a time. One pizza - one topping plus two toppings plus three toppings:

[latex size="2"] 10 + \frac{10 \times 9}{2 \times 1} + \frac{10 \times 9 \times 8}{3 \times 2 \times 1} [/latex]

[latex]10 + 45 + 120 = 175[/latex]

Since the second pizza will have the same number of variations, the total number of pizzas is

[latex] 175 \times 175 = 30,625[/latex]