Arrangements

According to FIFA rules, 32 teams participate in the final stage of the Football World Cup. Let us determine in how many ways the gold, silver, and bronze medals (three prize positions) can be distributed among the teams.

The first place can be taken by any of the 32 teams, the second by any of the remaining 31, and the third by any of the 30 remaining teams. By the generalized product rule, the number of possible distributions is $32 \cdot 31 \cdot 30 = 29\,760$ .

Each such ordered subset is called an arrangement of 3 elements chosen from 32 elements.

Definition and Formula

📐Definition — Arrangement

Any $k$ -element ordered subset of a given $n$ -element set is called an arrangement (or $k$ -permutation) of $n$ elements taken $k$ at a time.

The number of all possible arrangements of $n$ elements taken $k$ at a time is denoted by $A_n^k$ , using the first letter of the French word arrangement.

⚡Theorem — Formula for the Number of Arrangements

For any natural numbers $n$ and $k$ such that $k \leqslant n$ , the following formula holds:

A_n^k = n(n-1)(n-2) \cdot \ldots \cdot (n-k+1)

Proof. Consider an $n$ -element set and form its $k$ -element ordered subset. There are $n$ ways to choose the first element. After the first element is chosen, the second can be chosen in $n - 1$ ways. After the first two elements are chosen, there are $n - 2$ ways for the third, and so on. The $k$ -th element can be chosen in $n - k + 1$ ways.

By the generalized product rule:

A_n^k = n(n-1)(n-2) \cdot \ldots \cdot (n-k+1).

Relationship with Factorials and Permutations

Since there is only one $n$ -element subset of an $n$ -element set, the number $A_n^n$ equals the number of permutations:

A_n^n = P_n.

Multiplying and dividing the right side by $(n - k)!$ (which is valid since $(n-k)! \neq 0$ ), we obtain the compact formula:

A_n^k = \frac{n!}{(n-k)!}

✎Example — Proper Fractions with Prime Numerators and Denominators

Statement. How many proper fractions exist whose numerator and denominator are both prime numbers less than 30?

Solution. The set $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}$ consists of all prime numbers less than 30. The number of 2-element ordered subsets of this set equals the number of ordinary fractions (other than 1) whose numerator and denominator are these prime numbers. Half of these fractions are proper.

Therefore, the answer is $\dfrac{1}{2} A_{10}^2 = \dfrac{1}{2} \cdot 10 \cdot 9 = 45$ .

Answer: 45.

✏Exercise — Arrangement Problems

In a football team (11 players), a captain and a vice-captain need to be chosen. In how many ways can this be done?
A committee of 15 people must choose a chairperson, a deputy, and a secretary. In how many ways can this be done?
In 9th grade, students study 18 subjects. The daily schedule contains 6 lessons. In how many ways can the daily schedule be arranged so that all 6 lessons are different subjects?