
Навигация по странице
О задании
Задание 8 ЕГЭ по информатике направлено на проверку понимания методов измерения количества информации. Эта задача обычно имеет комбинаторную природу, где требуется определить количество кодовых слов или других элементов, которые соответствуют заданным условиям.
Чтобы успешно решать задачи на подсчет количества кодовых слов, нужно не просто знать математические формулы – важно понимать базовые принципы комбинаторики и уметь применять их в различных ситуациях.
В этой статье мы разберем основные комбинаторные принципы, которые помогут не только успешно справиться с заданием 8 на ЕГЭ, но и глубже понять, как устроены системы кодирования информации в целом.
Мы рассмотрим ключевые понятия, формулы и методы, а также разберём примеры задач, чтобы вы могли успешно применять полученные знания на практике.
Что такое комбинаторика?
Комбинаторика — это область математики, которая занимается изучением способов организации и подсчета различных комбинаций из дискретных объектов. Представьте себе комбинаторику как искусство упорядочивать и анализировать множества, где каждый элемент может быть использован для создания новых, порой неожиданных вариантов.
В своей сущности комбинаторика не задумывается о природе объектов – фрукты, игральные карты или монеты. Принципиальными являются только два условия: объекты должны быть перечисляемыми (или же дискретными) и уникальными, то есть в одном множестве не должно быть двух идентичных элементов.
Не стоит относиться к комбинаторике как к строго теоретической науке, которая нужно только для абстрактных математических моделей.
Применение комбинаторики в реальной жизни настолько широко, что порой мы даже не замечаем её повсеместного присутствия. В программировании она используется для создания алгоритмов и шифров, в логистике — для оптимизации маршрутов и распределения ресурсов, в теории вероятностей — для расчёта шансов событий, в генетике — для анализа комбинаций генов, в экономике — для оценки рисков и анализа рынка, а также в повседневных задачах, таких как планирование расписания, организация мероприятий или решение головоломок. Она помогает системно подходить к задачам, требующим подсчёта вариантов и принятия оптимальных решений.
Давайте рассмотрим несколько конкретных примеров, чтобы понять масштаб применения комбинаторики.
Представьте, что вы маркетолог кондитерской фабрики. Ваша задача – создать уникальные подарочные наборы, которые будут привлекать покупателей своим разнообразием. В вашем арсенале 5 видов шоколада (горький, молочный, белый, с орехами, с карамелью) и 3 вида орехов (миндаль, фундук, макадамия).
Используя комбинаторику, можно просчитать, сколько различных наборов получится изготовить из имеющихся товаров. Так, выбирая по одному виду шоколада и одному виду орехов к нему, можно создать15 уникальных вариантов шоколадно-ореховых композиций. Каждый набор будет отличаться, что позволит вам удивлять клиентов и расширять ассортимент.
Или же рассмотрим более научный пример. В генетике комбинаторика позволяет предугадывать генетические сценарии с математической точностью.
Когда родители имеют различные генетические варианты, мы можем просчитать вероятность передачи того или иного признака ребёнку.
Например, рассмотрим наследование цвета глаз. Если ген карих глаз (A) доминантный, а голубых (a) — рецессивный, то у родителей с генотипом Aa возможны четыре комбинации генов у ребёнка: AA, Aa, Aa и aa. Вероятность каждой комбинации составляет 25%.
Поскольку AA и Aa приводят к карим глазам, а aa — к голубым, шанс рождения ребёнка с карими глазами — 75%, а с голубыми — 25%.
Основные понятия
Давайте для начала разберём несколько базовых понятий комбинаторики.
Мы уже затрагивали такое понятие как множество уникальных объектов. Множество — это группа четко определенных, различимых объектов, которые можно перечислить и которые не имеют между собой повторений. Объекты в множестве понимаются как единое целое на основе тех или иных признаков.
Примером может служить множество фруктов: яблоки, бананы, вишня, виноград. Также это могут быть цифры или буквы латинского алфавита, например.
Следующим важным термином является выбор. Выбор в комбинаторике — это процесс извлечения определенных элементов из множества. Представьте, что у вас есть большой ящик с разноцветными шарами, и вам нужно выбрать несколько из них.
Классический пример выбора — это создание пароля. Допустим, у вас есть набор символов: p, C, 5, A, x, a, 0, w. Выбор означает, что вы можете произвольно отобрать некоторые из этих символов.
Например:
- Выбор 3 символов: p, A, 0
- Выбор 5 символов: C, 5, x, A, w
Важно понимать: при выборе порядок не важен. Выбор p, A, 0 – это то же самое, что A, 0, p.
Третьим основным понятием у нас будет расположение. Расположение – это упорядочивание выбранных элементов. Здесь каждая позиция имеет значение, и разные порядки считаются разными вариантами.
Используя те же символы из предыдущего примера, мы можем создать различные расположения:
- Cxi0aA5w
- axw0C5pA
- 5Apa0Cwx
Заметьте разницу с выбором: теперь каждая последовательность уникальна и имеет свой смысл.
А с термином «факториал» уже все должны быть знакомы, так что вкратце и без примеров напомним его определение. Факториал числа n — это математическая операция, которая определяется как произведение всех натуральных чисел от 1 до n включительно.
Также нам часто будут помогать следующие два правила: правило суммы и правило произведения.
Правило суммы гласит: если у нас есть несколько независимых способов выполнить действие, то общее количество способов равно сумме способов для каждого варианта. Иначе говоря, если объект А можно выбрать m способами, а объект B — n способами, то выбрать A или B можно m+n способами.
Это правило применяется, когда необходимо подсчитать количество вариантов, если выборы взаимоисключающие.
Например, в магазине есть 3 вида яблок и 5 видов груш. Сколько существует способов купить один фрукт (либо яблоко, либо грушу)?
- Выбор яблока: 3 способа.
- Выбор груши: 5 способов.
- Общее количество способов: 3+5=8.
Правило произведения применяется, когда нужно выполнить несколько последовательных действий, и количество способов выполнения каждого действия не зависит от других.
Таким образом, если объект А можно выбрать m способами, а объект B — n способами, то выбрать A и B можно m*n способами. То есть в данной ситуации мы имеем независимые друг от друга выборы.
Давайте рассмотрим такой пример: ресторан предлагает на выбор одно основное блюдо и напиток к нему. Всего в наличии 4 вида основных блюд и 5 напитков. Следовательно, у нас существует 4 * 5 = 20 способов выбрать себе обед из основного блюда и напитка к нему.
Эти правила по началу могут показаться сложными, но можно запомнить такое правило:
«Сумму используем, если выбираем что-то одно: или A, или B. Произведение следует использовать, если необходимо выполнить все действия: и A, и B»
Теперь же мы смело можем перейти к комбинаторным операциям.
Перестановка
Перестановка – это способ упорядочивания всех элементов некоторого множества, где каждый элемент используется ровно один раз, и важен порядок расположения.
Представим, что у нас есть множество из трёх фруктов: яблоко, банан и вишня.

