Комбинаторика#
”Первый ход — Е2-Е4, а там… А там посмотрим.” (Остап Бендер)
Комбинаторика занимается подсчетом числа элементов в множествах. Практическая польза - например, оценка числа комбинаций для перебора.
Основные правила комбинаторики#
Далее рассматриваются только конечные множества.
Правило сложения#
Пусть \(A, B\) - два конечных непересекающихся множества, \(|A| = n\), \(|B| = m\), \(A \cap B = \varnothing\). Тогда сколько элементов в двух этих множествах?
\(|A \cup B| = |A| + |B| = n + m\)
Пример. На столе лежат конфеты двух видов: 5 шоколадных и 7 карамельных. Сколькими существует способов выбрать одну конфету?
Два непересекающихся множества: шоколадные конфеты и карамельные конфеты. По правилу сложения ответ в задаче \(5 + 7 = 12\).
Note
Правило сложения используется, когда количества соединены союзом “или”.
Например: в стакане \(n\) ручек и \(m\) карандашей. Сколькими способами можно выбрать один пишущий предмет (карандаш или ручку)?
Правило умножения#
Пусть \(A, B\) - два конечных множества, \(|A| = n\), \(|B| = m\). Сколькими способами мы можем выбрать один элемент из \(A\) и вслед за ним - один элемент из \(B\)?
\(|A \times B| = |A| \cdot |B| = n \cdot m\)
Пример. Сегодня вечером мы посмотрим один из 3 фильмов, вслед за чем сыграем в одну из 2 настольных игр. Сколько существует способов провести вечер?
Два множества: фильмов и настольных игр. Выбрать пару “фильм, игра” по правилу умножения можно \(3 \cdot 2 = 6\) способами.
Упражнение. Чтобы добраться до Москвы из Владивостока, надо сперва добраться до аэропорта (на такси, на поезде или на автобусе), а затем долететь на самолёте на одном из 4 рейсов. Сколькими способами можно добраться из Владивостока до Москвы?
Note
Правило умножения используется, когда количества соединены союзом “и”.
Например: в стакане \(n\) ручек и \(m\) карандашей. Сколькими способами можно выбрать пару предметов (карандаш и ручку)?
Размещения без повторений и перестановки#
Пусть \(A\) - конечное множество, \(|A| = n\).
Размещение (без повторений) - это упорядоченная выборка из \(k\) различных элементов множества \(A\).
Например, если \(A = \{a, b, c, d\}\), \(k = 2\), то все размещения:
ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc
На первом месте - любой из \(n = 4\) элементов множества \(A\), на втором месте - любой из \(n - 1 = 3\) оставшихся элементов. Всего (по правилу умножения) \(n (n-1) = 4 \cdot 3 = 12\) размещений.
Пример. Куплено 12 различных книг. На полке можно расставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?
На первое место можно поставить любую из 12 книг, на второе место - любую из 11 оставшихся, на третье место - любую из 10 оставшихся, далее одну из 9, одну из 8 и одну из 7. По правилу умножения, искомое число способов равно
\(12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 665280\).
Вообще число способов выбрать в определенном порядке \(k\) различных объектов из \(n\) вычисляется по формуле
\( (n)_k = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+2) \cdot (n-k+1). \)
Запись \((n)_k\) читается “от \(n\) вниз \(k\)”, то есть умножение \(k\) множителей: от \(n\) до \(n-k+1\).
Для числа размещений без повторений принято следующее обозначение:
\(A_n^k = (n)_k = n \cdot (n-1)\cdot \ldots \cdot (n-k+1) = \dfrac{n!}{(n-k)!}\)
Поясним эту формулу подробнее:
\( \dfrac{n!}{(n-k)!} = \dfrac{1 \cdot 2 \cdot \ldots \cdot (n - k) \cdot (n - k + 1) \cdot \ldots \cdot n}{1 \cdot 2 \cdot \ldots \cdot (n-k)} = (n - k + 1) \cdot \ldots \cdot n \)
Пример. Куплено 6 различных книг. На полке можно расставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?
В задаче требуется найти общее число выборок из 6 элементов, выбранных из 6-элементного множества. Согласно общей формуле, ответ в задаче равен
\(A_6^6 = \dfrac{6!}{(6-6)!} = 6! = 720\)
Размещения без повторений из \(n\) по \(n\) еще называют перестановками из \(n\) элементов. Число перестановок из \(n\) элементов обозначается \(P_n\).
\(P_n = n! = 1 \cdot 2 \cdot \ldots \cdot n\)
Сочетания без повторений#
Вернёмся к примеру с размещениями (упорядоченными выборками). Посмотрим, как связать упорядоченные выборки с неупорядоченными.
Если \(A = \{a, b, c, d\}\), \(k = 2\), то все размещения:
ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc
Введём на множестве размещений отношение эквивалентности и сгруппируем все размещения по классам эквивалентности.
\( \{ab, ba\}, \{ac, ca\}, \{ad, da\}, \{bc, cb\}, \{bd, db\}, \{cd, dc\} \)
В каждой группе оказалось по два размещения. Если всего размещений \(12\), а в каждой группе \(2\) размещения, то можно найти число групп: \(12/2 = 6\).
Как быть в общем случае выборки \(k\) элементов из \(n\)-элементного множества? Всего размещений \(A_n^k\). Разобьём их на классы эквивалентности: в один класс попадут размещения, отличающиеся только порядком следования элементов. В каждом классе окажется \(k!\) размещений. Действительно, всякую неупорядоченную выборку из \(k\) элементов можно упорядочить \(k!\) способами.
Каждый класс эквивалентности - это сочетание (без повторений), или неупорядоченная выборка \(k\) различных элементов \(n\)-элементного множества.
Число сочетаний из \(n\) по \(k\) вычисляется по формуле
\( C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{k!(n-k)!} \)
Пример. Перечислим все сочетания из множества \(A = \{a, b, c, d\}\) по \(k = 2\):
\(\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}\)
Каждое сочетание из 4 по 2 - это 2-элементное подмножество 4-элементного множества.
Пример. \(n\) человек пожали друг другу руки. Сколько рукопожатий?
Посчитаем число неупорядоченных выборок из 2 разных объектов - это число сочетаний \(C_n^2 = \dfrac{n!}{2!(n-2)!} = \dfrac{n(n-1)}{2}\).
Пример. Сколькими способами можно расставить 4 одинаковые фигуры на шахматной доске?
Пусть \(A\) - это множество клеток шахматной доски, из которого извлекается \(4\) элемента (без учёта порядка).
Упорядоченных выборок \(64 \cdot 63 \cdot 62 \cdot 61\). Неупорядоченных выборок в \(4! = 24\) раз меньше, чем упорядоченных, потому что при выборе 4 мест существует \(4!\) способов упорядочить эту выборку.
Итак, число способов выбрать 4 клетки из 64 (без учёта порядка) равно \(C_{64}^4 = \dfrac{64 \cdot 63 \cdot 62 \cdot 61}{24}\).
Упражнение. Сколько треугольников можно построить на 10 точках?
Размещения с повторениями#
Размещение с повторениями - это упорядоченная выборка элементов заданного множества, в которой элементы могут повторяться.
Например, если \(A = \{a, b, c, d\}\), \(k = 2\), то все размещения с повторениями:
aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd
На каждую из двух позиций мы можем выбрать любой из 4 элементов множества \(A\). По правилу умножения, упорядоченных выборок с повторениями \(4 \cdot 4 = 16\).
Итак, число размещений с повторениями из \(n\) по \(k\) вычисляется по формуле
\(\overline{A_n^k} = n^k\)
Пример. Сколько различных комбинаций может получиться при одновременном бросании трёх игральных костей?
При бросании будем получать наборы \((a_1, a_2, a_3)\), где \(a_i \in \{1..6\}\) - количество очков, выпавших на соответствующей кости. Общее число указанных наборов равно \(\overline{A_6^3} = 6^3 = 216\).
Сочетания с повторениями#
Введем понятие мультимножества. Назовём \(k\)-мультимножеством неупорядоченную выборку (с повторениями) из \(k\) элементов. Два \(k\)-мультимножества считаются одинаковыми, если одинаковых элементов в них поровну. Например, \(\langle 1, 2, 2, 3\rangle = \langle 2, 1, 3, 2 \rangle\), но \(\langle 1, 2, 3\rangle \neq \langle 1, 2, 2, 3\rangle\).
Любое \(k\)-мультимножество, составленное из элементов \(n\)-элементного множества, называется сочетанием с повторениями из \(n\) по \(k\).
Пример. Все сочетания с повторениями из множества \(A = \{a, b, c, d\}\) по \(k = 2\):
\(\langle a, a \rangle, \langle a, b \rangle, \langle a, c \rangle, \langle a, d \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle b, d \rangle, \langle c, c \rangle, \langle c, d \rangle, \langle d, d\rangle\)
Как посчитать число различных сочетаний с повторениями из \(n\) по \(k\)? Может, просто разделить число размещений с повторениями на факториал чего-нибудь? Так не получится, ибо в разных классах эквивалентности здесь разное число элементов.
Сопоставим каждому \(k\)-мультимножеству из элементов множества \(A\), \(|A| = n\), его двоичный код.
На рисунке показано построение кода на примере мультимножества \(\langle a, b, b, c, e, e, e\rangle\) (выборка из множества \(A = \{a, b, c, d, e\}\)). Всего у нас 5 “типов” элементов выборки: a, b, c, d, e. Элементов каждого типа может выбрано сколько угодно, но так, чтобы в сумме было выбрано \(k = 7\) элементов.
Красными черточками на рисунке обозначены элементы, отнесенные к одному из \(n = 5\) классов. Чтобы построить двочиный код, сопоставим каждой черточке “единицу”, а каждой перегородке между классами - “ноль”. В начале и конце кода нули не ставятся, за исключением случая, когда они соответствуют перегородкам.
Таким образом, мультимножеству \(\langle a, b, b, c, e, e, e\rangle\) соответствует код \(10110100111\).
Всякому сочетанию с повторениями из \(n\) по \(k\) соответствует двоичный код из \(k\) единиц и \(n - 1\) нулей. Обратно, по любой последовательности из \(n + k - 1\) нулей и единиц, в которой ровно \(k\) единиц, можно построить \(k\)-мультимножество, пользуясь тем же правилом.
Иными словами, между всеми сочетаниями с повторениями из \(n\) по \(k\) и всеми двоичными кодами из \(k\) единиц и \(n-1\) нулей существует взаимно однозначное соответствие (биекция). Следовательно, сочетаний с повторениями столько же, сколько двоичных кодов.
Посчитаем число двоичных кодов из \(k\) единиц и \(n-1\) нулей. Для этого заметим, что места из \(n+k-1\) цифр, на которых будут стоять единицы, образуют подмножество - неупорядоченную выборку без повторений, или сочетание без повторений из \(n+k-1\) по \(k\). Итак, число двоичных кодов равно числу сочетаний без повторений из \(n+k-1\) по \(k\), то есть \(C_{n+k-1}^k\).
Поэтому число сочетаний с повторениями из \(n\) по \(k\) вычисляется по формуле:
\( \overline{C_n^k} = C_{n+k-1}^k \)
Пример. В магазине продаются онигири 3 видов. Покупатель хочет купить 5 онигири. Сколькими способами возможно сделать покупку?
Производится неупорядоченная выборка с повторениями 5 онигири из множества из 3 видов. Число различных выборок вычисляется по формуле \(\overline{C_3^5} = C_7^5 = C_7^2 = \dfrac{7 \cdot 6}{1 \cdot 2} = 42\).
Упражнение. Перечислите все сочетания с повторениями из \(n = 4\) по \(k = 2\), укажите для каждого из них соответствующий двоичный код.
Связь с множествами и функциями#
Задача. Вычислить число всех подмножеств \(n\)-элементного множества, состоящих ровно из \(k\) элементов.
Ответ: число сочетаний без повторений из \(n\) по \(k\), то есть \(C_n^k\).
Задача. Найти число различных функций \(f \colon A \to B\) из \(n\)-элементного множества \(A\) в \(m\)-элементное множество \(B\).
Ответ: число размещений с повторениями из \(m\) по \(n\), то есть \(\overline{A_m^n} = m^n\).
(Действительно, производится выборка из \(n\) элементов \(m\)-элементного множества.)
Задача. Найти число инъекций \(f \colon A \to B\) из \(n\)-элементного множества \(A\) в \(m\)-элементное множество \(B\).
Ответ: число размещений без повторений из \(m\) по \(n\), то есть \(A_m^n\).
(Производится выборка из \(n\) различных элементов \(m\)-элементного множества.)
Замечание. Число сюръекций вычисляется сложнее, см. раздел “Числа Стирлинга 2-го рода”.
Резюме#
без повторений |
с повторениями |
|
|---|---|---|
упорядоченные выборки (размещения) |
\(A_n^k\) |
\(\overline{A_n^k}\) |
неупорядоченные выборки (сочетания) |
\(C_n^k\) |
\(\overline{C_n^k}\) |
Решая комбинаторную задачу, нужно обозначить множество, из которого производится выборка, а затем указать разновидность выборки (по 2 критериям: наличие повторений и учёт порядка).
Примеры комбинаторных задач#
Пример. Сколькими способами можно поставить на шахматную доску белого и чёрного короля, чтобы они не били друг друга?
Прежде всего надо определиться, что мы считаем. Из какого множества производится выборка? Считаем упорядоченные или неупорядоченные выборки? С повторениями или без повторений?
Множество \(A\) - это клетки шахматной доски. Выбираем две разные клетки для двух разных королей (порядок важен!). Поэтому здесь упорядоченные выборки без повторений.
Выбрать клетку для чёрного короля можно 64 способами. После этого белого короля можно поставить в любую клетку, не смежную с чёрным.
Отметим в клетках число соседей.
3 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
5 |
8 |
8 |
8 |
8 |
8 |
8 |
5 |
3 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
Применяя правило сложения, рассмотрим 3 случая:
Чёрный король в углу \(\Rightarrow\) \(64 - 3 = 61\) способ поставить белого
Чёрный король с краю \(\Rightarrow\) \(64 - 5 = 59\) способов поставить белого
Чёрный король во внутренней клетке \(\Rightarrow\) \(64 - 8 = 56\) способов поставить белого
Применяя правило умножения, запишем формулу:
\(61 \cdot 4 + 59 \cdot (6 \cdot 4) + 56 \cdot 6^2 = 3676\).
Упражнение. В легковом автомобиле 5 мест (одно водительское и 4 пассажирских). Сколькими способами можно рассадить в автомобиль 5 друзей для поездки, если водительское удостоверение имеется только у троих?
Свойства биномиальных коэффициентов#
Числа \(C_n^k\) называются биномиальными коэффициентами.
Докажем следующее тождество Паскаля:
\(C_{n+1}^k = C_n^{k-1} + C_n^k\)
Требуется проверить, что
\( \dfrac{(n+1)!}{k!(n-k+1)!} = \dfrac{n!}{(k-1)!(n-k+1)!} + \dfrac{n!}{k!(n-k)!} \)
Домножив данное равенство на \(\dfrac{(k-1)!(n-k)!}{n!}\), получим
\( \dfrac{n+1}{k(n-k+1)} = \dfrac{1}{n-k+1} + \dfrac{1}{k} \)
Приводя слагаемые к общему знаменателю, убеждаемся, что это тождество.
Установленное свойство позволяет расположить все биномиальные коэффициенты в виде треугольника Паскаля.
\(C_0^0\)
\(C_1^0\) \(C_1^1\)
\(C_2^0\) \(C_2^1\) \(C_2^2\)
\(C_3^0\) \(C_3^1\) \(C_3^2\) \(C_3^3\)
\(C_4^0\) \(C_4^1\) \(C_4^2\) \(C_4^3\) \(C_4^4\)
и так далее…
\(1\)
\(1\) \(1\)
\(1\) \(2\) \(1\)
\(1\) \(3\) \(3\) \(1\)
\(1\) \(4\) \(6\) \(4\) \(1\)
В силу тождества Паскаля каждое число внутри треугольника равно сумме двух чисел над ним. В силу тождеств \(C_n^0 = C_n^n = 1\) по бокам треугольника находятся числа \(1\).
Кроме того, в силу тождества \(C_n^k = C_n^{n-k}\) каждая строка треугольника Паскаля симметрична.
Упражнение. Докажите это тождество.
Бином Ньютона#
Раскроем скобки в двучлене (биноме):
\((a + b)^n = \underbrace{(a + b)(a + b)(a + b) \ldots (a + b)}_{n\text{ раз}}\)
Получим \(2^n\) слагаемых, которые можно сгруппировать в одночлены вида \(a^k b^{n-k}\).
Каждое слагаемое похоже на двоичный кортеж с \(k\) единицами и \((n-k)\) нулями. Всего таких различных кортежей \(C_n^k\). Поэтому перед одночленом \(a^k b^{n-k}\) надо поставить коэффициент \(C_n^k\).
\((a + b)^n = \sum\limits_{k=0}^n C_n^k a^k b^{n-k}\)
Например,
\((a + b)^4 = C_4^0 a^4 + C_4^1 a^3b + C_4^2 a^2 b^2 + C_4^3 a b^3 + C_4^4 b^4 =\)
\(= a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4\)
Упражнение. Распишите по формуле бинома Ньютона выражение \((a + b)^5\).
Замечание. Полагая \(a = b = 1\), получаем, что сумма биномиальных коэффициентов в каждой строке треугольника Паскаля - это степень двойки.
Это же свойство можно доказать из комбинаторных соображений (как?).
Полагая \(a = 1\), \(b = -1\), получаем, что знакопеременная сумма биномиальных коэффициентов в \(n\)-й строчке треугольника Паскаля (при \(n > 0\)) равна \(0\).
Формула включений и исключений#
См. Вялый и др. - Лекции по дискретной математике
Доказательство формулы включений и исключений через характеристические функции множеств.
Числа Стирлинга второго рода#
См. Виленкин “Комбинаторика”