Введение
Комбинаторика подразделяется на три основных вида: размещения, перестановки и сочетания. В этой статье мы разберём первые два из них, которые встречаются в задании №8 ЕГЭ по информатике.
Термины, которые будем использовать:
Комбинаторика, размещения, перестановки, факториал.
Размещения
Этот тип комбинаторики подразумевает многократное использование любого символа из данного алфавита для составления различных комбинаций. Например, тебе дан алфавит, состоящий из букв Ш, К, О, Л, А, нужно составить четырёхбуквенные слова.
«Каждая из допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная»,
— такая формулировка часто встречается в задании №8. Она позволяет тебе использовать указанные буквы неоднократное количество раз и составлять любые комбинации.
Вернёмся к нашему примеру. Во всех комбинациях будет по 4 буквы, на каждом месте в слове может стоять любая из пяти букв: Ш, К, О, Л, А. Тогда для каждой позиции в слове у нас есть пять вариантов: 5*5*5*5 = 625 комбинаций. Почему именно умножение?
Правило произведения гласит:
если первое действие можно выполнить n способами, а второе — m способами, то оба действия можно выполнить n * m способами.
Представь, что ты выбираешь любые два предмета: рубашку и брюки.
У тебя есть 3 рубашки и 2 пары брюк. Чтобы посчитать, сколько всего комбинаций рубашек и брюк можно составить, ты умножаешь количество вариантов: 3 * 2 = 6 возможных комбинаций.
Потренируйся:
- Сколько разных нарядов ты можешь составить, если у тебя есть 3 футболки и 4 пары джинсов?
- Сколькими способами можно составить 3-значный код на чемодане, если используются десятичные цифры (от 0 до 9)?
- 3 * 4 = 12
- 10 * 10 * 10 = 1000
Обрати внимание
В отличие от последнего примера, где цифра 0 может располагаться на первом месте, в заданиях ЕГЭ на составление чисел очень важно помнить про незначащие нули. Если тебя попросили составить пятизначное число, то оно не может начинаться с 0, иначе оно будет уже четырёхзначным. Поэтому в задании №8 число никогда не начинается с 0.
Примеры заданий
Попрактикуемся на реальных заданиях ЕГЭ.
Задание 1
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая из допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
У нас даны 2 гласные буквы (А, У) и 2 согласные буквы (К, М).
Тогда на первом месте могут стоять только 2 буквы: или К, или М. На последнем месте — только А или У, а на остальных местах — любая:
2 4 4 4 2 => 2*4*4*4*2 = 256 вариантов возможно.
Ответ: 256
Задание 2
Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?
При решении руками переберём 2 случая:
Буква Х не появится вовсе: 3 3 3 3 3 => 3**5 = 243
Буква Х появится 1 раз на последнем месте: 3 3 3 3 1 => 3**4 = 81
Итого вариантов будет 243+81 = 324.
Ответ: 324
Задание 3
Определите количество шестизначных чисел, записанных в десятичной системе счисления, которые начинаются с чётной цифры и заканчиваются на нечётную цифру.
Всего у нас 5 чётных и 5 нечётных цифр, но так как 0 не может стоять на первом месте, то количество вариантов сокращается до 4.
Со второго по предпоследнее место можно располагать все возможные цифры. Получается 4 10 10 10 10 5 => 4*10*10*10*10*5 = 200000 комбинаций.
Ответ: 200 000
Перестановки
Этот тип подразумевает
однократное использование символов алфавита, то есть каждую букву или цифру можно использовать ровно один раз при составлении комбинации,
что и отличает перестановки от размещения.
Например, у Инны есть четыре буквы-магнита: Ф, Л, Э, Ш, из которых она любит составлять слова на холодильнике. На первое место она может поставить любую из четырёх букв, ведь они все у неё на руках. Инна выбрала букву Ф и прикрепила её к холодильнику. На второе место она может выбирать только из оставшихся трёх букв. С каждым разом количество её вариантов будет сокращаться на единицу. Инна сможет составить 4*3*2*1 = 24 варианта.
Лайфхак
Если количество символов алфавита n совпадает с длиной составляемой комбинации, то количество комбинаций будет равно n!
Факториал числа n (обозначение n!) — произведение чисел от n до 1. Например, 6! = 6*5*4*3*2*1.
Попрактикуйся:
- Сколькими способами можно расставить пять разных книг на полке?
- Сколькими способами можно составить шестибуквенные слова из букв русского алфавита на холодильнике у Инны?
- 5*4*3*2*1 = 120
- 33*32*31*30*29*28 = 797448960
Примеры заданий
Вернёмся к реальным задачам из ЕГЭ.
Задание 1
Сколько существует различных символьных последовательностей длины 5 в шестибуквенном алфавите М, А, Р, T, И, К, в которых все буквы различны?
Поскольку ограничений нет, начинаем с 6 вариантов: 6 5 4 3 2 <= 6*5*4*3*2 = 720.
Ответ: 720
Задание 2
Сколько существует шестизначных десятичных чисел, в которых каждая цифра может встречаться только один раз, при этом число не может начинаться с нечётной цифры и должно оканчиваться на цифру 5.
На первое место можно поставить одну из 4 цифр (2, 4, 6, 8), на второе место можно поставить все, кроме 5 и первой цифры, то есть 8 вариантов. Далее количество вариантов уменьшается на единицу, а на последнем месте может стоять только одна цифра. Получаем 4 8 7 6 5 1 => 4*8*7*6*5*1 = 6720.
Ответ: 6720
Заключение
У тебя получилось освоить два главных вида комбинаторики. И теперь ты сможешь с лёгкостью выполнить некоторые типы задания №8 ЕГЭ по информатике!
Автор:
Быкова Оксана, методист «100балльного репетитора» по информатике ЕГЭ
Подготовься к ЕГЭ на все 100
Скоро новый сезон! Ты с нами? Всем ученикам 100Б
даём самую низкую
цену на годовой курс 2025–2026.
Предложение ограничено.
Начать подготовку
