Combinations and Permutations for Counting Problems
Calculate combinations (nCr) and permutations (nPr), with and without repetition. Explore how counts grow as n and r change.
Calculate combinations (nCr) and permutations (nPr), with and without repetition. Explore how counts grow as n and r change.
The decision before any formula: does order matter? If A-B-C and C-B-A name the same outcome, you want combinations: C(n, k) = n! / (k! · (n − k)!). If they count separately, you want permutations: P(n, k) = n! / (n − k)!. They're related by P(n, k) = C(n, k) · k!, since permutations are combinations with all k! orderings of each one counted as distinct.
A 5-card poker hand is a combination, since the cards weren't dealt in any particular order. A first/second/third-place finishing list is a permutation, since Alice-then-Bob isn't the same result as Bob-then-Alice. A "lock combination" like 1-2-3 is, despite the name, a permutation: 3-2-1 doesn't open the lock. The page handles both, plus the "with repetition" variants for problems like password counts (n^k for permutations, C(n + k − 1, k) for multiset combinations). Large n runs through log-factorials to avoid overflow, so n = 170 evaluates cleanly where naive factorials blow past the float64 ceiling at 171!.
Before touching any formula, answer one question: does rearranging the chosen items create a different outcome? If picking A, B, C is the same as picking C, B, A, you need combinations. If the sequence matters—like assigning first, second, and third place—you need permutations.
Think about the physical result. A committee of three people is the same committee regardless of who was named first. But a three-digit lock code treats 1-2-3 as different from 3-2-1. Card hands are combinations; race finishing orders are permutations.
When order doesn't matter, dividing by r! removes the duplicate arrangements. That's why combinations are always smaller than or equal to permutations for the same n and r. The relationship is P(n, r) = C(n, r) × r!, meaning permutations count every ordering of each combination.
Quick test:
• "Does swapping two items change the outcome?" → Yes = permutation
• "Is the group the same regardless of arrangement?" → Yes = combination
Permutations without repetition: P(n, r) = n × (n−1) × (n−2) × … × (n−r+1). You multiply r consecutive integers starting from n. Choosing 3 items from 10: P(10, 3) = 10 × 9 × 8 = 720. Each position in the sequence pulls from a shrinking pool.
Combinations without repetition: C(n, r) = P(n, r) / r! = n! / (r!(n−r)!). The division removes duplicate orderings. C(10, 3) = 720 / 6 = 120. You can also compute it directly: (10 × 9 × 8) / (3 × 2 × 1).
Symmetry shortcut: C(n, r) = C(n, n−r). Choosing 3 from 10 is the same count as leaving out 7 from 10. When r is larger than n/2, compute the smaller side to reduce multiplication steps.
Example: C(52, 5) for poker hands
= (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1)
= 311,875,200 / 120 = 2,598,960
Permutations with repetition: n^r. Each of the r slots can be any of n options independently. A 4-digit PIN using digits 0–9 has 10^4 = 10,000 possibilities. This formula applies whenever you can reuse the same item in multiple positions.
Combinations with repetition use the "stars and bars" method: C(n + r − 1, r). Picking 5 scoops from 4 ice cream flavors, where order doesn't matter and repeats are allowed, gives C(4 + 5 − 1, 5) = C(8, 5) = 56. Visualize r stars (items) separated by n − 1 bars (dividers between categories).
Notice that with repetition r can exceed n—you can pick more items than there are categories. Without repetition r must be ≤ n because each item is used at most once.
Password example: An 8-character password from 62 characters (a–z, A–Z, 0–9) with repetition = 62^8 ≈ 218 trillion combinations.
Factorials explode fast: 20! ≈ 2.4 × 10^18, already near JavaScript's safe integer limit. Computing 100! directly overflows any standard number type. Use multiplicative cancellation instead—compute the numerator and denominator in steps, canceling as you go.
For C(n, r), exploit symmetry: use k = min(r, n − r). C(100, 3) is easier than C(100, 97) even though they're equal. Multiply the top three terms (100 × 99 × 98) and divide by 3! = 6.
When results exceed 10^15, scientific notation is cleaner than long digit strings. The tool displays large outputs as 1.23e15 for readability. If you need exact counts for cryptographic key spaces or lottery audits, use arbitrary-precision libraries like Python's math.comb() or Mathematica.
Tip: If a homework problem gives a suspiciously large factorial, check whether the formula simplifies. C(1000, 2) = 1000 × 999 / 2 = 499,500—no need to compute 1000! at all.
Using permutation when combination is needed (or vice versa). This is the most frequent error. A student asked, "How many ways can I pick 3 toppings for my pizza?" If the pizza doesn't care about topping order, the answer is combinations. Multiplying by 3! gives a wildly inflated count.
Forgetting the repetition constraint. Picking lottery balls without replacement is combinations without repetition. Guessing a combination lock (where you can repeat digits) is permutations with repetition. The formulas differ by orders of magnitude.
Swapping n and r. C(5, 3) ≠ C(3, 5). The first asks how many ways to choose 3 from 5; the second is undefined because you can't pick more items than exist without repetition. Always verify that r ≤ n for standard combinations.
Ignoring indistinguishable items. If two of your items are identical, standard formulas overcount. Arranging the letters in "MISSISSIPPI" requires multinomial coefficients, not a plain permutation.
Sanity check: Combinations should always be ≤ permutations for the same n and r. If your combination result exceeds the permutation result, you've applied the formulas backwards.
Why is 0! defined as 1?
By convention, 0! = 1 so that formulas stay consistent. C(n, 0) should equal 1 because there's exactly one way to choose nothing—do nothing. The formula n! / (0! × n!) only works if 0! = 1. It's a definitional choice that keeps everything tidy.
Can I have negative n or r?
Standard combinatorics uses non-negative integers. Negative factorials are undefined in elementary math. Extended definitions exist in advanced mathematics (the gamma function), but for counting problems, stick to n ≥ 0 and r ≥ 0.
What if items are not all distinct?
Use multinomial coefficients. The number of ways to arrange n items where n₁ are identical of one type, n₂ of another, etc., is n! / (n₁! × n₂! × …). "MISSISSIPPI" has 11 letters with 4 I's, 4 S's, 2 P's, and 1 M: 11! / (4! × 4! × 2! × 1!) = 34,650.
How do I calculate lottery odds?
For a 6/49 lottery (pick 6 numbers from 49, order irrelevant, no repeats), total outcomes = C(49, 6) = 13,983,816. Odds of matching all 6 = 1 in 13,983,816, or about 0.0000072%. If you pick more numbers, multiply by the probability of matching additional balls.
Why do passwords use permutations with repetition?
Each character position is independent, and you can use the same character more than once. A 12-character password from 95 printable ASCII characters has 95^12 ≈ 5.4 × 10^23 possibilities. That exponential growth is why longer passwords are exponentially harder to crack.
Distinguishable items: nCr and nPr assume all items are distinct. When some are identical, you want multinomial coefficients (n! / (k₁! · k₂! · …)) or the formula will overcount.
Non-negative integers: n and r must be non-negative integers in the standard formulation. Continuous extensions exist via the gamma function but most homework problems live in the integer case.
Float overflow at 171!: the page uses log-factorials to push the ceiling out. Cryptographic key-space audits or arbitrary-precision lottery analyses still need a bignum library.
Real-world dependencies: if two items can't both be drawn, or if order partially matters within a group, the pure combinatorial formula isn't the right tool. Verify your scenario maps to the model before trusting the count.
Note: SymPy handles combinatorics symbolically with arbitrary precision. scipy.special.comb returns the same numerical values for small n. For audit-grade work (lottery system design, security key-space estimation), use a system that's been validated for the exact range you care about, not a homework calculator.
Formulas and methods follow standard combinatorics references:
Ask: does swapping two of my chosen items create a different outcome? If yes, order matters and you want permutations. If no, order doesn't matter and you want combinations. Concrete tests. A 5-card poker hand is a combination because cards aren't dealt to ranked positions. A first/second/third place finish is a permutation because the ranking is the outcome. A "lock combination" 3-1-4 is, despite the name, a permutation because 4-1-3 doesn't open the lock. Office supply orders are combinations; passwords are permutations.
Use the cancellation form: nCr = n! / (r! · (n − r)!) simplifies because most factors cancel. C(10, 3) = (10 · 9 · 8) / (3 · 2 · 1) = 720 / 6 = 120. Always cancel against (n − r)! first; that leaves you with r terms in the numerator and r! in the denominator. For C(10, 3) you compute three factors top and bottom, not the full 10!. Pascal's triangle is another route: each entry is the sum of the two above. Useful for small n (under 10) when memory beats arithmetic.
The (n+1)-th row of Pascal's triangle (starting from row 0) lists C(n, 0), C(n, 1), …, C(n, n). The triangle is built by addition: each entry is the sum of the two above. The recurrence comes from the identity C(n, r) = C(n − 1, r − 1) + C(n − 1, r), which itself comes from a combinatorial argument: any group of r from n either includes a specific element (C(n − 1, r − 1) ways) or doesn't (C(n − 1, r) ways). The triangle gives binomial coefficients, which then give binomial expansion coefficients for (a + b)^n.
When you can reuse items: n^r for r-letter strings from n possible characters. A 4-character password from 26 letters has 26⁴ = 456,976 possibilities. Without repetition, P(n, r) = n! / (n − r)! limits you to using each item once. With repetition allows duplicates so the count grows faster. For combinations with repetition (multisets), the formula is C(n + r − 1, r), often called "stars and bars." Choosing r ice cream scoops from n flavors with repeats allowed: C(n + r − 1, r). Distinguishing the four cases is most of the challenge in counting problems.
C(n, r) for choosing r numbers from n. Powerball: pick 5 white balls from 69 and 1 red ball from 26. Probability of jackpot = 1 / (C(69, 5) · 26) = 1 / (11,238,513 · 26) = 1 / 292,201,338. So roughly 1 in 292 million per ticket. Mega Millions is similar with different parameters. The order in which you pick numbers doesn't matter (combinations). The probability of any specific ticket combination is 1 / C(69, 5) for Powerball's white balls; the red ball multiplies by 1/26. Quick-pick and self-pick have identical odds.
n! ≈ √(2πn) · (n/e)^n by Stirling's approximation. The (n/e)^n term dominates: an exponential with a base that itself grows. 10! ≈ 3.6 million. 20! ≈ 2.4 × 10¹⁸. 100! ≈ 9.3 × 10¹⁵⁷, more atoms than exist in the observable universe. 171! exceeds float64 (≈ 1.8 × 10³⁰⁸). The page handles this with log-gamma. For exact arbitrary-precision factorials, Python's math.factorial returns arbitrary-precision integers natively. The fast growth is why brute-force enumeration of permutations is intractable past n ≈ 11.
P(at least two people share a birthday in a group of k) becomes > 50% at just k = 23. The math: P(no shared birthday) = 365! / (365^k · (365 − k)!) for k ≤ 365. At k = 23, that's about 0.493, so P(shared) ≈ 0.507. The intuition trap: people compare to "someone shares MY birthday," which is much rarer. The birthday question is about any pair, and there are C(23, 2) = 253 pairs in a group of 23. With 253 chances at a 1/365 event each, hitting at least one is roughly 50/50. Cryptographic implication: hash functions need much more than n bits to avoid birthday-style collision attacks.
Divide by the factorial of each repeated count. Permutations of MISSISSIPPI: 11 letters with M (1), I (4), S (4), P (2). The count is 11! / (1! · 4! · 4! · 2!) = 34,650, not 11! = 39,916,800. The formula generalizes to multinomial coefficients: n! / (n₁! · n₂! · … · nₖ!) where nᵢ are the counts of each distinct item. Without the correction, you overcount by treating identical items as distinguishable. Same idea applies to arrangements of objects with multiple categories.
Calculate probabilities for various distributions and events
Calculate probabilities and z-scores for normal distributions
Calculate mean, median, mode, variance, and standard deviation
Calculate confidence intervals for population parameters
Explore counter-intuitive probability with this famous puzzle