Permutations & Combinations
What Are Permutations & Combinations?
Permutations and combinations are the two foundational counting concepts in combinatorics. The core difference boils down to one question: does order matter?
Permutation: order matters. Imagine arranging 3 books on a shelf—Hamlet, Moby Dick, and 1984. Left-to-right "Hamlet-Moby-1984" is a different arrangement from "1984-Moby-Hamlet." The number of ways to choose r items from n and arrange them is denoted P(n,r).
Combination: order does not matter. Suppose you pick 3 people from a class of 10 to form a study group. Choosing {Alice, Bob, Carol} is the same group as {Carol, Alice, Bob}. The number of ways to choose r items from n (ignoring order) is denoted C(n,r), also written (nr).
Quick Mnemonic
Permutation = Position matters (who sits where)
Combination = Committee (who is chosen, not where they sit)
This gives us a key relationship: C(n,r) = P(n,r) / r!. The same group of r items can be arranged in r! different orders, but a combination counts them all as one.
These concepts trace back to the Indian mathematician Mahavira (c. 850) and Chinese Song-dynasty mathematician Jia Xian (c. 1050). In Europe, Blaise Pascal and Pierre de Fermat laid the foundations of modern combinatorics through their 1654 correspondence on gambling problems.
Factorial (n!)
The factorial is the building block of every permutation and combination formula. The factorial of n is defined as the product of all positive integers from 1 to n:
For example: 5! = 1 × 2 × 3 × 4 × 5 = 120.
Who Invented the "!" Notation?
The exclamation-mark notation was introduced by the French mathematician Christian Kramp in 1808. Before that, there was no standard way to write factorials. Kramp likely chose "!" because it is short, eye-catching, and unlikely to be confused with other symbols.
Why Is 0! = 1?
This is one of the most frequently asked questions in math. 0! = 1 is a convention, not a computed result, justified by several arguments:
- Empty-product principle: In mathematics, the product of zero factors is defined as the multiplicative identity, 1 (just as the sum of zero terms is the additive identity, 0).
- Formula consistency: C(n,0) = n!/(0! × n!) = 1 (there is exactly one way to choose nothing from n items—choose nothing), which is intuitively correct.
- Recursion: n! = n × (n−1)!. Setting n = 1 gives 1! = 1 × 0!, so 0! must equal 1.
Stirling's Approximation
For large n, computing n! directly becomes impractical (170! already exceeds the range of a 64-bit float). Scottish mathematician James Stirling (1730) and French mathematician Abraham de Moivre proposed an elegant approximation:
Why is this useful? In statistical mechanics, information theory, and algorithm analysis, we frequently work with log(n!). Stirling's formula gives log(n!) ≈ n log n − n, which makes theoretical derivations tractable. For instance, the lower-bound proof that comparison-based sorting requires Ω(n log n) comparisons relies on this approximation.
Stirling Accuracy
The larger n is, the smaller the relative error—it converges to 1/(12n).
Permutations — P(n,r)
Permutations answer the question: In how many ways can you choose r items from n distinct items and arrange them in order?
Why This Formula?
Think of it as filling slots one by one:
Slot 2: n−1 choices (one item already used)
Slot 3: n−2 choices
…
Slot r: n−r+1 choices
Total = n × (n−1) × (n−2) × … × (n−r+1) = n!/(n−r)!
Example: 3 Books on a Shelf
Permutations with Repetition — nr
When repetition is allowed (items can be reused), each slot has n independent choices.
Why? Because each slot's choice is independent. Slot 1 has n options, and slot 2 also has n options (because the item from slot 1 can be picked again), and so on. This is a direct application of the multiplication principle.
Real-world example: a 4-digit PIN (digits 0–9), each digit can repeat → 104 = 10,000 possibilities.
Multiset Permutations — The "MISSISSIPPI" Problem
When some of the n items are identical, we must divide by the number of ways the identical items can be swapped among themselves without creating a new arrangement.
Classic: Arrangements of "MISSISSIPPI"
Why divide? The 4 I's are indistinguishable—swapping them among themselves produces the exact same string—so we divide by 4! to remove these "phantom" permutations. Same logic for S and P.
Combinations — C(n,r)
Combinations answer the question: In how many ways can you choose r items from n distinct items, ignoring order?
Why C(n,r) = P(n,r) / r!?
But combinations only care about WHICH items are chosen, not their order.
Each group of r items can be arranged in r! ways.
So combinations = permutations / r! = P(n,r) / r! = n! / (r!(n-r)!)
Example: Choose 2 People from 5 for a Team
Pascal's Triangle
Pascal's triangle is an elegant geometric arrangement of binomial coefficients, governed by the recurrence:
Why? Consider the n-th item: either you include it (C(n−1, r−1)—choose r−1 more from the remaining n−1) or you exclude it (C(n−1, r)—choose all r from the remaining n−1). These two cases are mutually exclusive and exhaustive.
Row n, column r = C(n,r). The highlighted 6 = C(4,2).
History: It's Not Just "Pascal's" Triangle
Although the Western world credits Blaise Pascal (1654), this structure appeared in earlier Eastern sources:
- Jia Xian (c. 1050, Song dynasty China): First documented the triangle for extracting higher-order roots.
- Yang Hui (1261, Song dynasty China): Cited Jia Xian's triangle—hence the Chinese name "Yang Hui Triangle" (杨辉三角).
- Omar Khayyam (c. 1100, Persia): Independently discovered the same structure.
- Blaise Pascal (1654, France): Systematically studied its mathematical properties and connected it to probability theory.
Combinations with Repetition — Stars and Bars
When repetition is allowed, the number of ways to choose r items from n types is:
This formula is also known as Stars and Bars, popularized by the American probabilist William Feller in his classic 1950 textbook.
Intuition: Imagine r stars (★) and n−1 bars (|) arranged in a row. The bars partition the stars into n groups, each group representing how many of a particular item you choose. For example, choosing 4 fruits from 3 types: ★★|★|★ means "2 apples, 1 orange, 1 banana." Out of r + n − 1 total positions, choose r for stars (or equivalently, n−1 for bars) → C(n+r−1, r).
The Binomial Theorem
The binomial theorem expands (a + b)n as a sum whose coefficients are exactly the combination numbers:
Why Do C(n,k) Appear as Coefficients?
When expanding, from each factor choose either a or b.
To get a term an−kbk, choose exactly k of the n factors to contribute b (the rest contribute a).
The number of ways to choose k from n = C(n,k).
So the coefficient of an−kbk is C(n,k).
Example: Expanding (a + b)4
Newton's Generalization
Isaac Newton (1665, at just 22 years old) generalized the binomial theorem to non-integer and negative exponents. For any real number α:
Here the generalized binomial coefficient C(α,k) = α(α−1)(α−2)…(α−k+1) / k!. This allows us to expand √(1+x), 1/(1+x)2, and similar expressions—a fundamental tool in calculus and series theory.
Real-World Applications
Permutations and combinations are far from abstract classroom exercises—they appear everywhere in the real world.
๐ฐ Lottery Odds
Lotto 6/49: choose 6 numbers from 49 (order irrelevant). Winning odds = 1/C(49,6) = 1/13,983,816 ≈ 0.00000715%. You are about 28 times more likely to be struck by lightning (~1/500,000).
๐ Poker Hands
Deal 5 cards from 52: C(52,5) = 2,598,960 possible hands. A royal flush exists in only 4 forms (one per suit), so P(royal flush) = 4/2,598,960 ≈ 1/649,740.
๐ฅ Committee Selection
Choose a 5-person committee from 20: C(20,5) = 15,504 ways. Then assign chair, vice-chair, secretary from those 5: P(5,3) = 60. Total = 15,504 × 60 = 930,240.
๐ Password Security
4-digit PIN (0–9): 104 = 10,000 (permutations with repetition). 8-character password (upper+lower+digits, 62 chars): 628 ≈ 2.18 × 1014. Each extra character multiplies brute-force time by 62×.
๐งฌ DNA / Protein Sequences
DNA uses 4 bases (A, T, C, G). A sequence of length n has 4n possibilities. The human genome is ~3.2 billion base pairs, giving 43.2×10โน theoretical sequences—an astronomical number. Proteins use 20 amino acids; a 100-residue protein has 20100 ≈ 10130 possible sequences.
๐ป Algorithm Complexity
The Traveling Salesman Problem (TSP) must examine all permutations of n cities: (n−1)!/2 tours. For 20 cities, that is ≈ 6 × 1016—this "combinatorial explosion" of permutations is precisely why brute force fails and dynamic programming / heuristic algorithms are needed.
Common Mistakes
Even after mastering the formulas, applying them correctly can be tricky. Here are the most common pitfalls:
Mistake 1: Confusing Permutations and Combinations
✗ "Choose 3 people from 10 for a team: P(10,3) = 720"
✓ Team membership is unordered → C(10,3) = 120
Test: Ask yourself "Does swapping the order of selected items create a different outcome?" Yes → permutation. No → combination.
Mistake 2: Ignoring Repetition
✗ "3-digit PIN (0–9): P(10,3) = 720"
✓ Digits can repeat → 10³ = 1,000
Test: Can a chosen item be chosen again? Yes → with repetition. No → without repetition.
Mistake 3: Forgetting to Divide for Multiset Permutations
✗ "Arrangements of AABB = 4! = 24"
✓ Repeated letters → 4!/(2!×2!) = 6
The six: AABB, ABAB, ABBA, BAAB, BABA, BBAA.
Mistake 4: Using Standard C(n,r) When r > n
✗ "Choose 8 from 5 colors (repeats OK): C(5,8)"—undefined!
✓ With repetition → C(5+8−1, 8) = C(12,8) = 495
Related Tools
If you are working with permutations and combinations, these related tools may also be useful:
- Probability Calculator — Compute event probabilities P(A∪B), P(A∩B), binomial distribution, and more
- Bayes' Theorem Calculator — Compute posterior probability from prior and likelihood with full derivation
- Prime Factorization — Decompose integers into prime factors, useful for number theory and GCD/LCM
- Percentage Calculator — Percentage conversions and increase/decrease calculations
FAQ
The core distinction is whether order matters. A permutation treats ABC and BCA as different; a combination treats {A,B,C} and {C,A,B} as the same. Formally, C(n,r) = P(n,r)/r!—combinations are smaller by a factor of r! because the internal ordering of the r chosen items is disregarded.
0! = 1 is a mathematical convention, justified on three grounds: (1) the empty-product principle—the product of zero factors is the multiplicative identity 1; (2) the recursion n! = n × (n−1)! requires 0! = 1 when n = 1; (3) it makes combination formulas consistent—C(n,0) = n!/(0!×n!) = 1, meaning "there is exactly one way to choose nothing."
This calculator uses JavaScript BigInt, which can compute exact factorials of any size. In practice, computation becomes noticeably slow beyond n ≈ 10,000. In scientific computing, 170! is the largest factorial representable in 64-bit floating point (≈ 7.26 × 10306). Beyond that, you need arbitrary-precision libraries or Stirling's approximation.
Ask two questions: (1) Does order matter? If "pick A then B" is different from "pick B then A" (e.g., passwords, seat assignments), use permutations. If they are the same (e.g., teams, lottery), use combinations. (2) Is repetition allowed? If yes, use the "with repetition" formula (permutations: nr; combinations: C(n+r−1,r)). If no, use the standard formula (P(n,r) or C(n,r)).
Pascal's triangle hides a wealth of patterns: (1) Symmetry: C(n,r) = C(n, n−r), so each row is a palindrome. (2) Row sums: The sum of row n = 2n (since (1+1)n = 2n). (3) Fibonacci numbers: Summing along shallow diagonals yields the Fibonacci sequence. (4) Primality test: For prime p, all interior entries of row p are divisible by p. (5) Sierpinski triangle: Color odd entries and leave even ones blank—you get a fractal.