Permutations & Combinations — Compute permutations and...

SECTION 1

Historical Context & Motivation

The art of counting arrangements and selections has occupied mathematical thinkers for millennia, long before formal notation codified their insights. Ancient civilizations recognized that the number of ways to arrange or choose objects grows explosively with the size of the collection—a realization that drove scholars to develop systematic methods. The twin concepts of permutations (ordered arrangements) and combinations (unordered selections) emerged from problems in gambling, astronomy, and philosophical inquiry, eventually crystallizing into the elegant formulas that underpin modern discrete mathematics, probability, and computer science.

c. 300 BCE

Sushruta Samhita & Early Indian Counting

The ancient Indian medical text enumerated combinations of tastes (sweet, sour, salty, bitter, pungent, astringent) taken one, two, three, etc. at a time—an early systematic treatment of what we now call n choose r.

c. 1070

Bhāskara II & Līlāvatī

The Indian mathematician Bhāskara II presented rules for permutations and combinations in his celebrated work Līlāvatī, giving explicit factorial-based formulas and applying them to problems involving syllable patterns and musical sequences.

1654

Pascal & Fermat: The Birth of Probability

Blaise Pascal and Pierre de Fermat exchanged letters analyzing the 'Problem of Points,' formalizing binomial coefficients and Pascal's Triangle as tools for counting combinations in games of chance.

1713

Bernoulli's Ars Conjectandi

Jakob Bernoulli's posthumous treatise unified permutation and combination theory within a broader probabilistic framework, introducing the notation and conceptual distinctions that persisted into the modern era.

20th Century

Combinatorics in the Digital Age

With the advent of computer science, permutations and combinations became foundational to algorithm analysis, cryptography, coding theory, and statistical mechanics—fields that rely on counting the number of feasible configurations in vast search spaces.

The central question that permutations and combinations answer is deceptively simple: How many ways can we select or arrange r objects from a collection of n? Whether order matters in the answer distinguishes the two concepts and determines which formula to apply. This seemingly modest distinction cascades into dramatically different counts—understanding it is the gateway to probability, statistical inference, and algorithm design.

SECTION 2

Core Principles & Definitions

Before diving into formulas, it is essential to internalize the foundational principles that govern all counting arguments. These principles provide the logical scaffolding upon which permutations and combinations are built, and they recur throughout combinatorics, probability, and discrete mathematics.

The Factorial Function

The factorial of a non-negative integer n, written n!, is the product n × (n − 1) × (n − 2) × … × 1. By convention, 0! = 1. Factorials count the total number of ways to arrange n distinct objects in a line.

The Multiplication Principle

If a process consists of k sequential stages with n₁, n₂, …, n_k choices at each stage respectively, the total number of outcomes is n₁ × n₂ × … × n_k. This principle is the engine behind both permutation and combination formulas.

Permutation: Order Matters

A permutation is an ordered arrangement of r objects chosen from n distinct objects. The arrangement ABC is different from BCA. The count is denoted P(n, r) or _nP_r.

Combination: Order Does Not Matter

A combination is an unordered selection of r objects from n distinct objects. The set {A, B, C} is the same as {C, A, B}. The count is denoted C(n, r), _nC_r, or the binomial coefficient (n choose r).

The Division Principle

If each outcome in a set has been counted exactly k times, dividing the total by k corrects the over-count. Combinations arise precisely this way: every combination of r objects corresponds to r! permutations, so C(n, r) = P(n, r) / r!.

✦ KEY TAKEAWAY

Think of permutations as filling labeled seats in a theater—who sits where matters. Combinations are like choosing a team from a roster—once you know who is on the team, the 'order' they were picked is irrelevant. The only structural difference between the two formulas is the r! in the denominator that removes the redundant orderings.

SECTION 3

Visual Explanation: Permutations vs. Combinations

The left panel lists all 6 permutations of choosing 2 elements from {A, B, C}—every reordering counts as a separate outcome. The right panel collapses each pair of mirror-image orderings (e.g., (A, B) and (B, A)) into a single combination, yielding 3 distinct subsets. The division by r! = 2! is what converts the permutation count into the combination count.

The diagram above captures the essential structural relationship between permutations and combinations. On the left, every distinct ordered pair drawn from the set {A, B, C} is listed; the six entries correspond to P(3, 2) = 3 × 2 = 6. On the right, pairs that differ only in order have been merged into a single unordered subset, reducing the count to C(3, 2) = 6 / 2! = 3. This visual makes the division principle tangible: because every 2-element combination can be internally rearranged in 2! = 2 ways, dividing the permutation count by 2! eliminates the over-counting introduced by treating order as significant.

SECTION 4

Mathematical Framework

With the core principles in hand, we now formalize the counting formulas. Each can be derived from the multiplication principle and the factorial function; the derivations reinforce why the formulas take the form they do rather than merely presenting them as facts to memorize.

