Foundations of Combinations

Imagine you’re planning an outfit for the day. You have five different tops and four different pairs of pants. How do you determine the total number of outfit combinations? The multiplication principle is here to help! This principle states that if you have multiple independent choices, you can find the total number of possibilities by multiplying the number of options for each choice.

For example, if you have two tasks to complete, and there are $m$ ways to do the first task and $n$ ways to do the second task, the total number of ways to complete both tasks is $m \times n$. Applying this to the outfit scenario, you multiply the number of tops (5) by the number of pants (4), resulting in $5 \times 4 = 20$ possible outfit combinations.

This principle can be extended to any number of tasks. Whether you’re choosing clothes, planning meals, or creating passwords, simply multiply the number of choices together to find the total number of possibilities.

Permutation problems ask you to determine the number of possible arrangements of a set’s elements in a specific order. For example, calculating the number of possible seven-digit phone numbers is a permutation problem. Since each digit can be from 0 to 9, there are $10^7$ possible phone numbers.

Order matters in permutations. For instance, the phone numbers 345-7872 and 543-7728 are different because the digits are arranged differently.

Consider the set $S = \{a, b, c\}$. The three elements can be arranged in six different ways: $abc, acb, bac, bca, cab,$ and $cba$. Each arrangement is a unique permutation because the order of elements differs.

For larger sets, calculating permutations manually becomes impractical. Instead, we use factorials. For any integer $n > 1$, $n!$ (n factorial) is the product of all positive integers from 1 to $n$. By definition, $0! = 1! = 1$. For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

To find the number of permutations of a set with $n$ distinct elements, calculate $n!$. For example, the number of ways to arrange three letters is $3! = 6$. Similarly, the number of ways to arrange five people in a row is $5! = 120$.

Here’s an example problem:

Problem: Sophia is arranging four different dance trophies in a row on her bookshelf. How many different ways can she arrange the four trophies?

Solution: The number of arrangements is $4! = 24$. Therefore, the correct answer is 24.

Permutations become more complex when you have a fixed number of objects, $n$, to fill a limited number of positions, $r$, and the order matters. The formula for permutations in this case is:

$P(n, r) = \frac{n!}{(n-r)!}$

For example, a baseball coach with 20 players needs to determine the number of possible batting orders for 9 players. Using the formula:

$P(20, 9) = \frac{20!}{(20-9)!} = \frac{20!}{11!}$

The GMAT won’t require you to compute this value fully, but understanding the formula is key.

Combinations are similar to permutations, but the order of selection doesn’t matter. For example, forming a committee from a group of people is a combination problem because the order of selection is irrelevant.

The formula for combinations is:

$C(n, r) = \frac{n!}{r!(n-r)!}$

For example, if a pollster randomly selects 3 people from a group of 5, the number of possible combinations is:

$C(5, 3) = \frac{5!}{3!2!} = 10$

Here’s a GMAT-style problem:

Problem: A group of six fourth graders is choosing foursquare teams at recess. What is the total number of possible four-person teams that can be chosen from the group?

Solution: Using the combination formula:

$C(6, 4) = \frac{6!}{4!2!} = 15$

Thus, the correct answer is 15.

By understanding permutations and combinations, you’ll be well-prepared to tackle these types of problems on the GMAT.