Combinatorics Calculator

About This Calculator

Combinatorics is the branch of mathematics concerned with counting, arranging, and selecting objects. The two fundamental questions are: how many ways can you choose items from a set, and does the order matter? This calculator answers both, covering seven distinct counting operations in a single tool.

Supported operations include permutations (ordered arrangements), combinations (unordered selections), their with-repetition variants, factorials, derangements (permutations where no item is in its original position), and Catalan numbers (which count balanced parenthesizations, polygon triangulations, and other recursive structures).

The calculator uses BigInt arithmetic for exact results when $n > 170$ (where standard IEEE 754 floating-point overflows), supports values of $n$ up to 10,000, and provides a Stirling approximation alongside the exact result for large inputs. An interactive Pascal's triangle lets you click any cell to compute $C(n, r)$ instantly, and the step-by-step panel shows every stage of the formula evaluation.

How to Use

1. Select an operation from the visual radio cards: Permutation, Combination, Perm + Rep, Stars & Bars, Factorial, Derangement, or Catalan.
2. Enter n — the total number of distinct items in your set (0 to 10,000).
3. Enter r — the number of items selected or arranged. This field is hidden for factorial, derangement, and Catalan modes (which depend only on $n$).
4. Click Calculate to see the exact result, a step-by-step formula breakdown, and (where applicable) a P vs. C comparison panel, distribution bar chart, derangement convergence chart, or interactive Pascal's triangle.
5. Click cells in Pascal's triangle (shown for combinations with $n \leq 30$) to instantly set $n$ and $r$ and recalculate.

Formulas

Factorial

The factorial of $n$ is the product of all positive integers up to $n$, with the convention that $0! = 1$:

Factorials grow extremely fast — $20! \approx 2.43 \times 10^{18}$, and $170!$ is the largest factorial representable in standard floating-point. Beyond that, this calculator uses BigInt for exact computation.

Permutations (Without Repetition)

The number of ways to arrange $r$ items from $n$ distinct items, where order matters:

When $r > n$, $P(n, r) = 0$ by convention — you cannot arrange more items than exist in the set.

Permutations (With Repetition)

When order matters and each item can be reused (e.g., PIN codes, passwords):

Combinations (Without Repetition) — Binomial Coefficient

The number of ways to choose $r$ items from $n$ items, where order does not matter:

Key identity: $\binom{n}{r} = \binom{n}{n-r}$ — choosing $r$ items to include is identical to choosing $n - r$ items to exclude.

Combinations (With Repetition) — Stars and Bars

When order does not matter but items can be repeated (e.g., distributing identical objects into distinct bins):

This counts the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_n = r$.

Derangements (Subfactorial)

A derangement is a permutation where no element remains in its original position. The count is given by:

Equivalently, using the recurrence: $!n = (n-1)(!(n-1) + !(n-2))$ with base cases $!0 = 1$ and $!1 = 0$. Asymptotically, $D(n)/n! \to 1/e \approx 0.3679$.

Catalan Numbers

The $n$-th Catalan number counts balanced parenthesizations, polygon triangulations, non-crossing partitions, and valid push/pop sequences on a stack:

First values: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Pascal's Rule

Each entry in Pascal's triangle is the sum of the two entries directly above it:

Stirling's Approximation

For large $n$, the factorial can be approximated logarithmically:

This calculator shows the Stirling approximation alongside the exact BigInt result for $n > 170$, letting you compare the two.

Relationship Between P and C

Permutations and combinations are related by:

In other words, the permutation count is always exactly $r!$ times the combination count. The calculator's P vs. C comparison panel shows this ratio explicitly.

Worked Examples

Example 1: Lottery Draw (6/49)

A standard 6/49 lottery draws 6 balls from 49 numbered balls. Order does not matter and no ball can be drawn twice, so we use combinations.

1. Set $n = 49$, $r = 6$, operation = Combination.
2. Apply the formula: $C(49, 6) = \frac{49!}{6! \cdot 43!}$.
3. Expand using the efficient form: $\frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!} = \frac{10{,}068{,}347{,}520}{720}$.

