№8 Комбинаторика

Задания: N8.Комбинаторика

1. Основные формулы комбинаторики

1.1. Факториал

Определение: Факториал натурального числа $n$ это это произведение всех натуральных чисел от 1 до $n$ .

Формула: $n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$

Особые случаи: $0! = 1$ (по определению) $1! = 1$

Примеры: $3! = 3 \cdot 2 \cdot 1 = 6$ $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

1.2. Перестановки $P_n$

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

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

Условия:

Все элементы различны
Используются все элементы
Порядок важен

Пример: Сколько способов расставить 3 книги на полке? $P_3 = 3! = 1 \cdot 2 \cdot 3 = 6$

1.3. Размещения $A_n^k$

Что считаем: Количество способов выбрать и упорядочить $k$ элементов из $n$ различных элементов (порядок важен).

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

Условия:

Элементы различны
Выбираем $k$ из $n$ элементов
Порядок важен
Элементы не повторяются

Пример: Сколькими способами можно выбрать 2 медали (золотую и серебряную) из 5 участников? $A_5^2 = \frac{5!}{(5-2)!} = \frac{5!}{3!} = \frac{120}{6} = 20$

1.4. Сочетания $C_n^k$

Что считаем: Количество способов выбрать $k$ элементов из $n$ различных элементов без учёта порядка (порядок не важен).

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

Условия:

Элементы различны
Выбираем $k$ из $n$ элементов
Порядок не важен
Элементы не повторяются

Пример: Сколько можно выбрать 2 человек из 5 для участия в проекте? $C_5^2 = \frac{5!}{2!(5-2)!} = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = 10$

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

(C_n^k = C_n^{n-k}) (симметрия); (C_n^0 = C_n^n = 1); (C_n^1 = n).

2. Основные правила

2.1. Правило суммы

Формулировка: Если событие A можно выбрать $n$ способами, а событие B это $m$ способами, причём события A и B не пересекаются, то событие "A или B" можно выбрать $n + m$ способами.

Условие: События должны быть несовместными (не могут произойти одновременно).

Пример: В магазине есть 5 видов яблок и 3 вида груш. Сколькими способами можно выбрать один фрукт? $5 + 3 = 8 \text{ способов}$

2.2. Правило произведения

Формулировка: Если событие A можно выбрать $n$ способами, а после этого событие B это $m$ способами, то пару "A и B" можно выбрать $n \cdot m$ способами.

Условие: События должны быть независимыми (выбор одного не влияет на выбор другого).

Пример: Сколько различных двузначных чисел можно составить из цифр 1, 2, 3, если цифры могут повторяться?

Первая цифра: 3 способа
Вторая цифра: 3 способа

$3 \cdot 3 = 9 \text{ чисел}$

3. Типичные задачи ЕГЭ по информатике (Задание 8)

3.1. Составление слов с ограничениями

Тип задачи: Сколько слов заданной длины можно составить из заданных букв при определённых ограничениях?

Алгоритм решения:

Определить количество позиций в слове
Для каждой позиции определить количество возможных вариантов
Применить правило произведения

Пример: Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз.

Решение:

Согласные: З, М (2 варианта)
Гласные: И, А (2 варианта)
Все буквы: З, И, М, А (4 варианта)

Позиции:

Позиция 1 (начало): согласная → 2 варианта
Позиции 2-4 (середина): любая буква → 4 варианта каждая
Позиция 5 (конец): гласная → 2 варианта

$2 \times 4 \times 4 \times 4 \times 2 = 256 \text{ слов}$

3.2. Коды и шифры с ограничениями

Тип задачи: Сколько различных кодов/шифров можно составить при заданных ограничениях?

Пример: Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 4. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно два раза?

Решение:

Выбираем 2 позиции из 5 для цифры 1: $C_5^2 = 10$ способов
На оставшихся 3 позициях размещаем цифры 2, 3, 4 (каждая может быть любой из трёх): $3^3 = 27$ способов

$C_5^2 \times 3^3 = 10 \times 27 = 270 \text{ вариантов}$

3.3. Слова с ограничениями на позиции

Тип задачи: Составление слов, где некоторые позиции имеют ограничения.

Пример: Ольга составляет таблицу кодовых слов для передачи сообщений. В качестве кодовых слов Ольга использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, Y. При этом первая буква кодового слова это это буква X или Y, а далее в кодовом слове буквы X и Y не встречаются.