The Factorial Function

FACTORIAL

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

n must be a non-negative integer. The convention 0! = 1 ensures consistency: for example, P(n, n) = n!/0! = n! and C(n, 0) = n!/(0! × n!) = 1, both of which match intuitive expectations.

Permutation Formula

When we arrange r objects from a pool of n distinct objects, the first position can be filled in n ways, the second in n − 1 ways, and so on down to n − r + 1 ways for the r-th position. By the multiplication principle the total is n × (n − 1) × … × (n − r + 1). This 'falling factorial' can be expressed compactly using the factorial function.

PERMUTATIONS

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

n = total number of distinct objects; r = number of objects being arranged (0 ≤ r ≤ n). The denominator (n − r)! cancels the tail of the factorial product, leaving exactly r factors.

Combination Formula

Each unordered subset of size r corresponds to r! ordered arrangements (permutations). To count only the distinct subsets, we divide the permutation count by r!, invoking the division principle.

COMBINATIONS (BINOMIAL COEFFICIENT)

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

Also written as (n choose r) or ₙCᵣ. The symmetry property C(n, r) = C(n, n − r) follows immediately from the formula's structure.

PERMUTATION–COMBINATION BRIDGE

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

This identity crystallizes the relationship: every combination can be internally rearranged in r! ways to produce all associated permutations.

📐 Derivation Sketch

Starting from P(n, r) = n!/(n − r)!, divide both sides by r! to remove the internal orderings within each selection. The result is C(n, r) = n!/[r!(n − r)!]. This derivation shows that the combination formula is not an independent fact—it is the permutation formula modulo the symmetry group of the chosen subset.

SECTION 5

Decision Framework: Which Formula to Use

Students often struggle not with the mechanics of the formulas but with recognizing which formula a problem demands. The decision hinges on two binary questions: (1) Are we arranging or selecting? (2) Are the objects distinguishable or not? In this course we focus on selections from a set of distinct objects, so the critical question reduces to whether order matters. The following decision-tree diagram and comparison table codify this reasoning.

Follow the decision tree from the top. The first branch asks whether the arrangement's order affects the outcome. Keywords in the problem statement—arrange, rank, sequence versus choose, select, committee—are reliable cues.

Side-by-side comparison of permutations and combinations

Feature	Permutation P(n, r)	Combination C(n, r)
Order	Matters — (A, B) ≠ (B, A)	Irrelevant — {A, B} = {B, A}
Formula	`n! / (n − r)!`	`n! / [r!(n − r)!]`
Relative size	Always ≥ C(n, r)	Always ≤ P(n, r)
Relationship	P(n, r) = C(n, r) × r!	C(n, r) = P(n, r) / r!
Typical context	Rankings, passwords, seating	Committees, hands of cards, teams

SECTION 6

Worked Examples

Example 1: Forming a Committee (Combination)

Step 1 — Read and ClassifyA department of 12 faculty members must select a search committee of 4. How many different committees are possible? Because a committee is an unordered group (the set {Adams, Brown, Clark, Davis} is the same committee regardless of listing order), this is a combination problem.

Step 2 — Identify ParametersWe have n = 12 distinct faculty and we choose r = 4.

n = 12, r = 4

Step 3 — Apply the FormulaC(12, 4) = 12! / [4! × (12 − 4)!] = 12! / (4! × 8!).

Step 4 — SimplifyRather than computing full factorials, cancel the 8! from numerator and denominator: C(12, 4) = (12 × 11 × 10 × 9) / (4 × 3 × 2 × 1) = 11,880 / 24.

Step 5 — Final AnswerC(12, 4) = 495. There are 495 distinct 4-person committees that can be formed from 12 faculty members.

C(12, 4) = 495

Example 2: Assigning Officers (Permutation)

Step 1 — Read and ClassifyFrom the same department of 12 faculty, a chair, vice-chair, and secretary must be elected. Because each position is distinct (being chair is different from being secretary), this is a permutation problem—order matters.

Step 2 — Identify Parametersn = 12, r = 3 (three labeled positions).

n = 12, r = 3

Step 3 — Apply the FormulaP(12, 3) = 12! / (12 − 3)! = 12! / 9!.

Step 4 — SimplifyCancel 9!: P(12, 3) = 12 × 11 × 10 = 1,320.

Step 5 — Final Answer & ComparisonP(12, 3) = 1,320. Notice that if the three elected officials formed an unordered committee instead, we would have C(12, 3) = 220, and indeed 1,320 / 3! = 1,320 / 6 = 220, confirming the P = C × r! bridge.

P(12, 3) = 1,320

SECTION 7

Common Pitfalls & Comparisons

