Counting and Combinatorics

SECTION 1

Historical Context & Motivation

The challenge of counting arrangements and selections is among the oldest problems in mathematics, stretching back thousands of years to ancient civilizations grappling with practical questions about dividing resources, organizing people, and understanding games of chance. Combinatorics — the branch of mathematics devoted to systematic counting — grew out of these concrete needs and evolved into a rigorous discipline that underpins modern probability, computer science, and statistical reasoning. For GRE test-takers, combinatorics provides the foundational toolkit for answering questions about how many ways events can occur, objects can be arranged, or groups can be formed.

~300 BCE

Ancient Beginnings

Indian mathematician Pingala studied binary combinations in prosody (poetic meter), effectively enumerating the ways syllables could be arranged — an early instance of systematic counting.

1202

Fibonacci's Liber Abaci

Leonardo of Pisa introduced combinatorial reasoning to European mathematics, including problems about counting arrangements that would later influence the development of formal counting techniques.

1654

Pascal and Fermat Correspondence

Blaise Pascal and Pierre de Fermat exchanged letters on the "problem of points," laying the groundwork for both probability theory and the systematic use of combinations in mathematical analysis.

1713

Bernoulli's Ars Conjectandi

Jakob Bernoulli published his treatise formalizing permutations and combinations, establishing the notation and principles still used in modern combinatorics and GRE-level counting problems.

The central question that combinatorics answers is deceptively simple: How many ways can something happen? Whether you are selecting committee members, arranging books on a shelf, or determining the number of possible passwords, the tools of counting and combinatorics provide elegant, systematic solutions. On the GRE, these concepts appear in both Quantitative Comparison and Problem Solving formats, often requiring you to distinguish between situations where order matters and those where it does not.

SECTION 2

Core Principles & Definitions

Counting problems on the GRE rest on a small set of powerful principles. Once you internalize these foundational ideas, even complex-looking problems decompose into manageable steps. The key is recognizing which principle applies to a given scenario and applying it with precision.

The Multiplication Principle

If task A can be done in m ways and task B can be done in n ways, then doing both tasks in sequence can be done in m × n ways. This is the backbone of all counting.

The Addition Principle

If task A can be done in m ways and task B can be done in n ways, and the two tasks are mutually exclusive, then doing one or the other can be done in m + n ways.

Permutations (Order Matters)

A permutation is an arrangement of objects where the sequence is significant. Choosing a president, vice president, and secretary from a group yields different permutations than merely selecting a committee of three.