Решение:

Позиция 1: X или Y → 2 варианта
Позиции 2-4: A, B, C, D → 4 варианта каждая

$2 \times 4 \times 4 \times 4 = 128 \text{ слов}$

3.4. Перестановки с ограничениями

Тип задачи: Сколько перестановок элементов, удовлетворяющих определённым условиям?

Пример: Левий составляет 5-буквенные коды из букв Л, Е, В, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕИ.

Решение:

Всего перестановок 5 букв: $5! = 120$
Исключаем перестановки, начинающиеся с Й: $4! = 24$
Исключаем перестановки с сочетанием ЕИ (сложнее, нужно использовать принцип включений-исключений)

Упрощённый подход:

Первая буква: Л, Е, В, И (4 варианта, не Й)
Остальные 4 буквы переставляем: $4! = 24$
Но нужно учесть ограничение на ЕИ

Более точное решение требует учёта всех ограничений одновременно.

3.5. Нумерация слов в алфавитном порядке

Тип задачи: Все слова заданной длины из заданных букв записаны в алфавитном порядке. Найти слово под заданным номером или номер заданного слова.

Алгоритм решения:

Определить алфавитный порядок букв
Использовать позиционную систему счисления (основание = количество букв)
Перевести номер в систему счисления с заданным основанием
Заменить цифры на соответствующие буквы

Пример: Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Запишите слово, которое стоит под номером 67.

Решение:

Алфавит: К, Л, Р, Т (4 буквы)
Основание системы счисления: 4
Переводим 67 в четверичную систему:
- $67 : 4 = 16$ (остаток 3) → последняя буква: Т (индекс 3)
- $16 : 4 = 4$ (остаток 0) → предпоследняя: К (индекс 0)
- $4 : 4 = 1$ (остаток 0) → вторая: К (индекс 0)
- $1 : 4 = 0$ (остаток 1) → первая: Л (индекс 1)
Ответ: ЛККТ

Важно: Нумерация обычно начинается с 1, поэтому нужно вычесть 1 перед переводом в систему счисления.

4. Алгоритм решения комбинаторных задач

Шаг 1: Анализ условия

Определить тип задачи (перестановки, размещения, сочетания, правило произведения/суммы)
Выявить все ограничения
Определить, важен ли порядок элементов

Шаг 2: Выбор метода

Правило произведения если нужно выбрать несколько элементов последовательно
Правило суммы если нужно выбрать один из нескольких вариантов
Формулы комбинаторики если задача подходит под стандартную схему

Шаг 3: Решение

Применить выбранную формулу или правило
Учесть все ограничения
Проверить, не учтены ли элементы дважды (при использовании правила суммы)

Шаг 4: Проверка

Проверить логику решения
Убедиться, что учтены все ограничения
Для сложных задач можно проверить на малых примерах

5. Типичные ошибки и как их избежать

Ошибка 1: Путаница между размещениями и сочетаниями

Проблема: Не учитывается, важен ли порядок элементов.

Как избежать:

Если порядок важен → размещения $A_n^k$
Если порядок не важен → сочетания $C_n^k$

Пример:

"Сколько способов выбрать председателя и секретаря из 5 человек?" → порядок важен → $A_5^2$
"Сколько способов выбрать 2 человек из 5?" → порядок не важен → $C_5^2$

Ошибка 2: Неправильное применение правила суммы

Проблема: Применяют правило суммы для совместных событий.

Как избежать: Убедиться, что события не могут произойти одновременно. Если могут это использовать формулу включений-исключений.

Ошибка 3: Забывают об ограничениях

Проблема: Не учитывают ограничения на позиции или элементы.

Как избежать: Внимательно читать условие, выписывать все ограничения отдельно.

Пример: В задаче про слова, начинающиеся с согласной, часто забывают это ограничение и считают все слова.

Ошибка 4: Неправильный перевод в систему счисления

Проблема: При нумерации слов забывают, что нумерация начинается с 1, а не с 0.

Как избежать: Вычитать 1 из номера перед переводом в систему счисления.

Ошибка 5: Путаница с повторениями

Проблема: Не учитывают, могут ли элементы повторяться.

Как избежать:

