Что такое комбинаторика и где она встречается
Комбинаторика отвечает на вопрос «сколько существует вариантов». Сколько четырёхбуквенных слов можно составить из букв М, А, Р, Т. Сколько шестизначных чисел бывает в двенадцатеричной системе. Сколькими способами из 5 человек выбрать двоих дежурных.
С этим сталкиваются с 2 по 11 класс. В младших классах это перебор вариантов: наряды из трёх вещей, комбинации свечей на торте. В 9 классе добавляются формулы, а в 10–11 классах комбинаторика нужна в информатике и в теории вероятностей. Там вероятность считают как отношение числа подходящих исходов к числу всех равновозможных, а оба числа находят комбинаторикой.
В информатике чаще всего попадаются слова из заданного алфавита, числа в разных системах счисления и номера слов в алфавитном списке.
Правила и формулы комбинаторики
Почти все задачи решаются двумя правилами.
- Правило умножения. Если первый выбор можно сделать a способами, а второй b способами, то вместе они дают a × b вариантов. Трёхбуквенное слово из 4 букв: 4 × 4 × 4 = 4³ = 64.
- Правило сложения. Если случаи не пересекаются, их количества складывают. Слова, которые начинаются на А, и слова, которые начинаются на Б, считают отдельно и суммируют.
Из этих правил получаются основные формулы:
- Размещения с повторениями. Слов длины k из n букв, когда буквы можно повторять: nᵏ.
- Перестановки. Способов расставить n разных предметов в ряд: n! = 1 × 2 × 3 × … × n. Считается, что 0! = 1.
- Размещения без повторений. Способов выбрать k из n разных предметов, если порядок важен: n! ÷ (n − k)!.
- Сочетания. Способов выбрать k из n предметов, если порядок не важен: n! ÷ (k! × (n − k)!). Например, двоих из пяти: 5! ÷ (2! × 3!) = 10.
Главный вопрос перед выбором формулы: важен ли порядок. Пара «Аня, Боря» и пара «Боря, Аня» в сочетаниях считается одной, а в размещениях двумя разными.
Разбор задания: слова, в которых буква встречается хотя бы раз
Похожие задания присылают часто, поэтому разберём такое.
Условие. Составляют четырёхбуквенные слова из букв А, Б, В, Г, Д. Буква Б должна встретиться хотя бы один раз. Остальные буквы можно повторять. Сколько существует таких слов?
Шаг 1. Считаем все слова без ограничений. На каждое из 4 мест подходит любая из 5 букв: 5 × 5 × 5 × 5 = 5⁴ = 625.
Шаг 2. Считаем слова, которые нам не подходят. Это слова вообще без буквы Б. На каждое место остаётся 4 буквы: 4⁴ = 256.
Шаг 3. Вычитаем. 625 − 256 = 369.
Ответ: 369 слов.
Можно было считать напрямую: слова с одной Б, с двумя, с тремя, с четырьмя. Это длиннее, и легко потерять случай. Если в условии «хотя бы один», проще вычесть слова без этой буквы из всех.
Если условие обратное, например «буква А не более 3 раз» при длине слова 4, не подходят только слова, где А стоит на всех четырёх местах. Их ровно одно, и его вычитают из всех.
Как решать задачи про алфавитный список слов
В таких заданиях все слова из нескольких букв выписаны по алфавиту, и нужно найти слово по номеру, номер по слову или количество слов между двумя данными.
Работа с таким списком похожа на счёт в системе счисления. Если в алфавите 3 буквы, то каждой букве соответствует цифра 0, 1, 2 по порядку. Тогда слово становится числом в троичной системе, а его номер в списке равен этому числу плюс 1, потому что первое слово ААА… соответствует нулю.
Пример. Слова из букв А, Б, В длиной 3. Найдём номер слова ВАБ. Заменяем буквы на цифры: В = 2, А = 0, Б = 1, получаем 201 в троичной системе. Переводим: 2 × 9 + 0 × 3 + 1 = 19. Номер слова 19 + 1 = 20. Проверка: слов на А девять, на Б девять, это 18 слов. Следом идут ВАА (19-е) и ВАБ (20-е).
Обратная задача решается переводом номера минус 1 в систему с основанием, равным числу букв, и заменой цифр на буквы. Не забудь дописать нули слева до нужной длины слова.
Когда нужно посчитать слова между двумя данными, найди номера обоих слов и вычти. Если границы не включаются, из разности вычти ещё 1. Если включаются, прибавь 1.
Где ошибаются чаще всего
- Путают размещения и сочетания. Если порядок важен (слова, пароли, места на пьедестале), нужны размещения. Если не важен (команда, набор карточек), нужны сочетания. Проверь на двух элементах: меняется ли результат, когда их поменяли местами.
- Считают «хотя бы один» напрямую. Это приводит к длинной сумме и пропущенным случаям. Надёжнее вычесть из всех вариантов те, где условие не выполнено.
- Забывают про ведущий ноль в числах. В шестизначном двенадцатеричном или шестнадцатеричном числе первая цифра не может быть нулём. Поэтому для первой позиции вариантов на один меньше, чем для остальных. Если ещё нужно ограничить количество определённой цифры, например В или А, считай отдельно случаи, когда она стоит на первом месте и когда на другом.
- Сбиваются на единицу в номерах. Номер слова равен его значению в системе счисления плюс 1. Слов между двумя номерами без границ на 1 меньше разности номеров, а с границами на 1 больше.
Какие задания по комбинаторике есть на странице
Ученики присылают в основном задания по информатике: слова из заданных букв с ограничениями на число повторов, позиции слов в алфавитном списке, количество слов между двумя данными, подсчёт чисел в двенадцатеричной и шестнадцатеричной системах с ограничением на число некоторых цифр, а также задачу про стоимость свечей-цифр.
Найди в списке выше задание, похожее на твоё, и сверь ход решения. Если подходящего нет, сфотографируй своё условие и отправь на сайт: решение придёт с ходом по шагам. Сравни свои рассуждения с разбором и найди, на каком шаге разошлись. Алфавит и длину слова удобно связать с кодированием информации, а подсчёт путей и вариантов на схеме бывает проще через графы.