Сколькими способами можно переставить все эти фрукты в корзине? Давайте перечислим все возможные варианты:
- Яблоко, Банан, Вишня
- Яблоко, Вишня, Банан
- Банан, Яблоко, Вишня
- Банан, Вишня, Яблоко
- Вишня, Банан, Яблоко
- Вишня, Яблоко, Банан

Количество перестановок для n различных элементов вычисляется по формуле:
Для наших трех фруктов: 3! = 3 · 2 · 1 = 6 перестановок.
В случае, когда среди выбираемых элементов некоторые могут встречаться несколько раз, все комбинации перестановок таких элементов называются перестановки с повторением.
Если вернуться к примеру с фруктами, то задачу нахождения перестановок с повторением можно сформулировать так: пусть у нас есть 10 фруктов, среди которых: 5 яблок, 2 банана, 2 вишни, 1 груша. Сколькими способами их можно положить в корзину в определённом порядке?
Здесь будем переставлять n=10 объектов всеми возможными способами. Как мы уже знаем, их будет n!, или же здесь — 10!. Но из-за того, что некоторые объекты представлены в нескольких экземплярах, то итоговое число перестановок будет меньше.
В частности, 5 яблок, можно переставлять между собой 5! способами, при этом они не будут менять итоговую перестановку всех фруктов в корзине.
Давайте попробуем вывести формулу для вычисления количества перестановок с повторением на основе уже имеющихся знаний.
Если бы все элементы были уникальными, то количество перестановок было бы равно n!, это мы уже определили ранее для перестановок без повторения. Теперь же, если некоторые элементы повторяются, то перестановки, которые отличаются только порядком этих повторяющихся элементов, считаются одинаковыми.
Чтобы исключить такие «лишние» перестановки, мы делим общее количество перестановок на произведение факториалов количества повторений каждого элемента.
В итоге получаем такую формулу:
Тогда, в приведенной выше задаче, количество перестановок с повторением будет вычисляться так:
Размещения
Размещение — способ выбора определённого количества элементов из множества и расположения их в определённом порядке.
Представим, что на столе лежат все те же фрукты: яблока, банан и вишня. Нам можно взять только 2 из них, причём в определённом порядке: сначала один фрукт, потом второй.
Давайте перечислим все возможные варианты:
- Яблоко, Банан
- Банан, Вишня
- Яблоко, Вишня
- Вишня, Яблоко
- Банан, Яблоко
- Вишня, Банан