Combinations (Order Doesn't Matter)

A combination is a selection where only membership matters, not arrangement. Choosing 3 members for a committee from 10 people is a combination problem — the set {A, B, C} is the same as {C, A, B}.

The Factorial Function

n! (read "n factorial") equals n × (n−1) × (n−2) × … × 2 × 1 and counts the number of ways to arrange n distinct objects in a line. By convention, 0! = 1.

✦ KEY TAKEAWAY

Think of permutations versus combinations like a race versus a team photo. In a race, finishing 1st, 2nd, and 3rd in a particular order matters — that's a permutation. In a team photo, you just need to know who's in the picture, not the order they lined up — that's a combination. The GRE tests whether you can tell the difference.

SECTION 3

Visual Explanation — The Counting Tree

One of the most intuitive ways to visualize counting problems is through a tree diagram. Each branch represents a choice at a particular stage, and the total number of outcomes equals the number of paths from root to leaf. The following diagram illustrates how the multiplication principle works when selecting from the letters A, B, and C — showing both permutations (where order matters) and how the tree prunes when we consider combinations.

The tree branches at each level show the available choices after previous selections. With 3 items choosing 2, the multiplication principle gives 3 × 2 = 6 permutations. Dividing by 2! collapses pairs like AB/BA into single combinations.

Notice how the tree naturally demonstrates the multiplication principle: at the first level there are 3 choices, and at the second level there are 2 remaining choices, yielding 3 × 2 = 6 total paths. Each path is a distinct permutation. To convert permutations into combinations, we recognize that each pair of items appears twice (AB and BA, for instance), so we divide by 2! = 2, giving us 3 unique combinations. This visual relationship between permutations and combinations is one of the most important insights for the GRE.

SECTION 4

Mathematical Framework

The formulas for counting and combinatorics are derived from the multiplication principle and the factorial function. Understanding how they relate to each other — rather than merely memorizing them — is the key to flexible problem solving on the GRE.

FACTORIAL

n! = n × (n − 1) × (n − 2) × … × 2 × 1

where n is a non-negative integer. By definition, 0! = 1. The factorial counts the number of ways to arrange n distinct objects in a line.

PERMUTATIONS

P(n, r) = n! / (n − r)!

where n is the total number of objects and r is the number being arranged. P(n, r) counts ordered arrangements of r items selected from n distinct items.

COMBINATIONS

C(n, r) = n! / [r! × (n − r)!]

Also written as (n choose r) or ⁿCᵣ. Dividing the permutation formula by r! removes duplicate orderings, giving the number of unordered selections of r items from n.

FUNDAMENTAL RELATIONSHIP

P(n, r) = C(n, r) × r!

This identity reveals that every permutation is a combination multiplied by the number of ways to arrange the selected items. It is the single most useful relationship for converting between the two formulas on the GRE.

A practical GRE strategy is to first determine whether the problem involves ordered arrangements (permutations) or unordered selections (combinations), then apply the corresponding formula. If you're unsure, ask yourself: Would rearranging the chosen items create a different outcome? If yes, use P(n, r); if no, use C(n, r). Many GRE problems also involve the multiplication principle directly — combining several independent choices in sequence — without needing the formal P or C formulas at all.

SECTION 5

Detailed Classification of Counting Problems

GRE counting problems fall into several recognizable categories. Knowing which type you're facing allows you to select the right formula and avoid common traps. The diagram below maps the decision process, and the table that follows provides a quick-reference classification.

Start at the top and follow the decision branches. Sequential choices use the multiplication principle, then ask whether order matters to select permutations or combinations. Problems with repetition (e.g., passwords) use nʳ.

Common GRE counting problem types and their formulas

Problem Type	Order Matters?	Repetition?	Formula	Example
Permutation	Yes	No	`P(n,r) = n!/(n−r)!`	Arranging 3 books from 8 on a shelf
Combination	No	No	`C(n,r) = n!/[r!(n−r)!]`	Choosing 3 members from 8 for a committee
Permutation w/ Repetition	Yes	Yes	`nʳ`	Creating a 4-digit PIN (digits 0–9)
Identical Items	Yes	N/A	`n!/(n₁!×n₂!×…)`	Arrangements of letters in MISSISSIPPI

SECTION 6

Worked Example

Let's work through a GRE-style problem that requires distinguishing between permutations and combinations and applying the multiplication principle.

📝 PROBLEM

A student organization has 12 members. The group must form a 5-person committee, then select a chairperson and a secretary from among the 5 committee members. How many different leadership structures are possible?

Solution: Committee Leadership Selection

Step 1 — Identify the Sub-TasksThis problem involves two sequential tasks: (1) choose the 5 committee members from 12, and (2) assign 2 leadership roles from the 5 chosen members. Since these tasks happen in sequence, we will use the multiplication principle to combine them.

Step 2 — Count the Committee Selections (Combination)Choosing 5 members from 12 is an unordered selection — a combination. We compute C(12, 5) = 12! / (5! × 7!) = (12 × 11 × 10 × 9 × 8) / (5 × 4 × 3 × 2 × 1) = 95,040 / 120.

C(12, 5) = 792

Step 3 — Count the Leadership Assignments (Permutation)Selecting a chairperson and a secretary from 5 members is an ordered arrangement — a permutation, because the chair and secretary roles are distinct. We compute P(5, 2) = 5! / (5 − 2)! = 5! / 3! = (5 × 4 × 3!) / 3! = 5 × 4.

P(5, 2) = 20

Step 4 — Apply the Multiplication PrincipleSince the committee selection and leadership assignment are independent sequential tasks, the total number of leadership structures is 792 × 20.

Total = 15,840

💡 STRATEGY NOTE

When a GRE problem involves multiple stages, break it into sub-tasks. Classify each sub-task as a permutation, combination, or simple multiplication, compute each separately, then multiply the results together. This decomposition strategy handles nearly every counting problem you'll encounter on the exam.

SECTION 7

Common Pitfalls & GRE Strategies

Counting problems on the GRE are notorious for traps. Recognizing these common pitfalls — and having a clear strategy for each — can make the difference between a correct answer and a costly error. The table below contrasts frequent mistakes with the correct approach.

Pitfalls and strategies for GRE counting problems

Common Pitfall	Why It's Wrong	Correct Approach
Using permutations when order doesn't matter	Overcounts by a factor of r!, treating {A, B} and {B, A} as different.	Ask: "Would rearranging the chosen items create a different outcome?" If no, use C(n, r).
Forgetting about restrictions	Ignores constraints like "a specific person must be included" or "no repeated digits."	Handle restrictions first: fix the constrained items, then count the remaining freely.
Double-counting overlapping cases	When cases overlap (e.g., "at least one"), adding separate counts overcounts shared outcomes.	Use complementary counting: Total − (none of the desired) = at least one.
Confusing 'with repetition' and 'without'	Using nʳ when items can't repeat, or P(n,r) when they can.	Read carefully: can an item be reused? Passwords typically allow repetition; team selections do not.
Arithmetic errors with factorials	Factorials grow rapidly; computation mistakes are common under time pressure.	Cancel common factors before multiplying. E.g., 10!/(7!×3!) = (10×9×8)/(3×2×1).

🔄 THE COMPLEMENT STRATEGY

When a problem asks for "at least one" or "at most," it is often far easier to count the complementary case and subtract. Think of it like finding how many people in a room are wearing glasses: instead of counting each bespectacled person, you could count those without glasses and subtract from the total. On the GRE, complementary counting often transforms a complex multi-case problem into a single subtraction.

SECTION 8

Connection to Probability & Advanced Topics

Counting and combinatorics are not studied in isolation on the GRE — they form the computational engine behind discrete probability. Probability questions on the GRE frequently require you to compute the number of favorable outcomes and divide by the total number of outcomes, both of which are counting problems. Furthermore, the binomial coefficient C(n, r) appears directly in the Binomial Theorem and in probability distributions studied in more advanced statistics courses.

How GRE counting concepts extend to advanced topics

GRE-Level Concept	Advanced Extension	Connection
C(n, r) for counting subsets	Binomial coefficients in (a + b)ⁿ expansion	Each term's coefficient is C(n, r), linking algebra and combinatorics.
Counting favorable outcomes	Binomial probability distribution	P(X = k) = C(n, k) × pᵏ × (1−p)ⁿ⁻ᵏ uses combinations directly.
Permutations with identical items	Multinomial coefficients	Generalizes from 2 groups to k groups: n! / (n₁! × n₂! × … × nₖ!).
Complementary counting	Inclusion-Exclusion Principle	A general framework for avoiding overcounting across multiple overlapping sets.

While the GRE will not ask you to apply the Binomial Theorem or Inclusion-Exclusion Principle directly, understanding that your counting tools are the building blocks of these advanced ideas provides deeper mathematical fluency. It also means that mastering combinatorics now will pay dividends in any future statistics, computer science, or quantitative reasoning coursework.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

A club has 8 members. Explain why the number of ways to choose a president and a vice president is different from the number of ways to choose a 2-person committee. What is each value?

PROBLEM 2 — BASIC CALCULATION

How many different 3-letter arrangements can be formed from the letters A, B, C, D, E if no letter may be repeated?

PROBLEM 3 — INTERMEDIATE

A pizza shop offers 10 different toppings. How many different pizzas with exactly 4 toppings can be made? If the shop also offers 3 crust types, how many total pizza configurations (4 toppings plus a crust choice) are possible?

PROBLEM 4 — APPLIED

A security system requires a 4-digit code where digits range from 0 to 9 and repetition is allowed. However, the code cannot start with 0 and no two adjacent digits can be the same. How many valid codes are there?

PROBLEM 5 — CRITICAL THINKING

From a group of 7 men and 5 women, a committee of 5 must be formed that includes at least 2 women. How many such committees are possible?

SUMMARY

Lesson Summary

Counting and combinatorics on the GRE revolve around four core tools: the multiplication principle (multiply choices across sequential stages), the addition principle (add choices across mutually exclusive cases), permutations P(n, r) = n!/(n−r)! for ordered arrangements, and combinations C(n, r) = n!/[r!(n−r)!] for unordered selections. The fundamental relationship P(n, r) = C(n, r) × r! connects permutations and combinations and reveals that combinations are simply permutations with duplicate orderings removed.

To solve any GRE counting problem, first identify whether order matters, whether repetition is allowed, and whether the problem has multiple stages. Use the decision flowchart to select the right formula, apply complementary counting for "at least" problems, and always simplify factorials by cancelling before computing. These techniques form the foundation for discrete probability and will serve you well on the GRE and beyond.