Комбинаторные задачи 1. Комбинаторные задачи: как считать варианты Учимся считать все возможные варианты без пропусков и повторов. Когда на столе два варианта — кажется, что всё просто. Но стоит добавить третий, четвёртый, пятнадцатый, как привычные перечисления ломаются. На помощь приходит комбинаторика — раздел математики, который учит находить количество вариантов без того, чтобы записывать каждый из них по очереди. 2. Где комбинаторика помогает каждый день Комбинаторные идеи встречаются в выборе одежды, меню, паролей и расписаний. Они показывают, как быстро растёт число вариантов и почему важно не забыть ни одного случая. Представим будничную ситуацию: утром нужно выбрать пару из нескольких вещей, затем — напиток из нескольких пунктов меню, а дальше — маршрут из вариантов, которые предлагает навигатор. Комбинаторика помогает понять: сколько разных комбинаций реально возможно, и какие из них стоит учитывать, чтобы ничего не потерять. 3. Что такое комбинаторная задача Комбинаторная задача требует определить количество всех возможных вариантов, а не просто найти один ответ. Обычно нужно выбрать предметы, расположить их или распределить по группам. Первый шаг — понять, что именно считается. Это может быть набор предметов, порядок размещения или распределение по группам. Один и тот же “выбор” в жизни часто кажется одинаковым, а в задаче может считаться по-разному. Скажем, нужно распределить людей по местам или по ролям: если меняется порядок — это уже другой вариант. Поэтому в комбинаторике всегда начинают с вопроса: что меняется, а что остаётся одинаковым? Так включается “логический фильтр”, который спасает от типичных ошибок. 4. Правило суммы и правило произведения Правило суммы применяют, когда нужно выбрать один вариант из нескольких несовместимых. Если есть разные напитки, их варианты просто складывают, потому что одновременно выбирают только один из них. Правило произведения используют при последовательном выборе. Если сначала выбирают одну вещь, а потом другую, общее число комплектов находят умножением, потому что каждый первый выбор сочетается с каждым вторым. На практике эти правила похожи на “развилки” и “цепочки”. Правило суммы — когда варианты не пересекаются: выбрал один путь — остальные уже невозможны. Правило произведения — когда сначала определили первый элемент, а затем каждый из получившихся вариантов дополняется следующей частью. Эти две идеи — как два универсальных переключателя в голове: они помогают быстро выбрать верное действие. 5. Как быстро растёт число вариантов Как быстро растёт число вариантов Даже небольшое добавление элементов может резко увеличить число решений в задаче. Когда выборов становится больше, число комбинаций начинает расти не “по чуть-чуть”, а иногда скачком — из-за умножения возможностей друг на друга. Если в начале кажется, что задача сводится к нескольким вариантам, то дальше вступает эффект “комбинационного взрыва”: каждый новый элемент не просто добавляет один шанс, он умножает количество уже существующих вариантов. Поэтому одно и то же правило — сложить или перемножить — важно применять строго, но умно. Рост вариантов идёт неравномерно: в некоторых случаях он почти линейный, а в других становится очень быстрым. И это полезный вывод: комбинаторика не только “считает”, но и объясняет, почему некоторые задачи легко, а другие требуют аккуратности. 6. Перестановки: когда важен порядок Перестановки: когда важен порядок Если нужно разместить все предметы в новом порядке, каждый вариант отличается расположением. Для четырёх книг порядок действительно “на вес золота”: поменяешь местами две — и уже получишь другой вариант. Если четыре книги полностью различимы, то количество перестановок не надо угадывать — его можно получить по стандартному правилу факториала. В учебной задаче это особенно наглядно: стартуем с первой позиции, затем выбираем для второй оставшийся вариант, и так далее, пока места не закончатся. 7. Основные формулы в простых комбинаторных задачах Основные формулы в простых комбинаторных задачах Таблица показывает три главных типа задач и помогает быстро выбрать нужный способ счёта. Когда задача сформулирована правильно, её почти всегда можно “разложить” на один из базовых случаев: перестановки, размещения или сочетания. Разница между ними определяется ответом на два вопроса — важен ли порядок и разрешены ли повторы (в простых формулировках повторы часто запрещены). Перестановки считают все порядки, размещения — выбор с учётом порядка, сочетания — выбор без него. Дальше, уже на этом фундаменте, любые более сложные ситуации превращаются в последовательность знакомых шагов. 8. Размещения: выбираем и расставляем Размещения: выбираем и расставляем Размещение используют тогда, когда берут только часть предметов, но порядок их расположения уже важен. Поэтому два одинаковых набора, стоящие по-разному, считаются разными вариантами. Представим школьный конкурс, где выбирают капитана и заместителя из нескольких учеников. Если состав командной “двойки” один и тот же, но должности распределены иначе, результат другой. Здесь порядок — не украшение, а часть условий. Такой же принцип работает, когда нужно поставить несколько книг на полку из большего числа. Важно не только какие книги выбраны, но и кто стоит первым, вторым и третьим. Именно поэтому в размещениях обычно “умножают по шагам”: сначала выбирают того, кто займёт первое место, затем — следующую позицию, и так далее. 9. Как выбрать способ решения задачи Как выбрать способ решения задачи Схема показывает, как определить тип комбинаторной задачи по условию. Иногда главный труд — не вычисления, а определение “типа”. Фактически решение начинается с мини-диагностики: что именно рассматривается как разные случаи? Такой подход напоминает работу следователя: сначала фиксируются признаки — меняется ли порядок, разрешены ли повторы, рассматривается ли выбор целиком или только частично. А затем выбирается “правильный инструмент”. Хорошая схема экономит время: вместо случайных попыток формула подбирается почти автоматически. 10. Сочетания: выбираем без порядка Сочетания: выбираем без порядка Сочетание описывает выбор предметов, где важно только, какие объекты попали в набор. Если поменять их местами, новый вариант не появляется, потому что состав остаётся тем же. Этот способ счёта подходит для команд, наборов вкусов и других ситуаций без порядка. Он помогает не считать один и тот же набор несколько раз, если его записали по-разному. Ключевая мысль сочетаний — “состав важнее расстановки”. Если выбираются участники в команду, то кто в каком порядке записан — не имеет значения. Именно поэтому при сочетаниях чаще используют формулы, которые “убирают” лишний подсчёт, возникающий из-за перестановок внутри одного набора. 11. Треугольник Паскаля и числа сочетаний Треугольник Паскаля и числа сочетаний Каждая строка строится из суммы двух соседних чисел над ней. Это как привычная таблица складывания, только она устроена так, что постепенно возникают числа сочетаний. Симметрия строк помогает быстро находить сочетания и проверять ответ без длинных вычислений. Если в строке число оказалось с одной стороны, то оно должно повториться зеркально. Это не магия, а аккуратное отражение структуры формулы сочетаний. Треугольник Паскаля стал популярным благодаря Уилльяму Паскалю и его математической культуре во Франции, а сама идея взаимосвязи коэффициентов и комбинаторных выборов позже стала основой для многих разделов алгебры. Для школьника треугольник особенно удобен как “подсказка”, когда нужно оценить или проверить результат. 12. Комбинаторные задачи с кодами и паролями Комбинаторные задачи с кодами и паролями Если код состоит из нескольких символов, сначала уточняют длину записи и набор доступных знаков. Именно эти два условия определяют, сколько всего вариантов можно получить. В большинстве кодов порядок символов важен: 12 и 21 — разные записи. Поэтому задачи на пароли почти всегда относятся к случаям, где учитывается последовательность выбора, и подсчёт идёт как цепочка вариантов на каждой позиции. Если повторы разрешены, число вариантов обычно считают по правилу произведения: каждый следующий знак выбирают независимо от предыдущих. Запрет повторов сразу уменьшает число кодов, потому что “следующая клетка” уже не имеет полного набора возможностей. Полезно отдельно проверить, допускаются ли нули в начале и могут ли совпадать символы. Такие детали часто меняют ответ сильнее, чем кажется сначала. Иногда один запрет превращает огромное количество вариантов в заметно меньшее — а значит, меняется и устойчивость пароля, и сложность задачи. 13. Порядок и повторения: четыре важных случая Порядок и повторения: четыре важных случая Сравнение помогает сразу выбрать нужный способ подсчёта и избежать путаницы между выбором и расстановкой. Если порядок важен или не важен, и если повторы разрешены или запрещены — получается ровно тот набор “ключей”, который открывает нужную формулу. Именно поэтому таблица напоминает не про вычисления, а про решение проблем с формулировкой. Сначала нужно определить два признака: важен ли порядок и разрешены ли повторы. После этого выбор формулы становится однозначным. Такой подход снижает вероятность ошибки: даже когда цифры в конце большие, логика должна быть чистой уже в начале. 14. Комбинаторика и вероятность Комбинаторика и вероятность Сначала находят общее число возможных исходов опыта. Затем считают, сколько из них удовлетворяют нужному условию, и только после этого составляют отношение двух чисел. Если событие связано с выбором предметов, комбинаторика помогает перечислить все варианты без пропусков. Это особенно удобно в задачах с шарами, картами, кубиками и жетонами. Чем точнее подсчитано число исходов, тем надёжнее ответ в вероятности. Ошибка в комбинаторном счёте сразу искажает весь результат, поэтому порядок и повторы нужно проверять заранее. В этом месте комбинаторика становится не просто “математической техникой”, а источником здравого смысла: вероятность — это не угадывание, а аккуратное сравнение “сколько всего” и “сколько подходит условию”. 15. Сколько исходов бывает в простых опытах Сколько исходов бывает в простых опытах При независимых действиях удобно сначала считать исходы каждого шага отдельно, а затем перемножать результаты. Независимость — важное слово: оно означает, что исход одного шага не влияет на доступные варианты другого. Тогда произведение действительно описывает всё многообразие пар, тройек и более длинных последовательностей. При объединении независимых опытов число исходов резко растёт, поэтому правило произведения экономит время и уменьшает риск ошибки. Это тот же принцип, что и в задачах про коды: если на первой позиции доступно столько-то символов, а на второй — столько-то, то вместе получается произведение. И в итоге формируется общий навык: сначала распознать структуру, затем выбрать действие — сложение или умножение, а уже потом аккуратно довести вычисление до ответа. 16. Перебор вариантов и дерево решений Любая комбинаторная задача начинается с одной и той же привычки: не прыгать сразу к ответу, а сначала понять, какие варианты вообще существуют. Даже когда кажется, что «всё и так ясно», часто теряется один важный кусочек — или появляются повторы, или некоторые случаи остаются вне рассмотрения. Вообще, идея перебора знакома давно: ещё математики Средневековья и раннего Нового времени сталкивались с задачами подсчёта, где нужно было проследить все возможности. Сегодня мы делаем это аккуратнее: строим дерево решений. Это как маршрут по развилкам. Каждая развилка — выбор, каждое продолжение — следующая часть. Когда ветка заканчивается, полученный маршрут соответствует одному конкретному варианту. Представим, что вариантов можно «обойти» как улочки в старом городе: если двигаться без системы, легко вернуться тем же путём и принять одно и то же за два разных. Дерево решений помогает избежать такого ощущения «кажется, что всё учтено». Напротив: оно заставляет пройти каждую ветку ровно один раз — и заметить, где условие ограничивает выбор. Вот три маленькие истории, которые хорошо объясняют сам подход. Первая история — про «перепутанную дорожку». Например, в задаче про выбор нескольких предметов из разных по цвету вариантов человек записывает результаты в разном порядке и считает, что это разные варианты. В реальности это один и тот же выбор. Дерево решений обычно вскрывает такую ошибку: если на верхнем уровне выбор один, а потом порядок лишь меняет запись, то ветки оказываются «про тем же набором», а не про новые случаи. Вторая история — про «ограничение, которое забыли». Есть задания, где по условию часть вариантов нельзя брать: «не подряд», «только разные», «только чётные», «не более одного элемента». В таких задачах самый коварный момент — увидеть условие позже, когда уже почти готов ответ. Дерево решений заставляет поставить «ограничитель» прямо на ветке: как только выбор нарушает условие, ветку прекращают. Третья история — про «слишком быстрый финиш». Иногда хочется посчитать первые несколько веток, почувствовать закономерность и остановиться. Но комбинаторика устроена так, что закономерность может появиться раньше, чем закончились все случаи. Полное дерево — как проверка на совесть: оно напоминает, что решение должно покрывать все листья, иначе ответ будет неполным. Так что перебор вариантов — это не «угадайка», а дисциплина. А дерево решений — способ сделать эту дисциплину видимой, чтобы ошибки становились заметными ещё до вычислений. 17. Типичные ошибки в комбинаторных задачах Когда подход уже ясен — выбор делается по системе, — возникает следующая трудность: ошибки. Чаще всего они не в арифметике, а в мышлении. Первая ошибка почти всегда связана с повторами. Очень распространённый сценарий: один и тот же набор вариантов учитывают несколько раз, просто записывая его в другом порядке. Классический пример — выбор без порядка. Если выбрать яблоко и грушу, то «яблоко+груша» и «груша+яблоко» — не два разных набора, а один и тот же. Перед подсчётом полезно задать простой контрольный вопрос: «Меняется ли результат от перестановки записи?» Если условие не считает порядок — перестановка не должна создавать новый вариант. Вторая ошибка — наоборот, не отличить «порядок важен» от «порядок не важен». Иногда люди автоматически считают как для выбора, хотя на самом деле речь о последовательности. Тогда разные последовательности должны считаться отдельно. Это особенно видно там, где порядок определён природой задачи: код на клавиатуре, очередь в банке, пароли. В таких историях перестановка превращает один вариант в другой, и «как же так, ведь набор тот же» — не аргумент. Третья ошибка — тема повторений. Бывает, что в условии сказано: элементы должны быть различными, но при переборе повторения случайно разрешают. Или наоборот: по условию повторения допускаются, а человек пытается запретить их «по привычке». В комбинаторике это меняет число вариантов очень сильно: иногда даже на целые порядки. Поэтому перед стартом перебора важно прямо выписать правило: «разрешены ли одинаковые элементы» и «сколько раз можно брать один и тот же». И, наконец, четвёртая ошибка — преждевременная остановка. У комбинаторных задач есть неприятная особенность: часть случаев может скрываться «в конце», и первая догадка работает не на всей области. Если выполнить перебор не до конца, ответ становится похожим на неполную картину: закономерность внутри видна, но общая сумма получается неверной. Итог простой: перебор должен покрывать все варианты ровно один раз — без дублей и без пропусков. Именно это правило превращает «дерево» из красивой картинки в надёжный инструмент. 18. Как меняется число способов выбора Теперь, когда ошибки известны, полезно увидеть, как вообще ведёт себя число вариантов. На следующем шаге появляется визуальная подсказка: как меняется количество способов выбора. Пусть в наборе всего 6 предметов, и нужно выбрать k из них. Тогда количество способов описывается биномиальными коэффициентами — сочетаниями C(6, k). Это не просто формула «для взрослых»: смысл в том, что мы считаем выбор без порядка. То есть важно только «какие» предметы выбраны, а не «в каком порядке» они перечислены. Очень заметное свойство сочетаний называется симметрией. Выбирая k предметов из 6, по сути мы оставляем «в стороне» остальные 6−k. Поэтому выбор k и выбор оставшихся 6−k дают одинаковое число возможностей. Говоря образно, это как две стороны одной медали: выбираешь часть — значит, автоматически определяешь, что не выбрано. Если проследить значения C(6, k) по всем k от 0 до 6, максимум обычно оказывается около середины. Интуитивно это объясняется просто: выбрать «половину» предметов — это как оказаться в самой большой толпе вариантов. Когда k маленькое или очень большое (почти 0 или почти 6), вариантов меньше: трудно составить много разных наборов, потому что выбор слишком узкий. Этот вывод полезен и для проверки ответов. Даже если вычисление сделано правильно, при сомнениях сравнение с ожидаемым «профилем» помогает заметить, что, например, выбран не тот тип счёта — порядок перепутан с выбором, или повторения разрешены там, где их нельзя. 19. Мини-набор задач для проверки Понимание формул становится куда устойчивее, когда есть короткие тренировки. Поэтому дальше — мини-набор задач, который помогает быстро определить тип ситуации. Смысл здесь такой: в комбинаторике большинство формул отличаются не «сложностью», а тем, что именно считается. Перестановки — когда мы упорядочиваем все объекты. Размещения — когда мы составляем последовательность из части объектов, то есть порядок важен. Сочетания — когда выбираем часть без учёта порядка. С практической точки зрения удобно действовать как переключателем режимов. Сначала читается условие и выделяется главный вопрос: «Можно ли менять порядок и получаются ли от этого новые варианты?» Если ответ да — это часто ведёт к перестановкам или размещениям. Если ответ нет — вероятнее сочетания. Дальше проверяется «частота повторений»: разрешены ли одинаковые элементы или каждый предмет берётся один раз. Это не теория ради теории — это то, что отличает задачи, где наборы уникальны, от задач, где элементы можно выбирать снова и снова. И ещё один маркер — есть ли в формулировке намёк на «распределение по местам» или на «выбор части». Когда написано про расстановку, места, очередность — чаще нужен счёт последовательностей. Когда говорится про выбор подмножества — счёт подмножеств. Мини-набор задач работает как диагностический тест: по одной короткой формулировке становится понятно, какую модель выбирать. Тогда формулы перестановок, размещений и сочетаний перестают быть наборами «разрозненных правил» и превращаются в понятный набор инструментов. 20. Главные выводы по теме В завершение — три мысли, которые удерживают в комбинаторике больше всего ошибок в узде. Первая: всегда нужно сначала определить, что именно считается — выбор, порядок или распределение по позициям. Это главный переключатель, без которого любая дальнейшая формула может применяться не к тому объекту. Вторая: после определения типа задачи формулы работают как навигатор. Правило суммы помогает объединять варианты, правило произведения — «умножать» независимые шаги, а формулы перестановок, размещений и сочетаний дают точный счёт для конкретных режимов. Третья: дисциплина перебора — гарантия правильности. Проверка на повторения, внимательность к порядку и полное покрытие всех случаев превращают задачу из гадания в строгий расчёт. Именно так ответы становятся надёжными, а не случайными совпадениями. Источники Демидович Б. П., Марон И. А. Сборник задач и упражнений по математике для средней школы. Комбинаторика и вероятность. — М.: Просвещение, (уточнить издание). Колмогоров А. Н. Основные понятия теории вероятностей. — М.: Наука, (уточнить издание). Кострикин А. И., Манин Ю. И. Математика: понятия и методы. Разделы по комбинаторике и алгебре. — М.: (уточнить издательство). Шварцбурд С. И. Комбинаторные задачи для школьников. — М.: (уточнить издательство), (уточнить год). Курант Р., Роббинс Г. Что такое математика? М.: МЦНМО, 2016. Пойа Д. Как решать задачу? М.: АСТ, 2020. Грэм Р., Кнут Д., Паташник О. Конкретная математика: Основание для информатики. М.: Мир, 1998. Виленкин Н. Я., Линник Ю. М., Звавич Л. А. Комбинаторика. М.: Просвещение, 1979.