01 / 21

Counting &
Combinatorics

Master the art of systematic counting: permutations, combinations, and the fundamental principles that unlock every GRE quantitative counting problem.

GRE Quantitative

Why Counting Matters

Combinatorics is the branch of mathematics that answers the question: "How many ways?" On the GRE, counting problems appear in both the Quantitative Comparison and Problem Solving sections. They test whether you can organize possibilities without listing every single one.

The Fundamental Counting Principle

If one event can occur in \( m \) ways and a second independent event can occur in \( n \) ways, then the two events together can occur in \( m \times n \) ways.

Shirt Pants then Red Blue Green 3 choices Jeans Khakis 2 choices
\( 3 \times 2 = 6 \) outfits

The Factorial Building Block

The factorial of a non-negative integer \( n \), written \( n! \), is the product of all positive integers up to \( n \). By convention, \( 0! = 1 \).

\( 5! \)
\( 5 \times 4 \times 3 \times 2 \times 1 = 120 \)
\( 4! \)
\( 4 \times 3 \times 2 \times 1 = 24 \)
\( 0! \)
\( = 1 \) (by definition)

Permutations: Order Matters

A permutation counts the number of ways to select and arrange \( r \) items from \( n \) distinct items, where order matters.

Pool of 5 items A B C D E → Choose 3 (ordered) 1st 2nd 3rd 5 × 4 × 3
\( P(5, 3) = 60 \) arrangements
 A-B-C and C-B-A are counted as different
\( ABC \neq CBA \neq BAC \neq \cdots \)

Combinations: Order Doesn't Matter

A combination counts the number of ways to select \( r \) items from \( n \) distinct items when order does not matter. We divide out the \( r! \) rearrangements that permutations would have counted separately.

Permutations of {A,B,C} ABC ACB BAC BCA CAB CBA 6 permutations = 3! ÷ 3! = ÷ 6 1 combination {A, B, C}
\( C(5, 3) = 60 \div 6 = 10 \) groups

Permutation vs. Combination

Permutation Combination
Order Matters Doesn't matter
Formula \( \frac{n!}{(n-r)!} \) \( \frac{n!}{r!\,(n-r)!} \)
Keyword clues arrange, order, rank, lineup choose, select, group, committee
\( n=5,\; r=3 \) 60 10
Relationship \( P(n,r) = C(n,r) \times r! \)

The Addition Principle

When you have mutually exclusive categories (you must pick one or the other, never both at once), you add the counts together.

Fiction books 8 Non-fiction books 5 OR
Total choices = \( 8 + 5 = \)13

Step-by-Step Strategy

1
Identify the task. What exactly are you counting? Arrangements? Selections? Routes?
2
Does order matter? If yes, use permutations. If no, use combinations.
3
Determine \( n \) and \( r \). \( n \) = total items, \( r \) = items being chosen.
4
Check for restrictions. Must certain items be included or excluded? Handle constraints first.
5
Multiply or add stages. Use the multiplication principle for "and" conditions, the addition principle for "or" conditions.

Example 1: Committee Selection

Problem: From a group of 8 students, how many ways can a committee of 3 be chosen?

1
Order? A committee of {A, B, C} is the same as {C, B, A}. Order does not matter: combination.
2
Identify: \( n = 8 \), \( r = 3 \).
3
Compute: \( \displaystyle \binom{8}{3} = \frac{8!}{3!\cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56 \)

Example 2: Seating Arrangement

Problem: In how many ways can 5 people be seated in a row of 5 chairs?

5 Chair 1 × 4 Chair 2 × 3 Chair 3 × 2 Chair 4 × 1 Chair 5

Example 3: Counting with Constraints

Problem: A club has 6 men and 4 women. A committee of 4 must include exactly 2 women. How many ways?

1
Break into stages: Choose 2 women from 4, and choose 2 men from 6.
2
Women: \( \displaystyle \binom{4}{2} = \frac{4!}{2!\cdot 2!} = 6 \)
3
Men: \( \displaystyle \binom{6}{2} = \frac{6!}{2!\cdot 4!} = 15 \)
4
Multiply (independent stages): \( 6 \times 15 = 90 \)

Complementary Counting

Sometimes it is easier to count what you don't want and subtract. If the total number of outcomes is \( T \) and the number of "bad" outcomes is \( B \):

Example: How many 3-person committees from 10 people include at least one woman (6 men, 4 women)?

Total
\( \binom{10}{3} = 120 \)
All men (bad)
\( \binom{6}{3} = 20 \)
At least 1 woman
\( 120 - 20 = 100 \)

Permutations with Repeated Elements

When some items are identical, we divide out the arrangements of those identical items. For the word with letters having frequencies \( n_1, n_2, \ldots \):

Example: How many distinct arrangements of the letters in MISSISSIPPI?

Total letters
\( n = 11 \)
Repeats
S: 4, I: 4, P: 2, M: 1
Answer
\( \frac{11!}{4!\,4!\,2!\,1!} = 34{,}650 \)

Common Mistakes to Avoid

✕ Confusing P and C
Using permutations when order doesn't matter (or vice versa) inflates or shrinks the answer by a factor of \( r! \).
✕ Forgetting constraints
If items must be included or excluded, handle the constraint first before applying formulas to the remaining items.
✕ Double-counting
When categories overlap, adding without subtracting the intersection counts some outcomes twice. Use complementary counting or inclusion-exclusion.

Formulas at a Glance

Scenario Formula Example
Fundamental Principle \( n_1 \times n_2 \times \cdots \) \( 3 \times 2 = 6 \)
Permutation \( \frac{n!}{(n-r)!} \) \( P(5,3)=60 \)
Combination \( \frac{n!}{r!\,(n-r)!} \) \( C(5,3)=10 \)
Repeated Elements \( \frac{n!}{n_1!\,n_2!\,\cdots} \) \( 34{,}650 \)
Complementary \( T - B \) \( 120 - 20 = 100 \)

Question 1 of 5

How many ways can a president, vice president, and secretary be chosen from a group of 10 people?

Question 2 of 5

A pizza shop offers 8 toppings. How many ways can you choose 3 toppings for your pizza?

Question 3 of 5

How many distinct arrangements of the letters in the word LEVEL are there?

Question 4 of 5

A team of 5 is chosen from 7 engineers and 5 designers. If the team must have exactly 3 engineers, how many teams are possible?

Question 5 of 5

From 9 books on a shelf, 4 are selected. How many selections include at least one of the 3 science books?