Permutations & Combinations — Compute permutations and combinations - Finite Mathematics

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.

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

Side-by-side comparison of permutations and combinations

SECTION 6

Worked Examples

Example 1: Forming a Committee (Combination)

1
Step 1 — Read and Classify

A 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.
2
Step 2 — Identify Parameters

We have n = 12 distinct faculty and we choose r = 4.

n = 12, r = 4
3
Step 3 — Apply the Formula

C(12, 4) = 12! / [4! × (12 − 4)!] = 12! / (4! × 8!).
4
Step 4 — Simplify

Rather 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.
5
Step 5 — Final Answer

C(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)

1
Step 1 — Read and Classify

From 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.
2
Step 2 — Identify Parameters

n = 12, r = 3 (three labeled positions).

n = 12, r = 3
3
Step 3 — Apply the Formula

P(12, 3) = 12! / (12 − 3)! = 12! / 9!.
4
Step 4 — Simplify

Cancel 9!: P(12, 3) = 12 × 11 × 10 = 1,320.
5
Step 5 — Final Answer & Comparison

P(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.

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).

Five frequent mistakes and their remedies

⚠

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.

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.

How basic permutation/combination concepts extend to advanced topics

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

Question 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?

Show answer

P(n, r) counts every ordered arrangement of r objects chosen from n, whereas C(n, r) counts only the distinct unordered subsets. Since each subset of r objects can be internally rearranged in r! ways, P(n, r) = C(n, r) × r!, and because r! ≥ 1 for all non-negative integers r, we have P(n, r) ≥ C(n, r). Equality holds precisely when r! = 1, which occurs at r = 0 (one way to choose nothing, one way to arrange nothing) and r = 1 (each single-element 'subset' has only one internal ordering).

Question 2: BASIC CALCULATION

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

Show answer

P(8, 3) = 8!/(8 − 3)! = 8!/5! = 8 × 7 × 6 = 336. C(8, 3) = 8!/(3! × 5!) = (8 × 7 × 6)/(3 × 2 × 1) = 336/6 = 56. Verification: C(8, 3) × 3! = 56 × 6 = 336 = P(8, 3). The identity holds, confirming that the 336 permutations consist of 56 subsets each arranged in 3! = 6 ways.

Question 3: INTERMEDIATE

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

Show answer

There are 13 hearts and 13 spades in a standard deck. The number of ways to choose 3 hearts from 13 is C(13, 3) = 286. The number of ways to choose 2 spades from 13 is C(13, 2) = 78. Since these selections are independent, the multiplication principle gives the total as 286 × 78 = 22,308 distinct hands. Note that a poker hand is an unordered set of 5 cards, so combinations (not permutations) are appropriate for each suit selection.

Question 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?

Show answer

Choosing 4 developers for the front-end group from 10 automatically determines the back-end group, so the number of divisions is C(10, 4) = 10!/(4! × 6!) = 210. Equivalently, C(10, 6) = 210 confirms the symmetry. For the second part, after forming the two groups (210 ways), we must choose 1 project lead from the 6 back-end developers, which can be done in C(6, 1) = 6 ways. By the multiplication principle, the total is 210 × 6 = 1,260. Alternatively, note that naming the lead is a permutation-like step within the back-end selection, distinguishing one member from the rest.

Question 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.

Show answer

Consider a group of m + n people partitioned into Group A (m people) and Group B (n people). The left side, C(m + n, r), counts the number of ways to choose r people from the entire group. Any such committee includes some number k of members from Group A (where 0 ≤ k ≤ r) and the remaining r − k members from Group B. For a fixed k, the number of ways to choose k from A is C(m, k) and the number of ways to choose r − k from B is C(n, r − k); by the multiplication principle, this particular split contributes C(m, k) × C(n, r − k) committees. Since k ranges over all valid values from 0 to r (with the understanding that C(m, k) = 0 when k > m and C(n, r − k) = 0 when r − k > n), summing over k accounts for every possible committee exactly once, establishing the identity.

SUMMARY

Summary & Key Takeaways

Summary

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.