Количество размещений из n элементов по m вычисляется по этой формуле:
В нашем примере количество элементов (n) равно 3. Выбирать будем по 2 элемента в последовательность (m). Следовательно, подставим эти значения в формулу выше и получим количество размещений из 3 элементов по 2:
Когда один и тот же элемент в комбинации может повторяться несколько раз, такое размещение называется размещением с повторением.
Возвращаясь к прошлому примеру, к уже известным комбинациям добавятся еще 3 комбинации с повторением: по 2 яблока, 2 банана и 2 вишни.

Формула для вычисления количества размещений с повторением следующая:
В нашем случае, для вычисления количества размещений из 3 элементов по 2 с повторением достаточно возвести число 3 во вторую степень, получив тем самым 9 возможных вариантов.
Сочетания
Сочетание — это способ выбрать определённое количество элементов из заданного множества без учёта порядка. В отличие от размещений, где порядок элементов важен, в сочетаниях имеет значение только состав выбранной группы
Давайте к уже полюбившимся нам трём фруктам добавим еще один — виноград. Теперь нам надо ответить на вопрос «Сколькими способами можно выбрать 2 фрукта из корзины с четырьмя фруктами, причем порядок выбора не имеет значения?»
В таком случае у нас существует только 6 пар фруктов:
- Банан с виноградом (или виноград с бананом)
- Банан с вишней (или вишня с бананом)
- Банан с яблоком (или яблоко с бананом)
- Вишня с виноградом (или виноград с вишней)
- Виноград с яблоком (или яблоко с виноградом)
- Вишня с яблоком (или яблоко с вишней)

Формула для вычисления количества сочетаний из n элементов по m представлена ниже:
В нашем случае количество сочетаний из 4 элементов по 2 будет следующим:
Если в сочетании элементы могут повторяться, то тогда такие комбинации называются сочетаниями с повторением.
Например, сформулируем задачу таким образом: «В магазине есть 4 вида фруктов — яблоки, бананы, вишни и виноград. Сколькими способами можно купить 2 фрукта (фрукты могут повторяться)?»
Логично предположить, что к уже рассмотренному сочетанию фруктов из 6 комбинаций добавятся еще 4, где фрукты будут повторяться: яблоко + яблоко, банан + банан, вишня + вишня и виноград + виноград.

Формула для вычисления количества сочетаний с повторением из n элементов по m:
Подставим в эту формулу наши значения: n = 4 и m = 2.
Давайте сделаем краткий вывод по всем комбинаторным конфигурациям.
Выбор нужной операции зависит от двух главных факторов:
Важен ли порядок элементов и допускаются ли повторения?
- Если порядок важен → используем перестановки или размещения:
- Если вам нужно упорядочить все элементы → перестановки.
- Если нужно выбрать часть элементов с учётом порядка → размещения.
- Если порядок не важен → выбираем сочетания.
- Если элементы могут повторяться → применяем их варианты с повторениями.