Ordered arrangements — P(n,r) permutations
P(n,r) vs C(n,r) for varying r (n fixed)
Combinatorics is the branch of mathematics concerned with counting arrangements and selections. Two foundational operations are permutations — ordered arrangements of r items chosen from n, computed as P(n,r) = n!/(n−r)! — and combinations — unordered selections, computed as C(n,r) = n!/(r!(n−r)!). The ratio P/C = r! captures precisely how many orderings correspond to each selection. These formulae appear throughout probability theory, cryptography, genetics (counting possible DNA sequences), and the analysis of algorithms (counting comparisons in sorting).
This interactive tool lets you adjust n (total items) and r (chosen), switch between permutation, combination, Pascal's triangle, and inclusion-exclusion views, and read off the exact counts. The bar chart at the bottom compares P(n,r) and C(n,r) for all values of r simultaneously, revealing the explosive factorial growth that makes large combinatorial spaces computationally intractable.
What is the difference between a permutation and a combination?
Order matters in a permutation but not in a combination. Arranging 3 letters chosen from {A, B, C, D} gives P(4,3) = 24 distinct sequences (ABC and BAC are different). Choosing 3 letters from the same set gives C(4,3) = 4 distinct groups (ABC and BAC are the same group). The ratio P/C = r! = 6 counts how many orderings each group has.
Why does Pascal's triangle give binomial coefficients?
Pascal's triangle is constructed so that each entry equals the sum of the two entries above it: C(n,k) = C(n−1,k−1) + C(n−1,k). This recurrence reflects the combinatorial identity that choosing k items from n is equivalent to either including or excluding a particular item. Row n of the triangle lists C(n,0), C(n,1), …, C(n,n), which are exactly the coefficients in the binomial expansion of (x+y)^n.
What is the inclusion-exclusion principle?
The inclusion-exclusion principle counts the size of a union of sets by alternately adding and subtracting intersections: |A∪B| = |A| + |B| − |A∩B|. For three sets it extends to |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. It is used in probability (the union of events), graph theory (counting derangements), and algorithm analysis (counting strings satisfying multiple constraints).
Factorial growth is hyper-exponential: 10! = 3,628,800; 20! ≈ 2.4 × 10¹⁸; 52! ≈ 8 × 10⁶⁷ (the number of ways to shuffle a deck of cards). Stirling's approximation gives n! ≈ √(2πn)·(n/e)^n, which shows factorial growth exceeds any fixed exponential 2^n for large n. This is why brute-force search over all permutations becomes infeasible for even modest n.
The binomial theorem states that (x+y)^n = Σ_{k=0}^{n} C(n,k) x^(n−k) y^k. Each term's coefficient C(n,k) counts the number of ways to choose k factors of y from n factors of (x+y). Setting x = y = 1 gives 2^n = Σ C(n,k), showing that the total number of subsets of an n-element set is 2^n. Setting x = 1, y = −1 gives the alternating sum Σ (−1)^k C(n,k) = 0.
A derangement is a permutation with no element in its original position — for example, rearranging {1,2,3} so that 1 is not in position 1, 2 is not in position 2, and 3 is not in position 3. The number of derangements D(n) = n! × Σ_{k=0}^{n} (−1)^k / k!, which by inclusion-exclusion equals the nearest integer to n!/e. For large n, about 1/e ≈ 36.8% of all permutations are derangements.
Stars-and-bars counts the number of ways to distribute n identical objects into k distinct bins (allowing empty bins): C(n+k−1, k−1). For example, 7 indistinguishable sweets into 3 children = C(9,2) = 36 ways. If empty bins are not allowed (each child must receive at least one sweet), the answer is C(n−1, k−1) = C(6,2) = 15. This technique underlies generating functions and polynomial coefficient extraction.
Classical probability defines the probability of an event as (favourable outcomes) / (total equally-likely outcomes). Both numerator and denominator are typically computed using permutations and combinations. For example, the probability of a 5-card poker hand being a flush is C(13,5) × 4 / C(52,5) ≈ 0.00198, because you choose 5 ranks from 13 in one of 4 suits, out of all possible 5-card hands.
Colouring entries of Pascal's triangle by C(n,k) mod p (for prime p) produces the Sierpinski triangle fractal when p = 2. This follows from Lucas' theorem: C(n,k) mod p ≡ the product of C(nᵢ, kᵢ) mod p for each digit in the base-p representations of n and k. Entries are zero mod p whenever any digit of k exceeds the corresponding digit of n in base p, creating self-similar triangular "holes" at every scale.
In genetics, C(n,k) counts the number of ways k mutations can occur in a genome of n base pairs — critical for estimating the probability of specific cancer-causing mutations. The Hardy-Weinberg equilibrium uses binomial coefficients to predict genotype frequencies in a population, and combinatorial counting underpins the calculation of the number of possible antibody structures the immune system can produce (estimated at over 10¹⁸ distinct configurations).