There are 13,983,816 possible lottery tickets. The probability of winning the jackpot is $1/13{,}983{,}816 \approx 7.15 \times 10^{-8}$ — about 1 in 14 million.

Example 2: Committee with Roles

A club with 20 members elects a president, vice-president, and treasurer. Since each role is distinct, order matters — use permutations.

1. Set $n = 20$, $r = 3$, operation = Permutation.
2. Compute: $P(20, 3) = \frac{20!}{17!} = 20 \times 19 \times 18 = 6{,}840$.

Compare: if all three were equal committee members (no roles), $C(20, 3) = 1{,}140$. The ratio is $6{,}840 / 1{,}140 = 6 = 3!$, confirming $P(n, r) = C(n, r) \times r!$.

Example 3: Secret Santa Derangements

Eight coworkers do a Secret Santa gift exchange. Each person draws a name at random. A valid assignment requires that nobody draws their own name — this is a derangement.

1. Set $n = 8$, operation = Derangement.
2. Using the recurrence $!n = (n-1)(!(n-1) + !(n-2))$ with $!0 = 1$, $!1 = 0$:

Out of $8! = 40{,}320$ total arrangements, 14,833 are valid Secret Santa assignments. The probability that a random shuffle works is $14{,}833 / 40{,}320 \approx 36.8\%$, which is already close to the asymptotic limit of $1/e \approx 36.79\%$.

Example 4: Ice Cream Scoops with Repetition

An ice cream shop offers 10 flavors. A customer wants 3 scoops in a bowl (order of scoops does not matter, repeats are allowed). Use combinations with repetition.

1. Set $n = 10$, $r = 3$, operation = Stars & Bars.
2. Apply the formula: $C_{\text{rep}}(10, 3) = \binom{10 + 3 - 1}{3} = \binom{12}{3}$.
3. Compute: $\frac{12!}{3! \cdot 9!} = \frac{12 \times 11 \times 10}{6} = 220$.

There are 220 different possible bowls of ice cream.

Example 5: DNA Codon Counting

DNA codons are sequences of 3 nucleotides from the alphabet {$A, T, C, G$} — order matters and repetition is allowed.

1. Set $n = 4$, $r = 3$, operation = Perm + Rep.
2. Compute: $4^3 = 64$.

64 possible codons exist — 61 encode amino acids and 3 are stop codons, consistent with the standard genetic code.

Example 6: Password Keyspace

How many 8-character passwords can be formed from 94 printable ASCII characters? Order matters and characters can be repeated.

1. Set $n = 94$, $r = 8$, operation = Perm + Rep.
2. Compute: $94^8 = 6{,}095{,}689{,}385{,}410{,}816$.

Approximately 6 quadrillion possible passwords. At 1 billion guesses per second, brute-forcing this keyspace would take about 70 days.

Which Operation Should I Use?

The choice of formula depends on two questions: Does order matter? Can items repeat?

Rule of thumb: If rearranging the selection gives a different outcome, use permutations. If rearranging gives the same outcome, use combinations.

Common Misconceptions

Historical Context

The study of counting arrangements has deep roots across multiple cultures. Pascal's triangle — the single most important structure in elementary combinatorics — was independently discovered centuries before Blaise Pascal formalized it.

• India (c. 200 BC): The Sanskrit scholar Pingala described binary patterns in poetic meter in his Chandahsastra, producing what we now recognize as binomial coefficients. Commentary by Halayudha (c. 10th century AD) explicitly constructed the triangle.
• China (1261-1303 AD): Yang Hui described the triangle in 1261. Chu Shi-Chieh included it in his 1303 book Precious Mirror of the Four Elements, noting it was already known for over 300 years.
• Persia (11th century): Al-Karaji and Omar Khayyam independently worked with binomial coefficients in algebraic and geometric contexts.
• Europe (17th century): Blaise Pascal systematized the triangle's properties in his 1654 Traite du Triangle Arithmetique. His correspondence with Fermat on the "Problem of Points" launched mathematical probability theory, with combinations as a central tool.

