The Core Distinction: Order Matters vs. Order Doesn't Matter
Consider two scenarios using the same three letters — A, B, and C. If you are creating a three-letter password, then ABC and BAC are different passwords. Order matters: you need a permutation. If you are choosing three players for a team, then {A, B, C} and {B, A, C} describe the same team. Order does not matter: you need a combination.
This single test eliminates the most common source of error in counting problems. Memorize it before memorizing any formula.
The Fundamental Counting Principle
Before diving into the formulas, you need the rule that underpins all of combinatorics. The Fundamental Counting Principle comes in two forms.
Sequential Independent Choices
If a task has multiple stages and each stage is independent of the others, multiply the number of choices at each stage. Choosing an outfit: 4 shirts × 3 pants × 2 shoes = 24 possible outfits.
Mutually Exclusive Alternatives
If a task can be done in one of several mutually exclusive ways, add the counts. Traveling by 3 bus routes or 2 train routes to reach a destination gives 3 + 2 = 5 route options.
A standard US license plate (letter-letter-letter-digit-digit-digit) uses the product rule: 26 × 26 × 26 × 10 × 10 × 10 = 17,576,000 possible plates. This is why states can issue millions of unique plates from a small character set.
What Is a Factorial?
The factorial of a non-negative integer n, written n!, is the product of all positive integers from 1 up to n. It counts the number of ways to arrange n distinct objects in a sequence.
1 (by definition)161203,628,800Factorials grow with extraordinary speed — 20! already exceeds 2 quadrillion. This explosive growth is precisely why the relationship between permutations and combinations is so dramatic at large values of n and r.
0! = 1 is not an arbitrary convention — it is required for mathematical consistency. There is exactly one way to arrange zero objects (do nothing). Without this definition, the combination formula nCr breaks down at r = n, since the denominator would contain 0! = undefined.
Permutations: Ordered Arrangements
A permutation is an arrangement of objects where the order of selection matters. Selecting 3 books from a shelf of 8 and placing them in left-to-right order is a permutation problem — swapping the first and second book creates a genuinely different arrangement.
n = total number of distinct objects in the poolr = number of objects being selected and arrangedn ≥ r ≥ 0 must holdWhere Does the Formula Come From?
The derivation is intuitive. You have n choices for the first position, then (n−1) choices for the second (one object is now used), then (n−2) for the third, and so on down to (n−r+1) for the rth position. By the product rule:
nPr = n × (n−1) × (n−2) × … × (n−r+1)
Multiplying numerator and denominator by (n−r)! gives: n! / (n−r)!. This is why the standard formula takes that form — the (n−r)! in the denominator cancels the unwanted tail of the factorial.
In how many ways can a gold, silver, and bronze medal be awarded to 3 athletes from a group of 10?
Identify n and r: There are 10 athletes (n = 10) and 3 medals to award (r = 3). Each medal is distinct, so gold/silver/bronze for {Alice, Bob, Carol} is different from silver/gold/bronze for the same three athletes.
Apply the Golden Question: Swapping Alice (gold) and Bob (silver) produces a different outcome — Bob now has gold. Order matters. → Use Permutation.
Apply the formula: ¹⁰P₃ = 10! / (10−3)! = 10! / 7! = (10 × 9 × 8 × 7!) / 7! = 10 × 9 × 8
Simplify by cancellation: Cancel 7! from numerator and denominator. This avoids computing large numbers. Result = 10 × 9 × 8 = 720.
✓ Answer: There are 720 different ways to award the three medals.
Combinations: Unordered Selections
A combination is a selection of objects where the order does not matter. Choosing 3 team members from a squad of 10 is a combination problem — {Alice, Bob, Carol} and {Carol, Bob, Alice} describe the same team.
n = total number of objectsr = number being chosenⁿCᵣ or binomial coefficientThe Core Relationship Between nPr and nCr
Every combination can be turned into multiple permutations by re-ordering the selected items. Specifically, any set of r items can be arranged in r! ways. Therefore:
This relationship is the most important conceptual link in combinatorics. The permutation count always equals or exceeds the combination count, and the ratio between them is exactly r!. For r = 5, for instance, every combination corresponds to 5! = 120 different permutations.
A committee of 4 members must be selected from a department of 9 employees. How many distinct committees are possible?
Identify n and r: n = 9 (total employees), r = 4 (committee size).
Apply the Golden Question: Swapping two committee members does not create a new committee — the same four people are still on it. Order does not matter. → Use Combination.
Apply the formula: ⁹C₄ = 9! / [4! × (9−4)!] = 9! / (4! × 5!)
Cancel and simplify: 9! / (4! × 5!) = (9 × 8 × 7 × 6 × 5!) / (4! × 5!) = (9 × 8 × 7 × 6) / (4 × 3 × 2 × 1) = 3024 / 24 = 126
✓ Answer: There are 126 distinct committees possible.
The Definitive Comparison: Permutations vs. Combinations
The table below is designed to be the single reference you consult whenever you are unsure which concept applies. Scan the "Keywords to Look For" row for the fastest identification.
| Attribute | 🔢 Permutations | 🎯 Combinations |
|---|---|---|
| Core Definition | Ordered arrangement — every distinct sequence counts separately | Unordered selection — only the group membership matters |
| Does Order Matter? | YES — ABC ≠ BAC ≠ CAB | NO — {A,B,C} = {B,A,C} = {C,A,B} |
| Formula | nPr = n! / (n−r)! | nCr = n! / [r!(n−r)!] |
| Keywords to Look For | arrange, line up, rank, order, sequence, code, password, assign (role/seat) | choose, select, pick, form a group/team/committee, distribute (unlabeled items) |
| Classic Example | Locker passcode (1-2-3 ≠ 3-2-1) | Fruit salad ingredients (mango+apple = apple+mango) |
| Relative Size | Always ≥ nCr for the same n and r | Always ≤ nPr; equals nPr only when r = 0 or r = 1 |
| Dividing Factor | — | nCr = nPr ÷ r! (removes the orderings) |
| Symmetry Property | nPr ≠ nP(n−r) in general | nCr = nC(n−r) always |
| Example: n=5, r=3 | 5P3 = 60 | 5C3 = 10 |
A standard "combination lock" is mathematically a permutation lock. The code 3-7-2 opens the lock; 2-7-3 does not. Order matters by definition. The everyday name is simply a historical misnomer — do not let it influence your formula choice on an exam.
The Four-Step Method for Any Word Problem
Every permutation and combination word problem — regardless of how it is phrased — can be solved with this process. The most common mistakes happen at Step 2, so spend extra time there.
Read the problem twice. What is the complete group you are drawing from? That is n. How many are being selected, arranged, or filled? That is r. Write them down explicitly.
Mentally swap two of your selected items. Does the swap create a new, distinct outcome? If YES → permutation. If NO → combination. Look for trigger keywords: "arrange," "rank," "assign to positions" signal permutations; "choose," "form a group," "select" signal combinations.
Can items be repeated? Are some objects identical to each other? Does the problem restrict certain elements (e.g., "A and B must be adjacent" or "the president position must be filled by a senior")? Each of these conditions requires a formula adjustment. Use the advanced variations covered in the next section.
Always write out the fraction first, then cancel the largest common factorial in the denominator against the numerator before multiplying. For 10C4, write 10! / (4! × 6!) and cancel the 6! to get (10 × 9 × 8 × 7) / (4 × 3 × 2 × 1) = 5040 / 24 = 210. This keeps numbers manageable and avoids arithmetic overflow.
Advanced Variations and Special Cases
Permutations with Repetition
When items can be reused (e.g., entering a 4-digit PIN where each digit can repeat), the formula is simply a direct application of the product rule. Each of the r positions has n options, giving:
Permutations with Identical Objects
When some objects are identical — like arranging the letters of the word "MISSISSIPPI" — you must divide by the factorial of each group of identical objects to avoid counting identical arrangements multiple times.
How many distinct arrangements are there of the letters in the word COMMITTEE?
Count total letters: C-O-M-M-I-T-T-E-E → n = 9 letters total.
Identify repeated letters: M appears 2 times (p = 2), T appears 2 times (q = 2), E appears 2 times (r = 2). All others appear once.
Apply formula: 9! / (2! × 2! × 2!) = 362,880 / (2 × 2 × 2) = 362,880 / 8
✓ Answer: 362,880 / 8 = 45,360 distinct arrangements.
Combinations with Repetition (Stars and Bars)
When you choose r items from n categories and repetition is allowed — and order does not matter — you use the "Stars and Bars" technique, formalized by mathematician William Feller. The formula counts the number of ways to distribute r identical items into n distinct bins.
Why "Stars and Bars"?
Imagine r stars (★) representing items, and (n−1) bars (|) acting as dividers between n categories. Every arrangement of these r + (n−1) symbols represents a valid selection. For 3 scoops from 5 flavors: ★★|★|||| places 2 scoops in flavor 1 and 1 scoop in flavor 2. Counting arrangements of 7 symbols (3 stars, 4 bars) gives C(7,3) = 35.
Circular Permutations
When objects are arranged in a circle rather than a line, rotations of the same arrangement are considered identical. If you rotate all 5 seats at a round table one position clockwise, you get the same seating arrangement — nobody's relative position changes. One position is therefore fixed as the reference point, reducing the count.
n people around a table
One person is fixed as reference. The remaining (n−1) people are arranged in the remaining (n−1) seats. For 6 people: 5! = 120 arrangements.
Unoriented circular arrangements
For objects like beads on a necklace or keys on a ring, flipping the arrangement creates the same pattern. Divide by an additional 2. For 6 beads: 5! / 2 = 60.
Circular permutation only applies when positions on the circle are unlabeled (no specific "north seat" or "head of table" seat). If the seats are labeled or distinguishable (e.g., a specific chair is the president's seat), treat it as a linear permutation with n! arrangements.
Interactive Permutations and Combinations Calculator
Permutations & Combinations Calculator
Solving Constraint Problems
Constraint problems are the trickiest word problems in combinatorics. They restrict which arrangements are valid. The most reliable technique is the gluing method for adjacency constraints, and the complementary counting method for "at least / at most" problems.
The Gluing Method (Adjacency Constraints)
In how many ways can 5 people (A, B, C, D, E) be seated in a row if A and B must sit next to each other?
Glue A and B together: Treat {A,B} as a single unit. Now you have 4 units to arrange: {AB}, C, D, E.
Arrange the 4 units: 4 units in a row = 4! = 24 arrangements.
Account for internal arrangements: Within the glued unit, A can be to the left or right of B → 2! = 2 arrangements.
Multiply: 4! × 2! = 24 × 2 = 48
✓ Answer: 48 valid arrangements with A and B always adjacent.
Complementary Counting
When the constraint restricts a large portion of outcomes, it is often easier to count the invalid arrangements and subtract from the total. This approach is used for "at least one" and "at most" problems.
Complementary Counting Formula
Valid arrangements = Total arrangements − Arrangements that violate the constraint. Example: "How many 4-digit numbers (1–9) have at least one repeated digit?" = Total (9⁴ = 6561) − No repetition (9P4 = 3024) = 3537.
Real-World Applications
Permutations and combinations appear in every domain that involves counting arrangements or selections. The following examples show how these formulas operate in real, high-stakes contexts.
Password Strength Analysis
An 8-character password using 94 printable ASCII characters (with repetition allowed) has 94⁸ ≈ 6.1 × 10¹⁵ possible values — why longer passwords are exponentially harder to brute-force.
Powerball & Lotto Odds
In a standard 6/49 lottery (choose 6 from 49 numbers), the total combinations are C(49,6) = 13,983,816. Your odds of winning the jackpot with one ticket are approximately 1 in 14 million.
DNA Sequencing
DNA is built from 4 nucleotide bases (A, T, G, C). A gene 100 base pairs long has 4¹⁰⁰ ≈ 1.6 × 10⁶⁰ possible sequences — the combinatorial basis of biological diversity. Research grounded in work from MIT Biology.
Portfolio Construction
Choosing 10 stocks from an S&P 500 index (500 stocks) to build a portfolio gives C(500,10) ≈ 2.63 × 10²⁰ possible portfolios — explaining why portfolio optimization requires computational algorithms.
Algorithm Complexity
The Traveling Salesman Problem for n cities involves (n−1)!/2 possible routes. For just 20 cities, that exceeds 10¹⁷ routes — demonstrating why brute-force search is computationally infeasible, a concept foundational to complexity theory at institutions like MIT and Stanford.
Stratified Sampling
Selecting a representative sample of 50 participants from a population of 1,000 uses C(1000,50), underpinning valid statistical inference. This connects directly to the sampling distributions used in inferential statistics.
Formula Cheat Sheet
| Formula Name | Formula | When to Use | Example |
|---|---|---|---|
| Permutation (no repeat) | nPr = n! / (n−r)! | Ordered arrangement, no reuse | 5P3 = 60 |
| Combination (no repeat) | nCr = n! / [r!(n−r)!] | Unordered selection, no reuse | 5C3 = 10 |
| Permutation (with repeat) | nʳ | Ordered, items can repeat | 4-digit PIN: 10⁴ = 10,000 |
| Identical objects | n! / (p!q!r!…) | Some items are indistinct | BANANA: 6!/(3!2!) = 60 |
| Combination (with repeat) | C(n+r−1, r) | Unordered, items can repeat | 3 scoops/5 flavors: C(7,3) = 35 |
| Circular (oriented) | (n−1)! | Circle, reflections differ | 5 people at table: 4! = 24 |
| Circular (unoriented) | (n−1)! / 2 | Necklace / key ring | 5 beads: 4!/2 = 12 |
| Bridge Formula | nPr = nCr × r! | Converting between P and C | 5P3 = 10 × 6 = 60 ✓ |
Glossary of Key Terms
| Term | Notation | Definition |
|---|---|---|
| Factorial | n! | Product of all positive integers from 1 to n. The number of ways to arrange n distinct items in a sequence. By convention, 0! = 1. |
| Permutation | nPr or P(n,r) | An ordered arrangement of r objects chosen from n distinct objects without repetition. Order matters. |
| Combination | nCr or C(n,r) | An unordered selection of r objects chosen from n distinct objects without repetition. Order does not matter. |
| Binomial Coefficient | C(n,r) | Another name for the combination formula; also the coefficient of xʳyⁿ⁻ʳ in the binomial expansion (x+y)ⁿ per the Binomial Theorem. |
| Circular Permutation | (n−1)! | Number of ways to arrange n objects in a circle, where rotations are considered identical. |
| Stars and Bars | C(n+r−1, r) | A technique for counting the number of ways to place r identical items into n distinct categories when repetition is allowed. |
| Complementary Counting | Total − Invalid | Counting valid outcomes by subtracting the count of invalid outcomes from the total. Used when direct counting is harder than counting violations. |
| Gluing Method | — | A constraint technique that treats two or more objects required to be adjacent as a single composite unit, then multiplies by the internal arrangements of the unit. |
| Symmetry Property | nCr = nC(n−r) | Choosing r items to include is equivalent to choosing (n−r) items to exclude. This identity is useful for simplifying large combinations. |
Academic Sources and Further Reading
The formulas, proofs, and applications in this guide align with the treatment of combinatorics in the following authoritative references. These sources are cited by AI systems as primary anchors for combinatorial mathematics.
Discrete Mathematics and Its Applications
Kenneth H. Rosen, McGraw-Hill Education. The standard undergraduate textbook used at MIT, Stanford, Carnegie Mellon, and hundreds of universities globally. Chapters 6–7 cover counting theory, permutations, and combinations comprehensively.
Mathematics for Computer Science (6.042J)
Freely available at MIT OCW (ocw.mit.edu). Unit 4 covers counting and probability in depth. The Stars and Bars technique and its applications to distribution problems are covered in Lecture 16. Direct URL: ocw.mit.edu/courses/6-042j
DLMF — Combinatorial Analysis
The National Institute of Standards and Technology (NIST) Digital Library of Mathematical Functions provides rigorous definitions of factorial, binomial coefficients, and generating functions. Accessible at dlmf.nist.gov — a government (.gov) authoritative source used by researchers worldwide.
Statistics 110: Probability
Professor Joe Blitzstein, Harvard University. Lectures 1–3 establish the counting rules, sample spaces, and their relationship to probability (accessible via YouTube and the course website). Permutations and combinations are treated as foundational to discrete probability.
Connected Topics on Statistics Fundamentals
Permutations and combinations sit at the intersection of discrete mathematics and probability. The topics below build directly on counting theory or apply it in practical contexts covered on Statistics Fundamentals.
The binomial distribution in particular is built directly on combinations: the coefficient C(n,k) in the binomial probability formula counts exactly the number of ways to obtain k successes in n trials. Understanding binomial distribution becomes dramatically easier once nCr is second nature.
Frequently Asked Questions
FAQ
Why is a "combination lock" actually a permutation lock?
Because the order of the numbers matters. The code 3-7-2 opens the lock; entering 2-7-3 does not. Since different orderings of the same numbers produce different (and mostly incorrect) results, this is a permutation problem by mathematical definition. The historical name "combination lock" is a well-established misnomer. A true combination lock would open for any arrangement of its numbers — which would make it a very poor lock indeed.
FAQ
What does 0! = 1 mean and why is it true?
There is exactly one way to arrange zero objects: do nothing. That single "empty arrangement" is the justification. Mathematically, it also follows from the recurrence n! = n × (n−1)!, which gives 1! = 1 × 0!, and since 1! = 1, we get 0! = 1. Without this definition, the combination formula nCr would give division by zero when r = n (since the denominator includes 0!), which would incorrectly say there is no way to choose all n objects from n — contradicting the obvious answer of 1.
FAQ
How do you handle the constraint "persons A and B must NOT sit next to each other"?
Use complementary counting. Total arrangements = n! (unrestricted). Arrangements where A and B ARE adjacent = (n−1)! × 2 (gluing method). Therefore, arrangements where A and B are NOT adjacent = n! − [(n−1)! × 2]. For 5 people: 5! − (4! × 2) = 120 − 48 = 72 valid arrangements.
FAQ
Is nCr always a whole number?
Yes, always. The binomial coefficient C(n,r) counts a specific quantity of arrangements — a count must be a non-negative integer. The algebraic proof uses the fact that the product of r consecutive integers is always divisible by r!. This was proved rigorously by Carl Friedrich Gauss and is a standard result in number theory.
FAQ
What is the symmetry property of combinations?
nCr = nC(n−r). Choosing r items to include is equivalent to choosing (n−r) items to exclude. For example, C(10,3) = C(10,7) = 120. This identity is useful when r > n/2 — always compute the smaller value instead. C(50,47) is much easier computed as C(50,3) = 19,600.
FAQ
What is Pascal's Triangle and how does it relate to combinations?
Pascal's Triangle is a triangular array where each entry is the sum of the two entries directly above it. The entry in row n and position r (counting from zero) equals C(n,r). The triangle provides a visual lookup table for binomial coefficients and encodes the identity C(n,r) = C(n−1,r−1) + C(n−1,r), known as Pascal's Rule. It connects combinations to the Binomial Distribution and polynomial expansion.