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

• Множества и операции над ними. Вспомним, что такое множества (а это основной объект комбинаторики) и какие операции над ними можно выполнять.
• Ключевые правила подсчета. Изучим главные принципы: правило суммы, правило произведения и принцип Дирихле.
• Классические комбинаторные формулы. Разберёмся в перестановках, размещениях и сочетаниях — с повторениями и без.
• Биномиальные коэффициенты. Увидим, как число сочетаний связано с треугольником Паскаля и формулой бинома Ньютона.

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

Зачем вообще нужна комбинаторика

Представьте, вам нужно собрать команду из подходящих соискателей. Или придумать надёжный пароль. Или придумать новый формат хранения данных о пользователях вашего продукта. Во всех подобных задачах встаёт один и тот же вопрос: а сколько разных конфигураций объектов вообще может быть?

И ответ на этот вопрос, а также на множество других, даёт именно комбинаторика.

Внимательный читатель заметит, что техники подсчёта пригодятся далеко за пределами чистой математики: в криптографии, биоинформатике, машинном обучении и много где ещё. Конечно, явно комбинаторика применяется в анализе данных и машинном обучении гораздо реже, чем линейная алгебра или же теория вероятностей.

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

Мы постараемся разобрать все основные понятия и методы, чтобы слова комбинаторный взрыв или power set не вызывали недоумения, и начнём мы с самого главного — с понятия множества.

Множества, отношения между множествами и основные понятия

Множество

Одним из центральных понятий в комбинаторике является множество.

💡Множество — это набор уникальных объектов, порядок которых не имеет значения, важно лишь их наличие или отсутствие.

Объекты, входящие в множества, обычно называют элементами множества или точками множества. В литературе элементы множества обычно заключают в фигурные скобки.

Отношения между множествами

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

Пример

Представим, что у нас есть:

• Множество — все студенты университета.
• Множество — все студенты факультета математики.

Поскольку каждый студент факультета математики () является также студентом университета (), то множество включено в множество ().

Важно заметить, что все элементы любого множества входят в него, а значит, множество включено в само себя: .

Равенство. Обозначается как . Если множество включено в множество , а множество включено в множество , т. е. они содержат одни и те же элементы, то они равны:

Пример

Бухгалтерия расположена в кабинете 69. В ней работают три сотрудника. Тогда:

• Множество (сотрудники бухгалтерии)
• Множество (обитатели кабинета 69)

Проверка условия:

• — каждый сотрудник бухгалтерии () находится в кабинете 69 ().
• — все люди в кабинете 69 () являются сотрудниками бухгалтерии ().

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

💡Примечание

Иногда отдельно выделяют отношения строгого включения множеств:

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

Подмножество

Вместе с понятием множества необходимо ввести и понятие подмножества.

💡Подножеством множества является любое множество, все элементы которого входят в .

Таким образом, любое множество, включённое в множество , будет являться его подмножеством, включая само множество !

Иногда выделяют понятие собственного подмножества: является собственным подмножеством , если оно является подмножеством и эти множества не совпадают, т. е.:

что полностью соответствует определению строгого включения, которое мы привели выше.

Пустое множество

Остается лишь ввести понятие пустого множества, которое стоит несколько обособленно. Пустое множество обозначается как и буквально означает множество, в котором не содержится ни одного элемента.

Важно:

💡Пустое множество — это подмножество любого другого множества.

Внимательно отнеситесь к этому факту, т. к. практика показывает, что он может показаться неочевидным. Однако он ещё не раз нам пригодится, например когда мы будем говорить о множестве всех подмножеств.

Пример отношений между множествами

В целях иллюстрации введем несколько множеств: , , и .

Заметим, что множества и равны: , т. к. порядок элементов не имеет значения. Также оба множества являются собственными подмножествами множества :

Множество никак не связано с остальными.

Способы задания множеств

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

Например:

• Множество всех букв русского алфавита: ,
• Множество — (это просто множество, заданное явным образом, не ищите в нём скрытого смысла).

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

• Множество всех положительных чисел , где — множество действительных чисел.
• Множество всех чётных чисел: , которое можно задать несколькими способами, оба приведённых определения верны. Здесь — множество целых чисел.
• Множество всех строк в латинском алфавите длиной не более , содержащих хотя бы одну букву q (формульную запись подобного множества опустим, т. к. она требует введения дополнительных обозначений и не является обязательной).

