Chapter Review

Permutation, Combination, and Probability

Permutation and Probability · Binomial Theorem

Fundamental Counting Principle and Factorials

The FCP states that sequential choices multiply: if one event has $p$ outcomes and a second has $q$, the total is $p \times q$. Factorials ($n!$) count the total arrangements of $n$ distinct objects.

Key Points

•
$n! = n \times (n-1) \times \dots \times 1$, with the convention $0! = 1$
•
FCP extends to any number of sequential stages — multiply the counts at each stage
•
Recursive relation: $n! = n \times (n-1)!$
•
Cancellation shortcut: $\frac{n!}{(n-r)!}$ equals $r$ descending factors from $n$

Formula

$$n! = n \times (n-1) \times (n-2) \dots \times 1$$

Permutations (Order Matters)

A permutation is an ordered arrangement of $r$ objects chosen from $n$ distinct objects. Changing the order produces a different permutation.

Key Points

•
$^nP_r = \frac{n!}{(n-r)!}$ — product of $r$ descending factors from $n$
•
$^nP_n = n!$ (arrange all items); $^nP_1 = n$ (choose one)
•
Relationship: $^nP_r = r! \times ^nC_r$
•
With repetition allowed, the count becomes $n^r$ instead

Formula

$$^nP_r = \frac{n!}{(n-r)!}$$

Permutations with Repetition and Circular Arrangements

When objects repeat, divide $n!$ by the factorials of each group's count to remove overcounting. In circular arrangements, fix one object to eliminate rotational symmetry.

Key Points

•
Repeated items: $\frac{n!}{n_1! \, n_2! \dots n_k!}$ distinct arrangements
•
Circular permutation: $(n-1)!$ — fix one, arrange the rest
•
Necklace/keyring (flippable): $\frac{(n-1)!}{2}$
•
Adjacent constraint at round table: treat the group as one unit, then multiply by internal arrangements

Formula

$$\text{Circular} = (n-1)! \qquad \text{Repeated} = \frac{n!}{n_1! \, n_2! \dots n_k!}$$

Combinations (Order Does Not Matter)

A combination is an unordered selection of $r$ objects from $n$. Choosing {A, B, C} is the same as {C, A, B}.

Key Points

•
$^nC_r = \frac{n!}{r!(n-r)!}$
•
Complementary property: $^nC_r = ^nC_{n-r}$ — use when $r > n/2$
•
Pascal's Identity: $^{n-1}C_r + ^{n-1}C_{r-1} = ^nC_r$
•
$^nC_0 = ^nC_n = 1$; $^nC_1 = n$
•
If $^nC_a = ^nC_b$, then $a = b$ or $a + b = n$

Formula

$$^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Combination Applications (Geometry and Constraints)

Combinations count selections in geometry (diagonals, triangles) and constrained group formation problems.

Key Points

•
Diagonals of an $n$-gon: $\frac{n(n-3)}{2}$
•
Triangles from $n$ vertices: $^nC_3$
•
Constrained selection: fix required members, choose remaining from the rest
•
Committee vs ranked positions: committee = combination, ranked roles = permutation

Probability Fundamentals

Probability measures the likelihood of an event as the ratio of favorable outcomes to total equally likely outcomes in the sample space.

Key Points

•
$P(E) = \frac{n(E)}{n(S)}$, always satisfying $0 \le P(E) \le 1$
•
Complement rule: $P(\bar{E}) = 1 - P(E)$
•
Mutually exclusive events: $A \cap B = \emptyset$, so $P(A \cap B) = 0$
•
Mutually exclusive ≠ independent — disjoint events are actually dependent

Formula

$$P(E) = \frac{n(E)}{n(S)}$$

Addition and Multiplication Rules

The addition rule handles "or" (union) of events, subtracting overlap. The multiplication rule handles "and" (intersection) of independent events by multiplying probabilities.

Key Points

•
Addition: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
•
If mutually exclusive: $P(A \cup B) = P(A) + P(B)$
•
Multiplication (independent): $P(A \cap B) = P(A) \times P(B)$
•
With replacement → independent; without replacement → dependent
•
Extends to $n$ independent events: multiply all individual probabilities

Formula

$$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

Binomial Theorem (Positive Integer Index)

The Binomial Theorem expands $(a+x)^n$ into $n+1$ terms, each weighted by a binomial coefficient with complementary powers of $a$ and $x$.

Key Points

•
$(a+x)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} x^r$
•
General term: $T_{r+1} = \binom{n}{r} a^{n-r} x^r$ (set $r = k-1$ for the $k$-th term)
•
Exponents of $a$ and $x$ always sum to $n$ in every term
•
Coefficient symmetry: $\binom{n}{r} = \binom{n}{n-r}$
•
Sum of all coefficients: $2^n$; alternating sum: $0$

Formula

$$T_{r+1} = \binom{n}{r} a^{n-r} x^r$$

Special Terms in Binomial Expansion

The independent term (constant term) and middle term(s) are found by analyzing the exponent of $x$ in the general term.

Key Points

•
Independent term: set the net power of $x$ in $T_{r+1}$ to zero, solve for $r$
•
Coefficient of $x^p$: set the net power of $x$ equal to $p$
•
Even $n$: one middle term at position $\frac{n}{2}+1$
•
Odd $n$: two middle terms at positions $\frac{n+1}{2}$ and $\frac{n+3}{2}$
•
For $(a-x)^n$, raise the entire $(-x)^r$ — odd $r$ gives negative terms

Binomial Series (Fractional/Negative Index)

When $n$ is fractional or negative, $(1+x)^n$ expands as an infinite series that converges only when $|x| < 1$.

Key Points

•
$(1+x)^n = 1 + nx + \frac{n(n-1)}{2!}x^2 + \frac{n(n-1)(n-2)}{3!}x^3 + \dots$
•
Use descending product form, not $\binom{n}{r}$, for non-integer $n$
•
To expand $(a+bx)^n$: factor out $a^n$ to get $a^n(1+\frac{bx}{a})^n$, then apply the series
•
First-order approximation: $(1+x)^n \approx 1 + nx$ for small $|x|$
•
$(1-x)^{-1} = 1 + x + x^2 + x^3 + \dots$ — the geometric series

Formula

$$(1+x)^n = 1 + nx + \frac{n(n-1)}{2!}x^2 + \frac{n(n-1)(n-2)}{3!}x^3 + \dots \quad (|x|<1)$$

Formulas

Permutation Formula

Ordered arrangements of $r$ items from $n$ distinct items.

Formula

$$^nP_r = \frac{n!}{(n-r)!}$$

Combination Formula

Unordered selections of $r$ items from $n$ distinct items.

Formula

$$^nC_r = \frac{n!}{r!(n-r)!}$$

Repeated Items Permutation

Distinct arrangements when some objects are identical.

Formula

$$\frac{n!}{n_1! \, n_2! \dots n_k!}$$

Circular Permutation

Arrangements of $n$ items around a circle.

Formula

$$(n-1)!$$

Addition Rule

Probability of $A$ or $B$ occurring, subtracting the overlap.

Formula

$$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

Binomial General Term

The $(r+1)$-th term of $(a+x)^n$ directly.

Formula

$$T_{r+1} = \binom{n}{r} a^{n-r} x^r$$

Binomial Series (Non-Integer Index)

Infinite expansion valid for $|x| < 1$.

Formula

$$(1+x)^n = 1 + nx + \frac{n(n-1)}{2!}x^2 + \frac{n(n-1)(n-2)}{3!}x^3 + \dots$$

Complement Probability

Probability that an event does NOT occur.

Formula

$$P(\bar{E}) = 1 - P(E)$$