Combinatorics and Probability: Counting and Chance
Combinatorics is the mathematics of counting. How many ways can you arrange objects? How many subsets does a set have? These questions arise in probability, statistics, computer science, and cryptography. This guide covers the essential counting techniques.
The multiplication principle states that if task A has m outcomes and task B has n outcomes, the combined process has m times n outcomes. The addition principle states that if A and B are mutually exclusive with m and n outcomes respectively, there are m plus n total outcomes.
A permutation is an ordered arrangement of objects. The number of permutations of n objects taken r at a time is nPr equals n factorial over (n minus r) factorial. A combination is an unordered selection: nCr equals n factorial over (r factorial times (n minus r) factorial). Our permutation and combination calculator computes both with full step-by-step explanations.
The binomial theorem expands (a plus b) raised to the nth power: it equals the sum from k equals 0 to n of C(n,k) a^(n-k) b^k. The coefficients C(n,k) form Pascal's triangle, where each entry is the sum of the two entries above it. Our binomial expansion calculator generates these expansions.
Probability connects counting to uncertainty. The probability of an event equals the number of favorable outcomes divided by the total number of equally likely outcomes. Conditional probability P(A given B) equals P(A and B) divided by P(B). Bayes' theorem reverses conditional probability: P(A given B) equals P(B given A) times P(A) divided by P(B).
The binomial distribution models the number of successes in n independent trials, each with probability p. The probability of exactly k successes is C(n,k) p^k (1-p)^(n-k). The expected value is np and the variance is np(1-p).
The inclusion-exclusion principle counts the size of a union of sets: the size of A union B equals the size of A plus the size of B minus the size of A intersect B. For three sets, add back the pairwise intersections and subtract the triple intersection.
Generating functions provide a powerful framework for counting problems. The ordinary generating function for a sequence a_n is A(x) equals a_0 plus a_1 x plus a_2 x squared plus ... Coefficients of products correspond to convolutions, making generating functions ideal for counting problems involving choices.