Введение

Комбинаторика - это раздел математики, который изучает, сколькими способами можно выбрать и (или) упорядочить элементы из некоторого множества. Она нужна не только в олимпиадных задачах, но и в программировании, криптографии, анализе данных и даже в повседневной жизни (например, при выборе пароля или составлении расписания).

Основные виды комбинаторных задач связаны с тремя понятиями:

• Перестановки - когда берём все элементы и меняем их порядок.
• Размещения - когда выбираем часть элементов и учитываем их порядок.
• Сочетания - когда выбираем часть элементов, но порядок не важен.

Правила комбинаторики

Правило сложения

Если объект \( A \) можно выбрать \( n \) способами, а объект \( B \) - \( m \) способами, и нельзя выбрать оба сразу, то «\( A \) или \( B \)» можно выбрать \( n + m \) способами.

Пример: В магазине есть 5 платных и 3 бесплатных приложения. Выберите одно - всего \( 5 + 3 = 8 \) вариантов.

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

Если объект \( A \) можно выбрать \( n \) способами, а после этого объект \( B \) - \( m \) способами, то пару \( (A, B) \) можно выбрать \( n \cdot m \) способами.

Пример: На обед - 3 супа и 4 горячих блюда. Всего \( 3 \cdot 4 = 12 \) разных обедов.

Факториал

Факториал числа \( n \) (обозначается \( n! \)) - это произведение всех натуральных чисел от \( 1 \) до \( n \):

\[ n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n,\quad\text{при этом }0! = 1. \]

Перестановки

Без повторений

Перестановка - это способ упорядочить все \( n \) различных элементов.

\[ P_n = n! \]

Пример: Сколько способов расставить 4 книги на полке? Ответ: \( 4! = 24 \).

С повторениями

Если среди \( n \) элементов есть повторяющиеся, например, \( n_1 \) одинаковых первого вида, \( n_2 \) - второго и т.\,д., то:

\[ P_n(n_1, n_2, \dots) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots} \]

Пример: Сколько перестановок слова «МАМА»? Здесь \( n = 4 \), буква «М» встречается 2 раза, «А» - тоже 2 раза:

\[ \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6. \]

Размещения

Без повторений

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

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

Пример: Сколько трёхзначных чисел можно составить из цифр 1–5 без повторений? Это \( A_5^3 = \frac{5!}{2!} = 60 \).

С повторениями

Если элементы можно повторять, то:

\[ \overline{A}_n^k = n^k \]

Пример: Пароль из 4 цифр (от 0 до 9). Всего \( 10^4 = 10\,000 \) вариантов.

Сочетания

Без повторений

Сочетание из \( n \) по \( k \) - это неупорядоченный набор из \( k \) элементов, выбранных из \( n \). Порядок не важен!

\[ C_n^k = \binom{n}{k} = \frac{n!}{k!(n - k)!} \]

Пример: Из 10 учеников нужно выбрать 3 дежурных. Сколькими способами?

\[ \binom{10}{3} = \frac{10!}{3! \cdot 7!} = 120. \]

С повторениями

Если можно выбирать один и тот же элемент несколько раз (например, покупать 4 шоколадки из 6 видов, и можно брать одинаковые), то:

\[ \overline{C}_n^k = \binom{n + k - 1}{k} \]

Пример: Сколькими способами купить 4 шоколадки из 6 видов, если можно брать одинаковые?

\[ \binom{6 + 4 - 1}{4} = \binom{9}{4} = 126. \]

Свойства сочетаний

1. \( \displaystyle \binom{n}{k} = \binom{n}{n - k} \)

   Пояснение: Выбрать 3 человека из 10 - то же самое, что выбрать 7, которых не берём.

2. \( \displaystyle \binom{n}{k} + \binom{n}{k - 1} = \binom{n + 1}{k} \) (формула Паскаля)

   Пояснение: Лежит в основе треугольника Паскаля.

Как выбрать нужную формулу?

Ответьте на два вопроса:

1. Используем все элементы или только часть?
   • Все → перестановки.
   • Часть → переходим ко 2-му вопросу.
2. Важен ли порядок?
   • Да → размещения.
   • Нет → сочетания.

Также уточните: могут ли элементы повторяться? Если да - используйте формулы с чертой сверху (\( \overline{A}, \overline{C} \)).

Заключение

Комбинаторика - это не просто «считать варианты», а логически разбираться, что именно происходит в задаче: выбираем? Упорядочиваем? Повторяем? Ответы на эти вопросы подскажут, какую формулу применить. Главное - практика и внимание к деталям!