Заданием множеств через описание часто пользуются, и вы почти наверняка уже с ним встречались, например когда говорили об области значений функции:

Конечные и бесконечные множества

Множества могут включать различное число элементов.

Конечным множеством будем называть множество, количество элементов которого конечно. Соответственно, бесконечным множеством будем называть то, количество элементов которого бесконечно.

Примечание

Если мы говорим о бесконечных множествах, важно также разделять счётные и несчётные множества. Счётным множеством называется то, все элементы которого можно взаимно однозначно сопоставить с множеством натуральных чисел . Если же это невозможно, множество называется несчётным.

Например, множество всех целых чисел и даже множество рациональных чисел являются счётными. Данный факт доказывается в курсах введения в математический анализ, ознакомиться с ним можно, например, в лемме 4 здесь.

Мощность множества

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

💡В разных дисциплинах термин мощность иногда заменяют словами кардинальность или просто размер. Мы будем пользоваться первым вариантом для единообразия.

Пример множеств разной мощности

Пусть — множество всех учащихся начальной школы, общее число которых равно 97, а — множество всех первоклассников, которых 32. Тогда , а , и согласно определению является собственным подмножеством , т. е. .

Заметим, что мощность собственного подмножества конечного множества всегда меньше мощности самого множества.

Также обратим внимание на пустое множество . Его мощность, конечно, равна нулю: , т. к. оно не содержит ни одного элемента.

Наконец-то мы ввели основные понятия, которые повсеместно используются в комбинаторике и получили широкое распространение за её пределами. Теперь мы полностью готовы к обсуждению операций над множествами, которые рассмотрим далее.

Основные операции над множествами

Рассмотрим основные операции над множествами: пересечение, объединение, разность, симметрическую разность (XOR), а также декартово произведение.

А чтобы вам было легче воспринимать теорию — покажем эти операции на примерах из жизни.

Обращаем ваше внимание: множества и будут использоваться как абстрактные множества, а множества, связанные с примерами, мы постараемся называть с использованием других латинских букв.

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

Обозначим множество всех людей в школе за (от слова school). Множество одноклассников Пети является собственным подмножеством всех людей в школе: . Также есть множество всех мальчиков и множество всех девочек . Множество всех учителей обозначим как , а учителей, которые преподают у класса Пети, как .

Ещё раз, для удобства:

• .
• .
• .
• .
• .
• , .

Пересечение множеств

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

Пересечением множеств будем называть множество элементов, принадлежащих одновременно и к , и к :

В случае с Петей именно людей из пересечения множеств и стоит звать играть в футбол:

Обратим внимание, что множества мальчиков и девочек не содержат общих элементов, как и множества одноклассников и учителей . Их пересечениями будет пустое множество , с которым мы уже сталкивались ранее:

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

Пересечение пустого множества с любым другим возвращает пустое множество.

Объединение множеств

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

Объединением множеств и будем называть множество элементов, принадлежащих хотя бы к одному из них, т. е. к , к или к обоим множествам сразу:

В случае с Петей угощать ягодами нужно будет объединение множеств и :

Обратим внимание, что объединение всех мальчиков и всех девочек школы включает в себя вообще всех людей школы:

Также уделим внимание пустому множеству: объединение пустого множества с любым другим возвращает то же самое множество:

Вообще, пустое множество можно воспринимать как нейтральный элемент для операции объединения множеств.

Также посчитаем количество людей, которых Петя собрался угостить. В конкретно данном примере мы бы получили нужное число, сложив число одноклассников и число учителей , ведь множества учеников и учителей не пересекаются, но в общем случае это неверно! Если бы множества пересекались, то мы бы учли людей из пересечения дважды. Общая же формула будет иметь вид:

Разность множеств

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

Разностью множеств и будем называть множество элементов , которые при этом отсутствуют в :

Т. е. маме Пети нужно зайти к множеству учителей:

Обратим внимание, что разность множеств некоммутативна, т. е. чувствительна к порядку операций:

Например, в случае с учителями:

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

Теперь посчитаем количество учителей, которых хочет угостить мама Пети: это все учителя, кроме тех, кто учит класс Пети. Или же, в виде формулы:

В терминах же абстрактных множеств мощность разности имеет вид:

Симметрическая разность

