Комбинаторика: правило умножения, перестановки, сочетания

Определение. Комбинаторика

Комбинаторика — раздел математики, изучающий способы подсчёта числа различных комбинаций объектов. В теории вероятностей комбинаторные формулы позволяют находить число благоприятных исходов и общее число исходов в задачах с равновозможными элементарными событиями.

Формула. Правило умножения

Если первое действие можно выполнить $n$ способами, а второе — $m$ способами (независимо от первого), то оба действия вместе можно выполнить $n \cdot m$ способами.

Для $k$ действий:

$N = n_1 \cdot n_2 \cdot \dots \cdot n_k$

Формула. Перестановки

Перестановкой $n$ элементов называется любой упорядоченный набор из всех $n$ элементов. Число всех перестановок:

$P_n = n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$

Формула. Размещения

Размещением из $n$ по $k$ ($k \leq n$) называется упорядоченный набор $k$ различных элементов, выбранных из $n$ различных. Число размещений:

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

На практике удобнее: $A_n^k = n \cdot (n-1) \cdot \dots \cdot (n-k+1)$ — произведение $k$ последовательных чисел, начиная с $n$.

Формула. Сочетания

Сочетанием из $n$ по $k$ ($k \leq n$) называется неупорядоченный набор $k$ различных элементов, выбранных из $n$ различных. Число сочетаний:

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

Сочетания и размещения связаны: $A_n^k = C_n^k \cdot k!$ (каждую неупорядоченную группу можно упорядочить $k!$ способами).

Обозначения

Символ	Название	Описание
$n!$	Факториал	Произведение всех натуральных чисел от 1 до $n$
$P_n$	Число перестановок	Число способов упорядочить $n$ элементов
$A_n^k$	Число размещений	Число упорядоченных выборок $k$ из $n$
$C_n^k$	Число сочетаний	Число неупорядоченных выборок $k$ из $n$

Пример 1. Перестановки

Сколько способов рассадить 5 человек в ряд на 5 стульев?

Дано: $n = 5$ человек, нужно упорядочить всех.

Формула: $P_n = n!$

Подстановка: $P_5 = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

Ответ: $120$ способов.

Пример 2. Размещения

В легкоатлетическом забеге участвуют 8 спортсменов. Сколько существует вариантов распределения золотой, серебряной и бронзовой медалей?

Дано: $n = 8$ спортсменов, $k = 3$ медали (порядок важен: золото, серебро, бронза).

Формула: $A_n^k = n \cdot (n-1) \cdot \dots \cdot (n-k+1)$

Подстановка: $A_8^3 = 8 \cdot 7 \cdot 6 = 336$

Ответ: $336$ вариантов.

Пример 3. Сочетания

Из 6 учеников нужно выбрать 2 для участия в олимпиаде. Сколько существует способов выбора?

Дано: $n = 6$ учеников, $k = 2$ участника (порядок не важен).

Формула: $C_n^k = \dfrac{n!}{k!(n-k)!}$

Подстановка: $C_6^2 = \dfrac{6!}{2! \cdot 4!} = \dfrac{720}{2 \cdot 24} = \dfrac{720}{48} = 15$

Ответ: $15$ способов.

Определение. Треугольник Паскаля

Числа сочетаний $C_n^k$ удобно располагать в виде треугольной таблицы — треугольника Паскаля. В нулевой строке стоит $C_0^0 = 1$. В $n$-й строке по порядку стоят числа $C_n^0, C_n^1, \dots, C_n^n$:

           1
         1   1
       1   2   1
     1   3   3   1
   1   4   6   4   1
 1   5  10  10   5   1

Каждое число внутри треугольника равно сумме двух чисел, стоящих над ним слева и справа. Это свойство выражается формулой сложения сочетаний:

$C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$

Формула. Свойства треугольника Паскаля

1. Симметрия: $C_n^k = C_n^{n-k}$ — строка читается одинаково слева направо и справа налево (например, $C_5^1 = C_5^4 = 5$).
2. Сумма строки: сумма всех чисел $n$-й строки равна $2^n$:

$\sum_{k=0}^{n} C_n^k = C_n^0 + C_n^1 + \dots + C_n^n = 2^n$

Например, в строке $n = 4$: $1 + 4 + 6 + 4 + 1 = 16 = 2^4$. 3. Края строки: $C_n^0 = C_n^n = 1$ — по краям треугольника всегда стоят единицы.

Пример 4. Сумма строки треугольника Паскаля

Чему равна сумма всех чисел в 6-й строке треугольника Паскаля?

Дано: номер строки $n = 6$.

Формула: сумма строки $= 2^n$

Подстановка: $2^6 = 64$

Ответ: сумма чисел 6-й строки равна $64$.

Пример 5. Свойство симметрии

Найдите $C_7^5$, зная, что $C_7^2 = 21$.

Дано: $n = 7$, $k = 5$, известно $C_7^2 = 21$.

Формула: $C_n^k = C_n^{n-k}$

Подстановка: $C_7^5 = C_7^{7-5} = C_7^2 = 21$

Ответ: $C_7^5 = 21$.

Важно!

⚠️ Типичная ошибка — путать размещения и сочетания. Если порядок важен (медали, должности, цифры в коде) — это размещения $A_n^k$. Если порядок не важен (команда, комитет, набор продуктов) — это сочетания $C_n^k$.

⚠️ Вторая частая ошибка — забывать, что $0! = 1$. Это нужно для корректной работы формул: $A_n^n = n!$ и $C_n^0 = 1$.