Fundamental Rules of Combinatorics. Permutations

In how many ways can the students in your class line up one after another in the cafeteria queue? In how many ways can you choose a class president and vice president? In how many ways can gold, silver, and bronze medals be distributed at the FIFA World Cup?

To answer these questions, we need to count how many different combinations, formed according to a certain rule, can be made from elements of a given finite set. The branch of mathematics that deals with such counting problems is called combinatorics.

At the core of solving most combinatorial problems are two rules: the sum rule and the product rule.

The Sum Rule

📐Definition — The Sum Rule

If sets $A$ and $B$ are such that $n(A) = m$ , $n(B) = k$ , and $A \cap B = \varnothing$ , then the choice of ” $a$ or $b$ ”, where $a \in A$ , $b \in B$ , can be made in $m + k$ ways.

This rule can be illustrated using the well-known property: if sets $A$ and $B$ are finite and $A \cap B = \varnothing$ , then $n(A \cup B) = n(A) + n(B)$ .

The sum rule generalizes naturally. If sets $A_1, A_2, \ldots, A_m$ are pairwise disjoint with $n(A_1) = k_1$ , $n(A_2) = k_2$ , …, $n(A_m) = k_m$ , then the choice of ” $a_1$ , or $a_2$ , or …, or $a_m$ ” can be made in $k_1 + k_2 + \ldots + k_m$ ways.

✎Example — Tourist Routes

Statement. A tourist is interested in 5 routes through the Dnieper region and 7 routes through the Carpathians. In how many ways can they plan their vacation if they have time for only one route?

Solution. Since there are $5 + 7 = 12$ different routes in total, one of them can be chosen in 12 ways.

Answer: 12 ways.

The Product Rule

📐Definition — The Product Rule

If element $a$ can be chosen in $m$ ways, and after each such choice element $b$ can be chosen in $k$ ways, then the choice of ” $a$ and $b$ ” in the specified order, i.e., the choice of the ordered pair $(a; b)$ , can be made in $mk$ ways.

The product rule also generalizes naturally. If element $a_1$ can be chosen in $k_1$ ways, element $a_2$ in $k_2$ ways, and so on, element $a_m$ in $k_m$ ways (with the independence principle), then the choice of the ordered tuple $(a_1; a_2; \ldots; a_m)$ can be made in $k_1 \cdot k_2 \cdot \ldots \cdot k_m$ ways.

✎Example 1 — Number of Divisors

Statement. How many natural divisors does the number $2^4 \cdot 5^3 \cdot 7^6$ have?

Solution. Any divisor of this number has the form $2^{k_1} \cdot 5^{k_2} \cdot 7^{k_3}$ , where $k_1, k_2, k_3$ are integers satisfying $0 \leqslant k_1 \leqslant 4$ , $0 \leqslant k_2 \leqslant 3$ , $0 \leqslant k_3 \leqslant 6$ .

The number $k_1$ can be chosen in 5 ways, $k_2$ in 4 ways, $k_3$ in 7 ways. By the generalized product rule, the total number of divisors is $5 \cdot 4 \cdot 7 = 140$ .

Answer: 140 divisors.

Ordered Sets

📐Definition — Ordered Set

A set $M$ consisting of $n$ elements ( $n \in \mathbb{N}$ ) is called ordered if a one-to-one correspondence has been established between it and the set of the first $n$ natural numbers.

Permutations

📐Definition — Permutation

A permutation of a finite set $M$ is any ordered set formed from all elements of $M$ .

For example, there are 6 permutations of the set $M = \{a, b, c\}$ :

$(a; b; c)$ , $(a; c; b)$ , $(b; a; c)$ , $(b; c; a)$ , $(c; a; b)$ , $(c; b; a)$ .

Permutations of a given finite set differ only in the order of their elements.

The number of permutations of an $n$ -element set $M$ is denoted by $P_n$ , using the first letter of the French word permutation.

⚡Theorem — Number of Permutations

For any natural number $n$ , the following formula holds:

P_n = n!

where $n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ (read: ” $n$ factorial”). By convention, $0! = 1$ and $1! = 1$ .

Proof. Let the set $M$ consist of $n$ elements. Writing any permutation of $M$ is essentially assigning each element a unique number from 1 to $n$ . Choose an element $a$ from $M$ . There are $n$ ways to assign it a number. Next, choose element $b$ — there are $n - 1$ remaining choices. Continuing this reasoning, the last unchosen element has exactly one available number. By the generalized product rule:

P_n = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!

✎Example 2 — Eight Rooks on a Chessboard

Statement. In how many ways can 8 rooks be placed on a chessboard so that no two attack each other?

Solution. For no two rooks to attack each other, there must be exactly one rook on each row and each column. Let $a_1$ be the column number where the rook on the first row stands, $a_2$ be the column for the second row, …, $a_8$ for the eighth row.

Then $(a_1; a_2; \ldots; a_8)$ is a permutation of the set $\{1, 2, \ldots, 8\}$ . Each such permutation corresponds to a valid placement of rooks.

Therefore, the number of ways is $P_8 = 8! = 40\,320$ .

Answer: $8! = 40\,320$ .

✏Exercise — Permutation Problems

In how many ways can 7 different books be arranged on a shelf?
In how many ways can 5 people sit in a car if any of them can be the driver?
A school has 20 classes and 20 class teachers. In how many ways can class supervision be distributed among the teachers?
How many five-digit numbers can be formed using the digits 1, 2, 3, 4, 5 with no digit repeated?