Back to Course
Permutation and Probability
Fundamental Counting Principle and Factorials
The Fundamental Counting Principle (FCP) states that if one event can occur in $p$ ways and, after it has occurred, a second event can occur in $q$ ways, then the total number of ways for the sequence is the product $p \times q$.
$$n! = n \times (n-1) \times (n-2) \dots 1$$
Factorial notation represents the product of all positive integers up to $n$.
$n!$=$n$ factorial — product of all integers from $1$ to $n$(unitless)
$0!$=Zero factorial, defined as $1$ by convention(unitless)
$n = 0$
→$0! = 1$ — required for consistent formulas like $P(n, n) = \frac{n!}{0!} = n!$
Sequential Choices: FCP applies to any sequence of choices — whether the pool shrinks (without replacement) or stays the same (with replacement).
Factorial as Arrangement Count: $n!$ gives the number of ways to arrange $n$ distinct objects in a line.
Recursive Definition: $n! = n \times (n-1)!$, so $5! = 5 \times 4! = 5 \times 24 = 120$.
Simplification Shortcut: $\frac{n!}{(n-r)!}$ cancels to the product of $r$ descending factors: $\frac{8!}{5!} = 8 \times 7 \times 6 = 336$.
Permutations: When Order Matters
A Permutation is an ordered arrangement of a set of distinct objects. Changing the sequence (e.g., ABC vs BCA) produces a different permutation.
$$^nP_r = \frac{n!}{(n-r)!}$$
Calculates the number of ways to arrange $r$ objects chosen from $n$ unique objects, where order matters.
$n$=Total number of distinct items available(count)
$r$=Number of items to arrange ($r \le n$)(count)
$r = n$
→$^nP_n = n!$ — arranging all items
$r = 1$
→$^nP_1 = n$ — just choosing one item
Descending Product: $^nP_r$ equals $r$ consecutive integers multiplied: $^6P_4 = 6 \times 5 \times 4 \times 3 = 360$.
Useful Identity: $^nP_r = n \cdot ^{n-1}P_{r-1}$ — fix one item first, then arrange the rest.
Permutations with Repeated and Circular Arrangements
When the set contains Identical Items, swapping them does not create a new arrangement. We divide $n!$ by the factorials of each group's count to remove duplicates.
$$\text{Arrangements} = \frac{n!}{n_1! \, n_2! \dots n_k!}$$
Counts distinct permutations when some objects are indistinguishable.
$n$=Total number of objects(count)
$n_i$=Number of identical objects in group $i$(count)
All objects distinct ($n_i = 1$ for all $i$)
→Reduces to $n!$ since each $n_i! = 1$
Why Divide?: If a letter appears $k$ times, those $k$ copies can be rearranged among themselves in $k!$ ways without producing a visibly new arrangement. Dividing removes this overcounting.
MISSISSIPPI Example: 11 letters with I×4, S×4, P×2, M×1 gives $\frac{11!}{4! \cdot 4! \cdot 2! \cdot 1!} = 34650$.
In a Circular Permutation, rotating all objects by the same amount does not produce a new arrangement. We fix one object's position to eliminate rotational symmetry.
$$(n-1)!$$
Number of distinct ways to arrange $n$ objects in a circle.
$(n-1)!$=Fix one object, arrange the remaining $n-1$(count)
Necklace or key ring (can flip over)
→Divide by 2: $\frac{(n-1)!}{2}$ — clockwise and anticlockwise arrangements are identical.
Why $(n-1)!$?: In a line, ABCD and BCDA are different. At a round table, they are the same rotation. Fixing one person removes this redundancy.
Necklace vs Table: A necklace can be flipped, so clockwise = anticlockwise. Divide $(n-1)!$ by 2. A table cannot be flipped, so use $(n-1)!$.
Constraint Handling: If two people must sit together at a round table, treat them as one unit. For $n$ total people: $(n-2)! \times 2!$ (fix combined unit, arrange rest, swap internal order).
Combinations: When Order Does Not Matter
A Combination is a selection of $r$ objects from $n$ distinct objects where the order of selection is irrelevant. Choosing {A, B, C} is the same as choosing {C, A, B}.
$$^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$
Counts the number of ways to choose $r$ items from $n$ without regard to order.
$n$=Total number of distinct items(count)
$r$=Number of items to choose(count)
$r!$=Divides out the internal orderings of the chosen group(count)
$r = 0$ or $r = n$
→$^nC_0 = ^nC_n = 1$ — only one way to choose nothing or everything
$r = 1$
→$^nC_1 = n$ — choosing one item from $n$
Permutation vs Combination: Permutation = arrangement (order matters). Combination = selection (order doesn't matter). A committee of 3 from 10 is $^{10}C_3$, but assigning President/VP/Secretary from 10 is $^{10}P_3$.
Complementary Property: $^nC_r = ^nC_{n-r}$ — choosing $r$ items to include is equivalent to choosing $n-r$ items to exclude. Use this when $r > n/2$ to simplify: $^{12}C_{10} = ^{12}C_2 = 66$.
Pascal's Identity: $^{n-1}C_r + ^{n-1}C_{r-1} = ^nC_r$ — the basis for Pascal's triangle.
Computational Shortcut: $^nC_r = \frac{n(n-1)\dots(n-r+1)}{r!}$ — multiply $r$ descending factors, then divide by $r!$. For $^{20}C_{17}$, use $^{20}C_3 = \frac{20 \times 19 \times 18}{3!} = 1140$.
Combinations are used to count selections in geometry (diagonals, triangles from vertices) and in forming groups with constraints.
Diagonals of a Polygon: Total line segments from $n$ vertices = $^nC_2$. Subtract $n$ sides to get diagonals: $^nC_2 - n = \frac{n(n-3)}{2}$.
Triangles from Vertices: Number of triangles = $^nC_3$ (choose any 3 non-collinear vertices).
Constrained Selection: To form a committee that must include 2 specific people from 8, choose the remaining members: $^{8-2}C_{5-2} = ^6C_3 = 20$.
Finding $n$ from $^nC_r$: If $^nC_a = ^nC_b$, then either $a = b$ or $a + b = n$ (by the complementary property).
Probability Fundamentals
Probability is the numerical measure of the likelihood that an event occurs, based on the ratio of favorable outcomes to total outcomes in a Sample Space of Equally Likely outcomes.
$$P(E) = \frac{n(E)}{n(S)}$$
The classical (Laplace) definition of probability for equally likely outcomes.
$n(E)$=Number of outcomes favorable to event $E$(count)
$n(S)$=Total number of outcomes in the sample space(count)
$P(E) = 0$
→Impossible event — cannot occur
$P(E) = 1$
→Certain event — guaranteed to occur
Range: $0 \le P(E) \le 1$ always. If you calculate a probability outside this range, recheck your work.
Complement Rule: $P(\bar{E}) = 1 - P(E)$ — the probability that event $E$ does NOT occur. Often easier to compute.
Sample Space Examples: Coin toss: $S = \{H, T\}$, $n(S) = 2$. Die roll: $S = \{1,2,3,4,5,6\}$, $n(S) = 6$. Two dice: $n(S) = 36$.
Two events are Mutually Exclusive if they cannot occur at the same time — their intersection is empty ($A \cap B = \emptyset$).
Disjoint Sets: If $A$ and $B$ are mutually exclusive, then $P(A \cap B) = 0$.
Example: Rolling a single die — the events 'getting 2' and 'getting 5' are mutually exclusive.
Non-Example: 'Getting an even number' and 'getting a number > 3' are NOT mutually exclusive because 4 and 6 satisfy both.
Addition and Multiplication Rules of Probability
The Addition Rule calculates the probability that at least one of two events occurs. For overlapping events, subtract the intersection to avoid double-counting.
$$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$
Probability of event $A$ OR event $B$ (or both) occurring.
$P(A \cup B)$=Probability of $A$ or $B$ occurring(probability)
$P(A \cap B)$=Probability of both $A$ and $B$ occurring (overlap)(probability)
$A$ and $B$ are mutually exclusive
→$P(A \cap B) = 0$, so $P(A \cup B) = P(A) + P(B)$
Disjoint Case: When events cannot overlap, simply add their probabilities: $P(A \cup B) = P(A) + P(B)$.
Overlapping Case: When events can co-occur, subtracting $P(A \cap B)$ prevents counting the overlap twice.
Example: Die roll — $P(\text{prime or odd}) = P(\{2,3,5\}) + P(\{1,3,5\}) - P(\{3,5\}) = \frac{3}{6} + \frac{3}{6} - \frac{2}{6} = \frac{2}{3}$.
For Independent Events, the probability that both occur is the product of their individual probabilities.
$$P(A \cap B) = P(A) \times P(B)$$
Probability of event $A$ AND event $B$ both occurring, when they are independent.
$P(A)$=Probability of event $A$(probability)
$P(B)$=Probability of event $B$(probability)
Multiple independent events $A_1, A_2, \dots, A_n$
→$P(A_1 \cap A_2 \cap \dots \cap A_n) = P(A_1) \times P(A_2) \times \dots \times P(A_n)$
Independence Defined: Two events are Independent Events if the occurrence of one does not affect the probability of the other.
With vs Without Replacement: Drawing with replacement keeps events independent (pool stays the same). Drawing without replacement makes events dependent (pool changes).
Example: Tossing a coin twice — $P(\text{Head then Head}) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$.