Even students who have memorized the formulas can make errors rooted in misclassifying a problem or misapplying the arithmetic. The table below catalogs the most common pitfalls alongside strategies for avoiding them.

Five frequent mistakes and their remedies

Pitfall	What Goes Wrong	How to Fix It
Order confusion	Using P(n, r) when order is irrelevant, inflating the count by a factor of r!.	Ask: 'Would rearranging the chosen objects produce a genuinely different outcome?' If no, use C(n, r).
Forgetting 0! = 1	Treating P(n, n) as n!/0 (undefined) instead of n!/0! = n!/1 = n!.	Memorize the convention: 0! = 1 by definition.
Overcounting with repetition	Applying the standard P or C formula when objects are not all distinct (e.g., letters in MISSISSIPPI).	Use the multinomial coefficient n!/(n₁! × n₂! × …) when duplicates exist.
Arithmetic overflow	Computing full factorials before dividing, causing unnecessarily large numbers.	Cancel common factors first. For C(n, r), compute the product of r factors in the numerator and divide by r! progressively.
Complement counting neglect	Tackling 'at least one' problems by summing cases rather than subtracting the complement.	Count the total ways, subtract the 'none' case: P(at least 1) = Total − P(none).

⚠ RULE OF THUMB

If your answer to a combination problem is suspiciously large—or your answer to a permutation problem is suspiciously small—check whether you mixed up the two formulas. The permutation count is always exactly r! times the combination count for the same n and r, so a quick sanity check is to verify that P(n, r) / r! equals your combination answer.

SECTION 8

Connections to Advanced Theory

Permutations and combinations are the starting point of a vast combinatorial landscape. Understanding how these foundational formulas generalize provides a roadmap for further study in probability, algebra, and algorithm design. The table below situates the basic formulas relative to their more advanced counterparts.

How basic permutation/combination concepts extend to advanced topics

Basic Concept	Advanced Extension	Key Difference
P(n, r) — permutation without repetition	nʳ — permutation with repetition	With repetition, each of the r positions can be filled by any of the n objects, including reuse.
C(n, r) — combination without repetition	C(n + r − 1, r) — combination with repetition (stars & bars)	With repetition, the same element may be selected multiple times; the 'stars and bars' technique counts multisets.
C(n, r) — single binomial coefficient	Binomial Theorem: (x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ	The binomial coefficient becomes the coefficient in the expansion of (x + y)ⁿ, linking counting to algebra.
Factorials n!	Gamma function Γ(n + 1) = n! for positive integers	The Gamma function extends the factorial to all complex numbers except non-positive integers.
Counting selections	Inclusion–Exclusion Principle	For overlapping conditions, simple products overcount; inclusion–exclusion corrects by alternately adding and subtracting intersection sizes.

Perhaps the most immediate and powerful extension is the Binomial Theorem, which expresses the expansion of (x + y)ⁿ as a sum whose coefficients are precisely the combination numbers C(n, k). This connection transforms a counting identity into an algebraic tool, and vice versa—a hallmark of the deep interplay between combinatorics and other branches of mathematics. In probability theory, C(n, r) appears as the coefficient in the binomial distribution, and in computer science, the growth rate of C(n, r) governs the complexity of brute-force search algorithms that enumerate all subsets of a given size.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain in your own words why C(n, r) is always less than or equal to P(n, r) for 0 ≤ r ≤ n. Under what condition are they equal?

PROBLEM 2 — BASIC CALCULATION

Compute P(8, 3) and C(8, 3). Verify that P(8, 3) = C(8, 3) × 3!.

PROBLEM 3 — INTERMEDIATE

A standard deck has 52 cards. How many 5-card poker hands contain exactly 3 hearts and 2 spades?

PROBLEM 4 — APPLIED

A software team of 10 developers must be divided into a front-end group of 4 and a back-end group of 6. How many ways can this division be made? How does the answer change if a project lead must also be named from the back-end group?

PROBLEM 5 — CRITICAL THINKING

Prove the Vandermonde identity: C(m + n, r) = Σ (k = 0 to r) C(m, k) × C(n, r − k). Provide a combinatorial (counting) argument rather than an algebraic manipulation.

SUMMARY

Summary & Key Takeaways

Permutations count the number of ordered arrangements of r objects chosen from n distinct objects, given by the formula P(n, r) = n!/(n − r)!. Combinations count the number of unordered selections, given by C(n, r) = n!/[r!(n − r)!]. The critical link is the division principle: because each combination of r objects generates r! permutations, C(n, r) = P(n, r)/r!. Both formulas rest on the factorial function and the multiplication principle.

To decide which formula to apply, ask whether order matters: keywords like arrange, rank, sequence signal permutations, while choose, select, committee signal combinations. These foundational counting techniques extend to the Binomial Theorem, probability distributions, and algorithm analysis, making them indispensable tools throughout mathematics and computer science.