Permutations, Combinations & Probability
Learning Objectives
- Understand the fundamental concepts of Permutations, Combinations & Probability
- Apply key formulas and techniques to solve problems
- Practice with exam-level questions to build speed and accuracy
Fundamental Counting Principles
1.1 The Multiplication Principle
The multiplication principle states that if a task can be broken into a sequence of independent stages, and the first stage can be performed in m ways while the second stage can be performed in n ways for each outcome of the first stage, then the whole task can be performed in m × n ways. This principle follows directly from the idea that each choice in the first stage can be paired with every choice in the second stage, producing a Cartesian product of the two sets of possibilities. When more than two stages are involved, the total number of ways is the product of the numbers of ways for each individual stage, provided the choices at each stage do not depend on earlier choices except through the already fixed outcomes.
In practice, the multiplication principle is the engine behind counting arrangements, selections, and many probability calculations. For example, to form a three‑digit code where the first digit cannot be zero, there are 9 choices for the first digit, 10 for the second, and 10 for the third, giving 9 × 10 × 10 = 900 possible codes. The principle also underlies the derivation of factorial notation, because arranging n distinct objects in a line can be seen as n successive choices: n ways for the first position, n−1 for the second, and so on, yielding n × (n−1) × … × 1 = n!.
1.2 The Addition Principle
The addition principle applies when a task can be completed by exactly one of several mutually exclusive methods. If method A can be carried out in a ways and method B in b ways, and the two methods cannot both be used for the same outcome, then the total number of ways to complete the task is a + b. This principle is essentially a statement about the cardinality of a disjoint union of finite sets: the size of the union equals the sum of the sizes of the individual sets. It is crucial when a problem naturally splits into cases that do not overlap, such as counting the number of ways to choose a committee that either includes a particular person or excludes that person.
Care must be taken to ensure the cases are truly disjoint; otherwise the simple sum would double‑count outcomes that belong to more than one case. In such situations the principle of inclusion–exclusion extends the addition principle by subtracting the sizes of intersections. The addition principle also appears in probability when computing the probability of the union of mutually exclusive events, because the probability of the union equals the sum of the individual probabilities.
1.3 Applications to Arrangements
Arrangements of objects in a line, around a circle, or in a row with restrictions are classic applications of the multiplication and addition principles. For linear arrangements of n distinct objects, the multiplication principle gives n! directly. When some objects are identical, the number of distinct permutations reduces because swapping identical objects does not produce a new arrangement; the formula becomes n! divided by the product of the factorials of the multiplicities of each identical type. Circular arrangements introduce a further division by n, since rotating the whole circle does not change the relative order, leading to (n−1)! for n distinct objects around a circle.
Restrictions such as “two particular persons must not sit together” are handled by first counting the total arrangements without restriction and then subtracting the arrangements where the restriction is violated. The latter is often counted by treating the restricted pair as a single combined object, applying the multiplication principle to the reduced set, and then multiplying by the internal permutations of the pair. This complementary counting technique is a direct consequence of the addition principle applied to the partition of the sample space into “restriction satisfied” and “restriction violated” cases.
Permutations
2.1 Definition and Notation
A permutation is an ordered arrangement of a selection of objects taken from a larger set. The notation P(n, r) or ⁿPᵣ denotes the number of ways to choose r objects from n distinct objects and arrange them in a sequence. By the multiplication principle, the first position can be filled in n ways, the second in n−1 ways, continuing until the r‑th position, which can be filled in n−r+1 ways. Hence P(n, r) = n × (n−1) × … × (n−r+1) = n! / (n−r)!. This formula makes explicit the relationship between permutations and factorials, and it reduces to n! when r = n, i.e., when all objects are arranged.
The notation ⁿPᵣ is read as “n permute r” and is standard in combinatorial textbooks. It emphasizes that order matters: the arrangement (a, b, c) is considered different from (b, a, c). This distinction is the defining feature that separates permutations from combinations, where order is irrelevant. Understanding this notation is essential for translating word problems into algebraic expressions that can be evaluated or simplified.
2.2 Permutations of Distinct Objects
When all n objects are distinct, the number of permutations of all n objects is n!. This follows immediately from the multiplication principle applied to n successive choices. For a partial permutation of length r, the formula P(n, r) = n!/(n−r)! gives the count. For instance, the number of ways to award gold, silver, and bronze medals to 10 athletes is P(10, 3) = 10 × 9 × 8 = 720. The reasoning is that the gold medal can go to any of the 10 athletes, the silver to any of the remaining 9, and the bronze to any of the remaining 8.
Permutations of distinct objects also appear in problems involving seating arrangements, password formation, and scheduling. In each case, the key is to identify the number of positions to fill and the pool of available distinct items for each position, then apply the product rule. If additional constraints such as “person A must sit at the left end” are present, the constrained position is fixed first, reducing the effective pool for the remaining positions, and the multiplication principle is applied to the reduced problem.
2.3 Permutations with Repetition
When objects are not all distinct, the number of distinct permutations decreases because swapping identical objects does not create a new arrangement. If a multiset contains n objects with n₁ of type 1, n₂ of type 2, …, n_k of type k (where Σ n_i = n), the number of distinct permutations is n! / (n₁! n₂! … n_k!). This formula is derived by starting with n! permutations of n labelled objects and then dividing by the factorial of each multiplicity to eliminate the overcounting caused by permutations among identical objects.
A classic example is the word “MISSISSIPPI”, which has 11 letters with multiplicities M=1, I=4, S=4, P=2. The number of distinct arrangements is 11! / (1! 4! 4! 2!) = 34 650. The same principle applies to arranging coloured balls, distributing identical gifts, or any scenario where some items are indistinguishable. It is important to verify that the objects within each type are truly identical; if any subtle distinction exists, the simple division by factorials would undercount the true number of arrangements.
Combinations
3.1 Definition and Notation
A combination is a selection of objects from a larger set where the order of selection does not matter. The notation C(n, r) or ⁿCᵣ (also written as binom{n}{r}) denotes the number of ways to choose r objects from n distinct objects without regard to order. Since each combination of r objects corresponds to r! permutations of those same objects, the relationship between permutations and combinations is C(n, r) = P(n, r) / r! = n! / [r! (n−r)!]. This formula is symmetric: C(n, r) = C(n, n−r), reflecting the fact that choosing r objects to include is equivalent to choosing n−r objects to exclude.
The binomial coefficient binom{n}{r} appears in the binomial theorem, in Pascal’s triangle, and in many probability calculations. It is read as “n choose r”. The symmetry property is often used to simplify calculations, for example by replacing C(100, 97) with C(100, 3). Understanding the combinatorial interpretation of binom{n}{r} as the number of r‑element subsets of an n‑element set is fundamental for solving selection problems.
3.2 Combinations of Distinct Objects
When selecting r objects from n distinct objects, the number of possible selections is binom{n}{r}. For example, the number of ways to form a committee of 4 members from a group of 12 people is binom{12}{4} = 495. The reasoning is that we first count ordered selections (permutations) which would be P(12, 4) = 12 × 11 × 10 × 9 = 11 880, and then divide by 4! = 24 because each committee can be ordered in 4! ways, leaving 495 distinct committees.
Combinations are used whenever the problem asks for “groups”, “teams”, “subsets”, or “selections” without any ordering. If the problem later imposes an order on the chosen objects (e.g., assigning distinct roles to the chosen members), the count must be multiplied by the number of ways to order the chosen objects, effectively converting the combination back into a permutation. Recognizing whether order matters is the first decision point in any counting problem.
3.3 Combinations with Repetition
Sometimes we are allowed to choose the same type of object more than once, as in selecting r scoops of ice cream from n flavours where multiple scoops of the same flavour are permitted. The number of such combinations with repetition is binom{n+r-1}{r}. This result is derived by a stars‑and‑bars argument: represent the r selections as r stars and the n−1 dividers between flavours as bars; the total number of arrangements of r stars and n−1 bars is binom{n+r-1}{r}. Each arrangement corresponds uniquely to a multiset of size r drawn from n types.
For instance, the number of ways to buy 6 donuts from 4 varieties is binom{4+6-1}{6} = binom{9}{6} = 84. The stars‑and‑bars method also provides a visual intuition: the positions of the bars determine how many of each variety are chosen. This technique extends to solving integer equations of the form x₁ + x₂ + … + x_n = r with non‑negative integer solutions, where the number of solutions is exactly binom{n+r-1}{r}.
| Aspect | Permutations | Combinations |
|---|---|---|
| Order matters | Yes | No |
| Formula (distinct objects) | P(n, r) = n!/(n−r)! | C(n, r) = n!/[r!(n−r)!] |
| Typical wording | Arrange, order, sequence, schedule | Select, choose, group, committee |
| Relation | P(n, r) = C(n, r) × r! | C(n, r) = P(n, r) / r! |
Probability Foundations
4.1 Sample Space and Events
The sample space of a random experiment is the set of all possible outcomes. An event is any subset of the sample space, including the empty set (impossible event) and the sample space itself (certain event). For a finite sample space with equally likely outcomes, the probability of an event E is defined as the ratio of the number of outcomes in E to the total number of outcomes in the sample space. This classical definition connects directly to counting principles: the numerator and denominator are often computed using permutations or combinations.
When outcomes are not equally likely, the probability measure must assign a non‑negative weight to each elementary outcome such that the sum of all weights equals 1. The probability of an event is then the sum of the weights of the outcomes it contains. This axiomatic approach, formalized by Kolmogorov, provides a rigorous foundation that accommodates continuous sample spaces, where outcomes are points in a continuum and probabilities are defined via density functions rather than simple counting.
4.2 Axioms of Probability
The three Kolmogorov axioms state: (1) For any event A, 0 ≤ P(A) ≤ 1. (2) P(S) = 1, where S is the sample space. (3) For any countable sequence of mutually exclusive events A₁, A₂, …, the probability of their union equals the sum of their probabilities: P(∪ A_i) = Σ P(A_i). These axioms imply several useful rules, such as the complement rule P(Aᶜ) = 1 − P(A), the addition rule for non‑exclusive events P(A ∪ B) = P(A) + P(B) − P(A ∩ B), and the monotonicity property that if A ⊆ B then P(A) ≤ P(B).
The axioms also justify the definition of conditional probability and the multiplication rule for intersections. They are the logical bedrock upon which all further probability theory, including Bayes’ theorem and the theory of random variables, is built. In problem solving, the axioms are rarely invoked explicitly, but they guarantee that any probability computed by legitimate counting or integration will satisfy the basic consistency requirements.
4.3 Classical and Empirical Probability
Classical probability applies when the sample space is finite and all outcomes are equally likely, as in tossing a fair coin, rolling a fair die, or drawing a card from a well‑shuffled deck. In such cases, probability reduces to a counting problem: P(E) = |E| / |S|. Empirical probability, on the other hand, is based on observed frequencies from repeated trials. If an experiment is performed N times and event E occurs f times, the empirical probability is f/N. As N grows, the law of large numbers ensures that the empirical probability converges to the true (theoretical) probability, provided the trials are independent and identically distributed.
Both viewpoints are essential. Classical probability gives exact answers for idealized models, while empirical probability provides estimates when the model is unknown or too complex. In many practical situations, such as quality control or medical trials, empirical probabilities are used to infer the underlying theoretical probabilities, often with confidence intervals derived from the binomial or normal approximations.
Conditional Probability, Bayes' Theorem and Distributions
5.1 Conditional Probability and Independence
Conditional probability quantifies the likelihood of an event A given that another event B has occurred. It is defined as P(A|B) = P(A ∩ B) / P(B), provided P(B) > 0. This definition reflects the idea of restricting the sample space to the outcomes in B and then measuring the proportion of those outcomes that also belong to A. The multiplication rule P(A ∩ B) = P(A|B) P(B) = P(B|A) P(A) follows directly and is a powerful tool for computing joint probabilities when conditional probabilities are known.
Two events A and B are independent if the occurrence of one does not affect the probability of the other, i.e., P(A|B) = P(A) and P(B|A) = P(B). Equivalently, independence means P(A ∩ B) = P(A) P(B). Independence simplifies calculations dramatically because the joint probability factorizes. However, independence is an assumption that must be justified by the physical context; many real‑world events exhibit dependence, and assuming independence incorrectly can lead to severe errors in risk assessment.
5.2 Bayes' Theorem
Bayes’ theorem provides a way to update the probability of a hypothesis H in light of new evidence E. It states P(H|E) = P(E|H) P(H) / P(E), where P(E) can be expanded using the law of total probability: P(E) = Σ P(E|H_i) P(H_i) over a partition {H_i} of the sample space. The theorem is a direct consequence of the definition of conditional probability and the multiplication rule. It is widely used in medical diagnosis, spam filtering, and machine learning, where prior probabilities are updated with observed data.
A classic illustration is the disease testing problem: suppose a disease affects 1 % of the population, a test has 99 % sensitivity (true positive rate) and 99 % specificity (true negative rate). If a randomly selected person tests positive, Bayes’ theorem gives the posterior probability of actually having the disease as (0.99 × 0.01) / (0.99 × 0.01 + 0.01 × 0.99) = 0.5, i.e., only a 50 % chance despite the high accuracy of the test. This counter‑intuitive result highlights the importance of the prior probability (prevalence) in interpreting diagnostic tests.
5.3 Common Discrete Distributions
Discrete probability distributions assign probabilities to countable outcomes. The binomial distribution models the number of successes in n independent Bernoulli trials with constant success probability p. Its probability mass function is P(X = k) = binom{n}{k} p^k (1−p)n−k for k = 0, 1, …, n. The mean is np and the variance is np(1−p). The Poisson distribution models the number of events occurring in a fixed interval of time or space when events happen independently at a constant average rate λ. Its mass function is P(X = k) = e−λ λ^k / k! for k = 0, 1, 2, …, with mean and variance both equal to λ.
The geometric distribution describes the number of trials needed to obtain the first success in independent Bernoulli trials, with P(X = k) = (1−p)k−1 p for k = 1, 2, … . The negative binomial generalizes this to the number of trials needed for the r‑th success. The hypergeometric distribution models sampling without replacement from a finite population, giving the probability of k successes in n draws from a population of size N containing K successes. Each distribution arises from a specific random mechanism, and recognizing the underlying mechanism is the key to selecting the correct model for a given problem.
| Feature | Binomial | Poisson |
|---|---|---|
| Underlying experiment | Fixed number n of independent Bernoulli trials | Events occurring randomly in continuous interval |
| Parameters | n (trials), p (success probability) | λ (average rate) |
| Support | k = 0, 1, …, n | k = 0, 1, 2, … |
| Mean | np | λ |
| Variance | np(1−p) | λ |
| Limit relationship | Poisson approximates Binomial when n large, p small, np = λ | — |
Mastering the interplay between counting principles, probability axioms, and the standard discrete distributions equips a student to tackle a wide spectrum of problems in competitive examinations and in practical data analysis.
Inclusion–Exclusion Principle and Its Applications
The inclusion–exclusion principle systematically counts elements in the union of finite sets that may overlap. For two sets A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. For three sets A, B, C, |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. In general, for n sets A₁, A₂, …, Aₙ,
|A₁ ∪ A₂ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − … + (−1)ⁿ⁺¹|A₁ ∩ A₂ ∩ … ∩ Aₙ|,
where sums run over all distinct indices. The term for the intersection of k sets carries sign (−1)ᵏ⁺¹.
A standard application counts integers up to a bound not divisible by given primes. For positive integers ≤ 100 not divisible by 2, 3, or 5, let A₂, A₃, A₅ be the sets of multiples. Then |A₂| = ⌊100/2⌋ = 50, |A₃| = 33, |A₅| = 20. Pairwise intersections: |A₂ ∩ A₃| = ⌊100/6⌋ = 16, |A₂ ∩ A₅| = ⌊100/10⌋ = 10, |A₃ ∩ A₅| = ⌊100/15⌋ = 6. Triple intersection: |A₂ ∩ A₃ ∩ A₅| = ⌊100/30⌋ = 3. By inclusion–exclusion, numbers divisible by at least one of 2,3,5 total 50+33+20−16−10−6+3 = 74. Hence 100−74 = 26 are not divisible by any.
The principle extends to probability: for events E₁, …, Eₙ, P(E₁ ∪ … ∪ Eₙ) follows the same alternating‑sum formula with probabilities replacing cardinalities. This is useful when the union probability is hard to compute directly but individual and intersection probabilities are accessible.
Another application counts onto functions. The number of surjections from an m‑element set to an n‑element set is Σk=0n (−1)ᵏ C(n, k) (n−k)ᵐ, obtained by letting Aᵢ be the functions missing the i‑th codomain element and applying inclusion–exclusion.
When applying inclusion–exclusion, correctly identify all intersections and maintain the alternating sign pattern. A common error is stopping at pairwise intersections when triple (or higher) intersections are non‑empty, causing overcounting.
Derangements and Subfactorial Numbers
A derangement is a permutation with no element in its original position. The number of derangements of n distinct objects is denoted !n (subfactorial n) or Dₙ. Inclusion–exclusion gives
!n = n! Σk=0n (−1)ᵏ / k! = n! (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!).
This sum is the truncated Maclaurin series for e⁻¹, so for large n, !n ≈ n!/e. Rounding n!/e to the nearest integer yields the exact value.
A useful recurrence is !n = (n−1)(!(n−1) + !(n−2)) for n ≥ 2, with !0 = 1, !1 = 0. It follows by placing element 1 in any of n−1 positions, say k. If element k goes to position 1, the remaining n−2 elements must be deranged; otherwise, element k must avoid position 1, equivalent to deranging n−1 elements with a modified forbidden position.
The first few derangement numbers are:
| n | !n |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 9 |
| 5 | 44 |
| 6 | 265 |
Derangements appear in the hat‑check problem: n guests receive hats randomly; the probability no guest gets his own hat is !n/n! ≈ 1/e ≈ 0.3679 for large n. The same probability arises in the matching problem (letters to envelopes).
For moderately large n, the factorial sum is efficient because terms decrease rapidly. For n = 10, the 11‑term sum gives !10 = 1,334,961. The approximation 10!/e ≈ 3,628,800/2.71828 ≈ 1,334,960.9 rounds correctly.
In competitive problems, derangements often combine with other constraints, such as exactly k fixed points. The number of permutations of n elements with exactly k fixed points is C(n, k) × !(n−k), obtained by choosing the k fixed elements and deranging the rest.
Circular Permutations and Necklace Problems
Arranging n distinct objects around a circle treats rotations as identical. The number of distinct circular permutations is (n−1)!, found by fixing one object and permuting the remaining n−1 linearly.
If objects are not all distinct, divide by the factorials of multiplicities. For example, circular arrangements of "ALGEBRA" (7 letters, A twice) total (7−1)! / 2! = 720 / 2 = 360.
When reflections are also identical, the objects form a necklace. For n > 2 distinct beads, the number is (n−1)!/2. For n = 1 or 2, division by 2 does not apply because a reflection coincides with a rotation. With colored beads (repetitions allowed), the problem becomes counting orbits under the dihedral group Dₙ. Burnside's lemma (Cauchy‑Frobenius lemma) gives the number of distinct colorings as (1/|G|) Σg∈G fix(g), where G is the symmetry group (cyclic for rotations, dihedral for rotations and reflections) and fix(g) is the number of colorings fixed by g.
For a binary necklace (two colors) with n beads, rotationally distinct necklaces number (1/n) Σd|n φ(d) 2n/d, where φ is Euler's totient function. If reflections are allowed, the formula for odd n is (1/(2n)) [ Σd|n φ(d) 2n/d + n·2⌈n/2⌉ ]; for even n an analogous expression with additional terms applies. These are standard results in Polya enumeration theory.
In examination problems, the symmetry group is usually explicit: "round table" implies rotations only; "necklace" or "bracelet" implies rotations and reflections. Misidentifying the group is a frequent error.
Fixed positions break circular symmetry: if certain objects must occupy specific seats (e.g., host at the head), the problem reduces to a linear permutation of the remaining objects.
Multinomial Coefficients and the Multinomial Theorem
The multinomial coefficient generalizes the binomial coefficient to partitioning a set into more than two subsets. The number of ways to divide n distinct objects into k labeled groups of sizes n₁, n₂, …, nₖ (Σ nᵢ = n) is
n! / (n₁! n₂! … nₖ!).
This coefficient appears as the coefficient of x₁n₁ x₂n₂ … xₖnₖ in the expansion of (x₁ + x₂ + … + xₖ)ⁿ, the multinomial theorem:
(x₁ + x₂ + … + xₖ)ⁿ = Σn₁+…+nₖ=n (n! / (n₁! … nₖ!)) x₁n₁ … xₖnₖ.
The sum runs over all k‑tuples of non‑negative integers summing to n. For k = 2 this reduces to the binomial theorem.
A direct combinatorial interpretation: the number of distinct permutations of a multiset with n total items, where item i appears nᵢ times, is n!/(n₁!…nₖ!). For "MISSISSIPPI" (M=1, I=4, S=4, P=2), distinct permutations = 11!/(1!4!4!2!) = 34,650.
Multinomial coefficients also give the probability mass function of the multinomial distribution: for n independent trials with outcomes 1,…,k having probabilities p₁,…,pₖ (Σ pᵢ = 1), the probability of exactly nᵢ occurrences of outcome i is (n!/(n₁!…nₖ!)) p₁n₁ … pₖnₖ, generalizing the binomial distribution.
An important identity: Σn₁+…+nₖ=n n!/(n₁!…nₖ!) = kⁿ, obtained by setting x₁ = … = xₖ = 1 in the multinomial theorem.
When solving problems, a multinomial coefficient can be computed sequentially as a product of binomial coefficients: choose n₁ items for the first group (C(n, n₁)), then n₂ from the remainder (C(n−n₁, n₂)), etc. This stepwise approach simplifies arithmetic and reduces overflow risk in manual calculations.
Advanced Probability: Expectation, Variance, and Generating Functions
The expectation of a discrete random variable X is E[X] = Σ x·P(X=x). Expectation is linear: E[aX + bY] = aE[X] + bE[Y] for any constants a, b and random variables X, Y, regardless of independence. This simplifies expectations of sums, e.g., the number of successes in n Bernoulli trials: E[X] = Σ E[Iᵢ] = n·p, where Iᵢ indicates success on trial i.
Variance measures spread: Var(X) = E[(X − E[X])²] = E[X²] − (E[X])². For independent variables, variances add: Var(X+Y) = Var(X) + Var(Y). Covariance Cov(X,Y) = E[XY] − E[X]E[Y] quantifies linear dependence; the correlation coefficient ρ = Cov(X,Y)/√(Var(X)Var(Y)) lies in [−1,1].
Moment generating functions (MGFs) encapsulate all moments. The MGF of X is M_X(t) = E[etX], defined for t near 0. The k‑th moment is E[Xᵏ] = M_X(k)(0). For independent X, Y, MX+Y(t) = M_X(t) M_Y(t), making MGFs ideal for sums of independent variables.
Common MGFs: Binomial(n,p): M(t) = (1−p + p e^t)ⁿ. Poisson(λ): M(t) = exp(λ(e^t−1)). Exponential(λ): M(t) = λ/(λ−t) for t<λ. Normal(μ,σ²): M(t) = exp(μt + ½σ²t²). The MGF of a sum of independent Poissons is Poisson with parameter equal to the sum of the individual parameters, confirming the reproductive property.
Probability generating functions (PGFs) are used for non‑negative integer‑valued variables: G_X(s) = E[s^X] = Σ P(X=k) s^k. The PGF of a sum of independent variables is the product of their PGFs. Factorial moments come from derivatives at s=1: E[X(X−1)…(X−k+1)] = G_X(k)(1). For Binomial(n,p), G(s) = (1−p + ps)ⁿ; for Poisson(λ), G(s) = eλ(s−1).
Generating functions also solve recurrence relations for probabilities. For example, the extinction probability in a branching process is the smallest non‑negative root of s = G(s), where G is the PGF of the offspring distribution.
In examinations, questions often ask for the expectation or variance of a function of a random variable, or to identify a distribution from its MGF or PGF. Recognizing standard MGFs/PGFs and using their algebraic properties (product for sums, composition for mixtures) can dramatically reduce computation.
Common Traps
- Forgetting to divide by 2 when counting necklaces with reflection symmetry for n > 2.
- Applying the binomial coefficient formula to multinomial problems without adjusting for multiple categories.
- Confusing the inclusion–exclusion sign pattern: the term for k sets has sign (−1)k+1.
- Using the derangement approximation n!/e without rounding to the nearest integer, leading to off‑by‑one errors.
- Assuming independence when computing expectation of a product; E[XY] = E[X]E[Y] holds only for independent variables.
- Misapplying the multinomial theorem by omitting the factorial denominator for repeated items.
- Neglecting the condition P(B) > 0 when writing conditional probability formulas in multi‑step Bayes problems.
Mastering these advanced counting and probability techniques ensures a robust toolkit for tackling the most challenging combinatorial problems.