The subfactorial (derangement count) was first studied by Pierre Remond de Montmort in 1708 and later by Leonhard Euler. The "hat-check problem" — in which $n$ guests check their hats and each receives a random hat back — became the canonical illustration. Catalan numbers were named after Eugene Charles Catalan (1838), though Euler had already counted polygon triangulations in the 18th century.

Pascal's Triangle

Pascal's triangle is a triangular array where row $n$, position $k$ holds $\binom{n}{k}$. It encodes row sums ($2^n$), palindromic symmetry, diagonal sequences (naturals, triangulars), and binomial expansion coefficients.

For a deep dive into construction, key patterns (hockey stick identity, diagonals), the binomial theorem connection, and applications in probability and number theory, see the Pascal's Triangle Generator guide.

Connections to Other Fields

• Probability: The binomial distribution uses $\binom{n}{k}$ directly: $P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$.
• Computer science: Combinations appear in analyzing algorithms (subset enumeration, hash collisions), and the number of edges in a complete graph $K_n$ is $\binom{n}{2}$.
• Cryptography: Permutation counting underlies keyspace size calculations and birthday attack analysis.
• Generating functions: The ordinary generating function for the $n$-th row of Pascal's triangle is $(1 + x)^n$, linking it directly to the binomial theorem.

Frequently Asked Questions

What is the difference between a permutation and a combination?

A permutation counts arrangements where order matters (e.g., {$A, B$} and {$B, A$} are different). A combination counts selections where order does not matter (e.g., {$A, B$} and {$B, A$} are the same). They are related by $P(n, r) = C(n, r) \times r!$.

When should I use combinations with repetition (Stars and Bars)?

Use this when you are distributing identical items into distinct categories, or when you can select the same item more than once and order does not matter. Classic examples include choosing ice cream scoops (repeats allowed), distributing identical coins among people, or counting non-negative integer solutions to an equation like $x_1 + x_2 + x_3 = 10$.

What is a derangement?

A derangement is a permutation in which no element appears in its original position. The classic "hat-check problem" asks: if $n$ people check their hats and each receives a random hat back, how many arrangements leave nobody with their own hat? The surprising result is that this probability converges to $1/e \approx 36.8\%$ very quickly — for $n \geq 5$, it is already within 0.3% of the limit.

What are Catalan numbers used for?

Catalan numbers appear in dozens of counting problems: the number of ways to correctly match $n$ pairs of parentheses, the number of triangulations of a polygon with $n + 2$ sides, the number of valid sequences of push/pop operations on a stack, and the number of full binary trees with $n + 1$ leaves.

How does the calculator handle very large numbers?

For $n \leq 170$, the calculator uses standard floating-point arithmetic. For $n > 170$, it switches to JavaScript's BigInt for exact computation. Results are displayed with commas for readability, along with the digit count and a Stirling's approximation for reference. $n$ values up to 10,000 are supported.

Why does the Pascal's triangle visualization cap at row 30?

Beyond row 30, the numbers grow too large and the cells too small to display meaningfully in an interactive grid. The calculator still computes $C(n, r)$ exactly for any $n \leq 10{,}000$ — the visual cap is purely a usability decision.

Is this calculator free?

Yes, completely free with no sign-up required. All seven operations, step-by-step solutions, the interactive Pascal's triangle, and all visualizations are available without restriction.

References

• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. Chapters 6 and 8.
• NIST Digital Library of Mathematical Functions, Sections 5.9 and 26.1-26.4. https://dlmf.nist.gov/
• Weisstein, Eric W. “Permutation,” “Subfactorial,” “Catalan Number.” MathWorld — A Wolfram Web Resource. https://mathworld.wolfram.com/
• Flajolet, Philippe and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
• Wikipedia. “Pascal's triangle,” “Derangement,” “Catalan number.” https://en.wikipedia.org/

Disclaimer

This calculator is provided for educational and informational purposes only. While the underlying algorithms produce exact results using BigInt arithmetic for inputs up to $n = 10{,}000$, very large computations may take a moment to process in-browser. The Stirling approximation is supplementary and may differ from the exact result in lower-order digits. Always verify critical calculations — particularly for cryptographic keyspace estimation, statistical modeling, or academic submissions — through independent means.