К концу четверти Петя подружился с одноклассниками и даже пошел в секцию по футболу. Сборная команда школы как раз победила в важных соревнованиях, и теперь всех игроков хотят поздравить, устроив им сюрприз. Введём еще несколько множеств: — всех людей, кто ездил на соревнования от школы (тренер, медицинский работник и сама команда), — непосредственно команда, игравшая в футбол, и — все школьники, которые ходят в секцию. Для удобства приведём их отдельным списком:

• .

Легко заметить, что , т. к. все игроки победившей команды ездили на соревнования, а , ведь из ездивших на соревнования лишь школьники играли в футбол в зачёте.

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

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

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

Обратим внимание, что симметрическая разность также является коммутативной: порядок множеств в данной операции не важен.

В случае с Петей нас интересует симметрическая разность множества и :

в которую входят тренер, медработник и все школьники из секции, не участвовавшие в соревновании.

Если же понадобится посчитать количество людей, которые будут готовить сюрприз, то:

В терминах абстрактных множеств мощность симметрической разности имеет вид:

Декартово произведение

Особняком стоит операция декартова произведения, но из-за её широкой применимости не сказать о ней в этом разделе мы не можем.

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

• — тип регуляризации.
• — значения коэффицента регуляризации.

Для каждого типа регуляризации нужно перебрать все указанные значения коэффициента регуляризации. Именно здесь нам поможет декартово произведение.

Декартово произведение множеств и есть множество всех возможных упорядоченных пар, где первый элемент принадлежит множеству , а второй — множеству :

В случае с примером выше мы получим шесть различных наборов значений гиперпараметров. Их проще всего представить в виде таблицы:

Reg type\Reg coefficient

Важно заметить, что декартово произведение по формальным критериям не является коммутативной операцией, т. к. пары в итоговом множестве упорядочены. На практике, например, если вам нужно перебрать все возможные комбинации гиперпараметров и вы знаете, на каком месте стоит какой из них, порядок роли не играет.

Сводная таблица операций над множествами

Для удобства приведём все рассмотренные операции в единой таблице:

Операция	Формула	Коммутативна	Мощность результата
Пересечение		Да
Объединение		Да
Разность		Нет
Симметрическая разность (XOR)		Да
Декартово произведение		Нет

Операции над несколькими множествами

До сих пор мы работали лишь с парами множеств и именно для них вводили все основные операции. Однако на практике приходится работать сразу с несколькими. Операции объединения и пересечения ведут себя ожидаемым образом:

Разность и симметрическая разность используются именно для пар, так что обобщать их на несколько множеств не будем.

Декартово же произведение может быть применено для троек, четвёрок и т. д. множеств:

Здесь мы можем впервые для данного повествования заметить явление комбинаторного взрыва: даже если мощность каждого отдельного множества небольшая — мы всё ещё говорим о конечных множествах, — мощность их декартова произведения может быть очень большой. Например, если у нас 10 гиперпараметров, каждый из которых может принимать всего по 5 значений (множество значений ), то итоговое количество комбинаций, которые придётся перебрать, составляет:

что на практике зачастую не представляется возможным.

Связь с событиями в теории вероятностей

Внимательные читатели могут обратить внимание, что работа с множествами очень похожа на работу с событиями в теории вероятностей, и это неспроста.

События в теории вероятностей — также множества, просто они обладают дополнительными свойствами, которые необходимы, чтобы пользоваться математическим аппаратом теории вероятностей.

Например, вводится понятие меры, для каждого события есть его отрицание , которое очень похоже на дополнение множества, но мы опустили это определение в данном параграфе. События также могут пересекаться, объединяться и др. Более подробно вы можете прочитать об этом в главе, посвященной теории вероятностей. Надеемся, вы обнаружите для себя много общего и это поможет вам лучше понять математические основы машинного обучения и анализа данных.

---

Итак, мы зафиксировали язык, на котором разговаривает комбинаторика.

Определили множества, подмножества и пустое множество, обсудили мощность, а также базовые операции: пересечение, объединение, разность, симметрическую разность и декартово произведение.

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

Теперь, когда мы умеем корректно описывать, что именно считаем, перейдём к тому, как это считать. В следующем параграфе мы формализуем два краеугольных правила — правило суммы (это когда варианты исключают друг друга) и правило произведения (когда выборы независимы), разберем принцип Дирихле, а затем выведем и сопоставим классические формулы для перестановок, размещений и сочетаний — с повторениями и без. Это даст нам компактный и практичный калькулятор для последующих задач.