Комбинаторика
2026-02-26 18:44 Diff
https://ru.hexlet.io/courses/combinatorics/lessons/intro/theory_unit

На этом курсе будем изучать комбинаторику — очередной раздел дискретной математики.

Комбинаторика изучает сочетания, перестановки, размещения и перечисления отдельных объектов и множеств. Эта дисциплина помогает глубже понять алгебру, геометрию и теорию вероятностей. Еще без нее не обойтись в генетике, информатике, статистической физике.

В этом уроке мы выясним, что такое комбинаторика и чем она полезна в программировании. Мы познакомимся с базовой терминологией и узнаем об основных инструментах комбинаторики. Эти знания помогут нам погрузиться в новую дисциплину и подготовиться к решению комбинаторных задач.

Что такое комбинаторика

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

Множество: {2,5,8} Элементы множества: 2, 5 и 8

Из любого множества можно составить разные сочетания — комбинации. В нашем примере множество {2,5,8} состоит из трех элементов (2, 5 и 8), из которых можно составить шесть трехзначных комбинаций:

Комбинации: 258, 285, 528, 582, 825, 852

В программировании комбинаторика помогает тестировать программы и анализировать алгоритмы. Она автоматизирует расчеты количества возможных ситуаций. Другими словами, с помощью комбинаторики можно ответить на вопрос: «Сколько комбинаций можно собрать из конкретных элементов и по конкретным правилам?».

Этот вопрос часто встает в реальных задачах программиста, особенно когда речь идет о работе с большими данными или таблицами. Даже с перебором паролей без комбинаторики не справится:

  • Представим, что мы создали сайт и выбираем правила, каким должен быть пароль пользователя
  • Решили не усложнять жизнь пользователю и поставили такие правила «Пароль должен состоять только из цифр, длина пароля — 4 символа»
  • Пока не очевидно, насколько надежным получится такой пароль. Чтобы это понять, надо вычислить, сколько возможно комбинаций. Ответить на этот вопрос помогает комбинаторика

Подобные задачи можно решить с помощью трех методов:

  • Комбинаторные формулы
  • Динамическое программирование
  • Рекурсивные алгоритмы полного или частичного перебора

В этом курсе будем рассматривать решение с помощью комбинаторных формул. Динамическое программирование и рекурсивные алгоритмы перебора подробнее рассмотрены в других курсах Хекслета.

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

Комбинаторные задачи и инструменты

В этом курсе мы сосредоточимся на трех типах комбинаторных задач:

Такие задачи можно решить различными методами. В этом курсе мы рассмотрим следующие комбинаторные инструменты:

  • Способы подсчета
  • Счет через биекцию
  • Принцип включения и исключения
  • Теорема Рамсея
  • Порождающие функции
  • «Принцип голубятни»

Подробнее перечисленные типы и инструменты будем разбирать в отдельных уроках.

А сейчас познакомимся с основными обозначениями, которые будут часто встречаться на курсе. Они помогут легче понимать теорию и проходить практику.

Основные обозначения в комбинаторике

Многие обозначения в комбинаторике нам уже знакомы: они используются в математической логике и теории множеств. Поэтому в этом курсе мы не будем разбирать их подробно, но сосредоточимся на неизвестных понятиях.

Перечислим ключевые понятия для комбинаторики:

Еще одно важное понятие — это семейства множеств (или системы множеств).

Для примера рассмотрим семейство множеств F:

Пара (X,F), где X — конечное множество, а F subseteq P (X)

У разных семейств множеств могут быть разные характеристики, на которые мы должны обращать внимание:

Подробнее о множествах и их характеристикам мы говорили в курсе «Теория множеств» — можете обратиться к нему, чтобы освежить знания.

Еще в комбинаторике часто работают с графами, чтобы визуализировать задачу. Разберем, что это такое и как они выглядят.

Графы

Графы — это инструмент, который помогает подсчитывать и перебирать различные комбинации в задаче. Это совокупность точек, которые соединены линиями. Точки называются вершинами или узлами, а линии — ребрами, которые обозначают, какие узлы связаны между собой. Например:

Граф G — это пара (V, E), где V — конечное множество, а E — набор подмножеств размера 2 из V. Члены V — вершины, члены E — ребра.

Например, если e = {u, v} — ребро, то u и v — его конечные точки. Мы говорим, что u и v смежны, и что u и v инцидентны e.

Степень вершины v, которая обозначается как deg(v) — это количество ребер, где v — конечная точка. Вершина со степенью 0 называется изолированной.

С помощью графов можно визуализировать задачу, что поможет понять и решить ее легче и быстрее.

Выводы

В этом вводном уроке мы обсудили особенности комбинаторики и узнали, в каких практических задачах она применяется.

Еще мы рассмотрели основные символы, которые встречаются в большинстве случаев, и графы, которые помогают визуализировать задачу. Остальные обозначения изучим, когда будем разбирать инструменты и комбинаторные задачи подробнее.