Permutations and Combinations

Combinatorics is the branch of mathematics dealing with counting, arrangement, and selection. Before invoking algebraic formulas, systematic enumeration relies upon two foundational counting axioms.

Generalization: If there are $k$ successive events where the first can occur in $n_1$ ways, the second in $n_2$ ways, ..., and the $k$-th in $n_k$ ways, then the total number of ways in which all $k$ events can occur in sequence is:

Example: Finding the number of 3-digit numbers that can be formed from digits $\{1, 2, 3, 4, 5\}$ without repetition:

• Hundreds place: 5 choices ($1, 2, 3, 4, 5$)
• Tens place: 4 remaining choices
• Units place: 3 remaining choices
• Total 3-digit numbers $= 5 \times 4 \times 3 = \mathbf{60}$.

Distinguishing "AND" versus "OR":

• Multiplication Rule ($\times$): Corresponds to logical "AND" (both events occur in succession/jointly).
• Addition Rule ($+$): Corresponds to logical "OR" (mutually exclusive alternatives, where only one occurs).

The notation $n!$ (read as "$n$ factorial") provides the essential compact notation for products of consecutive positive integers.

For any natural number $n \in \mathbb{N}$, the factorial of $n$ is defined as the product of the first $n$ natural numbers:

Alternatively written in descending order:

First Few Factorial Values to Memorize:

For any integer $n \ge 1$, we can factor out $n$:

Substituting $n = 1$ into this relation reveals why zero factorial equals 1:

Factorials are undefined for negative integers because substituting $n = 0$ yields $(-1)! = \frac{0!}{0} = \frac{1}{0}$ (undefined division by zero).

• $(a + b)! \neq a! + b!$ (e.g., $(2 + 3)! = 5! = 120 \neq 2! + 3! = 2 + 6 = 8$).
• $(a \times b)! \neq a! \times b!$.
• Simplifying factorial fractions: $\frac{n!}{(n - 2)!} = \frac{n(n - 1)(n - 2)!}{(n - 2)!} = n(n - 1) = n^2 - n$.

A permutation is an arrangement of a number of objects in a definite order, taken some or all at a time. In permutations, ORDER MATTERS FUNDAMENTALLY (e.g., the arrangement $AB$ is distinct from $BA$).

The number of permutations of $n$ distinct objects taken $r$ at a time ($0 \le r \le n$) without repetition is denoted by $^n P_r$ or $P(n, r)$:

Proof Sketch: Filling $r$ vacant positions using $n$ distinct objects:

• 1st position: $n$ choices
• 2nd position: $(n - 1)$ choices
• $r$-th position: $[n - (r - 1)] = (n - r + 1)$ choices
• By the product rule: $^n P_r = n(n - 1) \cdots (n - r + 1) = \frac{n(n - 1)\cdots(n - r + 1)(n - r)!}{(n - r)!} = \frac{n!}{(n - r)!}$.

Special Values:

• $^n P_0 = \frac{n!}{n!} = \mathbf{1}$
• $^n P_1 = \frac{n!}{(n - 1)!} = \mathbf{n}$
• $^n P_n = \frac{n!}{(n - n)!} = \frac{n!}{0!} = \frac{n!}{1} = \mathbf{n!}$ (Arranging all $n$ distinct objects in a row).

The number of permutations of $n$ distinct objects taken $r$ at a time when each object may be repeated any number of times is:

Classic Example: Arranging the letters of the word "MATHEMATICS":

• Total letters $n = 11$.
• Identical subsets: M occurs 2 times, A occurs 2 times, T occurs 2 times, and H, E, I, C, S occur 1 time each.
• Total distinct permutations $= \frac{11!}{2! \, 2! \, 2!} = \frac{39916800}{8} = \mathbf{4,989,600}$.

When arranging $n$ distinct objects along a closed circle rather than a linear row, shifting every object one position does not produce a new arrangement because there are no fixed ends:

1. Distinct Orientations (Clockwise $\neq$ Anti-clockwise): Arranging $n$ distinct persons around a circular dining table: $$\mathbf{\text{Circular Permutations} = (n - 1)!}$$
2. Indistinguishable Orientations (Necklaces / Garlands): Where flipping the necklace turns a clockwise arrangement into an anti-clockwise one: $$\mathbf{\text{Circular Permutations} = \frac{(n - 1)!}{2}}$$

In board examinations and competitive tests, permutation problems rarely ask for raw formulas; they almost always impose specific restrictions on arrangements.

When certain specified items must always occur together in an arrangement:

Example: In how many ways can 5 boys and 4 girls be arranged in a row such that all 4 girls sit together?

• Treat the 4 girls as 1 composite block. Total objects to arrange: 5 boys + 1 block = 6 objects.
• Ways to arrange 6 objects $= 6! = 720$.
• Ways to arrange the 4 girls among themselves inside the block $= 4! = 24$.
• By the product rule, total arrangements $= 6! \times 4! = 720 \times 24 = \mathbf{17,280}$.

When certain items must NEVER sit adjacent to one another (no two items together):

Example: In how many ways can 5 boys and 4 girls sit in a row such that no two girls sit together?

• First arrange the 5 boys: $5! = 120$ ways.
• The 5 boys create $5 + 1 = 6$ gaps: $\underline{\phantom{x}} B_1 \underline{\phantom{x}} B_2 \underline{\phantom{x}} B_3 \underline{\phantom{x}} B_4 \underline{\phantom{x}} B_5 \underline{\phantom{x}}$.
• The 4 girls must be seated in 4 of these 6 gaps: $^6 P_4 = \frac{6!}{2!} = 360$ ways.
• Total arrangements $= 5! \times \, ^6 P_4 = 120 \times 360 = \mathbf{43,200}$.

To find the alphabetical rank of a word (e.g., "MOTHER") when all its anagrams are arranged in dictionary order:

1. List the constituent letters in alphabetical order: E, H, M, O, R, T.
2. Words beginning with E: $1 \times 5! = 120$ words.
3. Words beginning with H: $1 \times 5! = 120$ words.
4. Words beginning with M followed by E: $1 \times 4! = 24$ words; followed by H: $24$; followed by O: match found!
5. Continue successively for O, T, H, E, R to sum preceding counts and add $1$ for the word itself.

A combination is a selection or grouping of a number of objects where the order of selection DOES NOT MATTER. Selecting players $\{A, B\}$ for a doubles tennis team is identical to selecting $\{B, A\}$.

The number of combinations of $n$ distinct objects taken $r$ at a time ($0 \le r \le n$) is denoted by $^n C_r$ or $C(n, r)$:

Fundamental Relation between Permutations and Combinations:

Every combination of $r$ objects can be arranged among themselves in $r!$ ways to yield permutations:

Combinatorics demonstrates immense problem-solving power when applied to geometric configurations and distribution of objects into distinct or identical groups.

1. Number of Straight Lines: The number of straight lines formed by joining $n$ points in a plane, of which $m$ points are collinear: $$\mathbf{\text{Lines} = \, ^n C_2 - \, ^m C_2 + 1}$$ (The $m$ collinear points yield only 1 straight line instead of $^m C_2$).
2. Number of Triangles: The number of triangles formed by joining $n$ points, of which $m$ points are collinear: $$\mathbf{\text{Triangles} = \, ^n C_3 - \, ^m C_3}$$ (Collinear points cannot form triangles, yielding 0 triangles).
3. Number of Diagonals in an $n$-sided Polygon: Connecting any 2 vertices gives a line segment ($^n C_2$). Subtracting the $n$ perimeter sides yields the diagonals: $$\mathbf{\text{Diagonals} = \, ^n C_2 - n = \frac{n(n - 1)}{2} - n = \frac{n(n - 3)}{2}}$$
4. Number of Parallelograms: Formed by a set of $m$ parallel lines intersecting another set of $n$ parallel lines: $$\mathbf{\text{Parallelograms} = \, ^m C_2 \times \, ^n C_2}$$