Если элементы могут повторяться → использовать правило произведения
Если элементы не могут повторяться → использовать формулы размещений/сочетаний

6. Решение задач на Python (для проверки)

Пример 1: Слова с ограничениями

from itertools import product

# Задача: Сколько слов длины 5, начинающихся с согласной 
# и заканчивающихся гласной, из букв З, И, М, А?

согласные = {'З', 'М'}
гласные = {'И', 'А'}
все_буквы = ['З', 'И', 'М', 'А']

count = 0
for word_tuple in product(все_буквы, repeat=5):
    word = ''.join(word_tuple)
    if word[0] in согласные and word[-1] in гласные:
        count += 1

print(f"Ответ: {count}")

# Аналитическое решение:
# 2 (согласные) × 4³ (середина) × 2 (гласные) = 256
analytical = 2 * (4 ** 3) * 2
print(f"Проверка: {analytical}")

Пример 2: Нумерация слов

# Задача: Найти слово под номером 67 из 4-буквенных слов
# из букв К, Л, Р, Т (в алфавитном порядке)

алфавит = ['К', 'Л', 'Р', 'Т']
номер = 67 - 1  # Вычитаем 1, т.к. нумерация с 1

# Переводим в систему счисления с основанием 4
result = []
n = номер
while n > 0:
    result.append(n % 4)
    n //= 4

# Дополняем нулями слева до 4 позиций
while len(result) < 4:
    result.append(0)

# Переворачиваем и заменяем цифры на буквы
word = ''.join(алфавит[i] for i in reversed(result))
print(f"Слово под номером 67: {word}")

7. Практические рекомендации

Для быстрого решения:

Запомните основные формулы: $P_n = n!$

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

Используйте правило произведения для задач с последовательным выбором
Используйте правило суммы для задач с выбором одного из вариантов
Для проверки можно написать простую программу на Python с перебором

Для сложных задач:

Разбивайте задачу на подзадачи
Используйте дерево решений для визуализации
Проверяйте на малых примерах
Учитывайте все ограничения по отдельности

8. Типичные формулировки в ЕГЭ

Формулировка	Что это означает	Метод решения
"Сколько способов упорядочить..."	Все элементы используются, порядок важен	Перестановки $P_n = n!$
"Сколько способов выбрать и расставить..."	Выбираем часть элементов, порядок важен	Размещения $A_n^k$
"Сколько способов выбрать..."	Выбираем часть элементов, порядок не важен	Сочетания $C_n^k$
"Сколько слов/кодов можно составить..."	Обычно правило произведения	$n_1 \times n_2 \times \dots \times n_k$
"Сколько вариантов, если... встречается ровно $k$ раз"	Комбинация сочетаний и правила произведения	$C_n^k \times (\text{остальные варианты})$

Составлено: Лилия С.
Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике, яндекс учебник

Удачи на экзамене! 🎓

1. Основные формулы комбинаторики

1.1. Факториал

1.2. Перестановки PnP_nPn​

1.3. Размещения AnkA_n^kAnk​

1.4. Сочетания CnkC_n^kCnk​

2. Основные правила

2.1. Правило суммы

2.2. Правило произведения

3. Типичные задачи ЕГЭ по информатике (Задание 8)

3.1. Составление слов с ограничениями

3.2. Коды и шифры с ограничениями

3.3. Слова с ограничениями на позиции

3.4. Перестановки с ограничениями

3.5. Нумерация слов в алфавитном порядке

4. Алгоритм решения комбинаторных задач

Шаг 1: Анализ условия

Шаг 2: Выбор метода

Шаг 3: Решение

Шаг 4: Проверка

5. Типичные ошибки и как их избежать

Ошибка 1: Путаница между размещениями и сочетаниями

Ошибка 2: Неправильное применение правила суммы

Ошибка 3: Забывают об ограничениях

Ошибка 4: Неправильный перевод в систему счисления

Ошибка 5: Путаница с повторениями

6. Решение задач на Python (для проверки)

Пример 1: Слова с ограничениями

Пример 2: Нумерация слов

7. Практические рекомендации

Для быстрого решения:

Для сложных задач:

8. Типичные формулировки в ЕГЭ

1.2. Перестановки $P_n$

1.3. Размещения $A_n^k$

1.4. Сочетания $C_n^k$