Permutations - GMAT Math Study Guide
Definitions
- Combinatorics - The branch of mathematics that deals with collections of objects that satisfy specified criteria (e.g., counting arrangements, permutations, and combinations).
For example, combinatorics would answer the question "how many different ways can the BCS top-25 American college football rankings be arranged if only 100 possible teams exist?"
- Combinations - The branch of combinatorics where changing the order of the objects does not create a new scenario.
For example, the question "how many different ways can a manager select a team of 5 auditors from a recruiting pool of 10 potential employees?" is a combinations question since changing the order in which the employees are hired does not create a new arrangement (see combinations for much more on this topic).
- Permutations - The branch of combinatorics where changing the order of the objects creates a new scenario.
For example, the question "how many unique ways can the letters A, B, and C be arranged?" is a permutations question because moving A from the beginning to the end (e.g., ABC to BCA) creates a new arrangement.
Permutations - Defined by Example
While the definitions provided above likely offered some insight into permutations, the concept of combinatorics and permutations vs. combinations is often one of the more complicated mathematics topics. As a result, we will thoroughly examine an example to help shed light on this vitally important topic.
An Example Problem
Three different teams, denoted A, B, and C, are competing for first place in a curling tournament. How many different orders can the teams finish the tournament in?
Permutation
The above example would normally be read as an example of a permutations problem (and not a combinations problem) since changing the order in which the teams finished (e.g., A finished 3rd instead of 1st) would create a new rank order.
Pool of Teams Competing: A, B, and C
Possible Scenario: 6
ABC
ACB
BAC
BCA
CAB
ABC
Calculating the total number of possible arrangements of the rankings does not have to be done through diagramming out the possible scenarios. A shorter formula that uses factorials exists and is discussed below.
Combination
The above scenario would become a combinations problem if changing the order in which the 3 teams ranked did not create a new arrangement (e.g., ABC and ACB were considered no different). However, this interpretation of the problem as a combination example is not the natural reading of the question. Consequently, the text describing the example scenario would need to be changed for the example to be a combinations problem.
Permutations
Permutations problems such as the one involving the ranking of teams A, B, and C do not need to be solved by listing all the possible outcomes. The generic formula for selecting k objects from a pool of n objects when the order in which the n objects is chosen matters is given by the following formula:
Permutations Formula
Examples
Both permutations and combinations are best learned through working examples.
A computer scientist is trying to discover the keyword for a financial account. If the keyword consists only of 10 lower case characters (e.g., 10 characters from among the set: a, b, c, ..., w, x, y, z) and no character can be repeated, how many different unique arrangements of characters exist?
Step 1: Determine whether the question pertains to permutations or combinations.
Since changing the order of the potential keywords (e.g., ajk vs. kja) would create a new possibility, this is a permutations problem.
Step 2: Determine n and k
n = 26 since the computer scientist is choosing from 26 possibilities (e.g., a, b, c, ..., x, y, z)
k = 10 since the computer scientist is choosing 10 characters
Step 3: Apply the formula
Another Example
In a qualifying race for an Olympic road cycling event, 15 men competed for 5 slots. How many different ways could the top 5 slots be arranged if the order in which the men finished mattered?
Step 1: Determine whether the question pertains to permutations or combinations.
The phrase "the order in which the men finished mattered" indicates that this question pertains to permutations. Without this phrase, the question would be quite ambiguous and in need of clarification. In fact, without the phrase "the order in which the men finished mattered," the most logical reading would probably be to assume this question dealt with combinations since there is often no difference between finishing first, second, third, etc. in qualifying rounds.
Step 2: Determine n and k
n = 15 since there are 15 cyclists competing in the qualifying race
k = 5 since cyclists are competing for 5 spots
Step 3: Apply the formula
