Комбинаторные принципы

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

• Правило сложения, правило умножения и принцип включения-исключения часто используются для целей перечисления.
• Принцип Дирихле часто устанавливает существование чего-либо или используется для определения минимального либо максимального количества чего-либо в дискретном контексте.
• Биективное доказательство используется, чтобы убедиться, что два множества имеют одинаковое количество элементов.
• Многие комбинаторные тождества возникают из метода двойного счёта^[англ.] или метода выделенного элемента^[англ.].
• Производящие функции и рекуррентные соотношения — мощные инструменты, которые можно использовать для управления последовательностями, и они могут быть полезны при исследовании многих комбинаторных ситуаций.

Правило сложения

Основная статья: Правило сложения (комбинаторика)

Интуитивно правило сложения утверждает, что если событие A имеет ${\displaystyle a}$ возможных исходов, а событие B имеет ${\displaystyle b}$ возможных исходов, причём только одно из этих событий может произойти, то общее число возможных результатов равно[1] ${\displaystyle a+b}$.

На языке теории множеств это правило означает, что размер объединения двух непересекающихся множеств равен сумме размеров этих множеств: если ${\displaystyle A\cap B=\varnothing }$, то ${\displaystyle |A\cup B|=|A|+|B|}$ (здесь и далее символ ${\displaystyle |A|}$ обозначает число элементов конечного множества ${\displaystyle |A|}$).

Пример. Выясним, сколько трёхзначных чисел содержат (в десятичной записи) ровно две девятки. Возможны три формата таких чисел[2]:

${\displaystyle 9n9,n=0,1,2,\dots ,8.}$ Всего 9 вариантов.

${\displaystyle 99n,n=0,1,2,\dots ,8.}$ Всего 9 вариантов.

${\displaystyle n99,n=1,2,3,\dots ,8.}$ Всего 8 вариантов.

Согласно правилу сложения, всего таких чисел будет ${\displaystyle 9+9+8=26.}$

Правило умножения

Основная статья: Правило умножения

Правило умножения — ещё один интуитивный принцип, утверждающий, что если есть ${\displaystyle a}$ способов сделать что-то и ${\displaystyle b}$ способов независимо сделать что-то другое, то существует ${\displaystyle ab}$ способов сделать и то, и другое[1].

Пример[3]. Имеется 6 красных, 8 синих и 10 зеленых кубиков. Выясним, сколькими способами они могут быть разложены в два ящика. Красные кубики можно распределить по двум ящикам так:

${\displaystyle 0+6;1+5;2+4;3+3;4+2;5+1;6+0.}$ Всего 7 вариантов.

Аналогично и независимо синие кубики дают 9 вариантов, зелёные — 11. По правилу умножения общее число вариантов равно ${\displaystyle 7\cdot 9\cdot 11=693}$ способа.

Включение – исключение для трёх множеств

Принцип включения-исключения

Основная статья: Формула включений-исключений

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

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

Эта формула обобщает приведённое выше правило суммы. Вариант для трёх множеств:

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$

В общем случае принцип утверждает[4]: если ${\displaystyle A_{1}\dots A_{n}}$ — конечные множества, то:

${\displaystyle {\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

Пример[5]. В группе 40 туристов. Из них 20 человек говорят по-английски, 15 — по-французски, 11 — по-испански. Английский и французский знают семь человек, английский и испанский — пятеро, французский и испанский — трое. Два туриста говорят на всех трёх языках. Сколько человек группы не знают ни одного из этих языков? Подсчитаем по формуле включений-исключений общее число туристов, знающих хотя бы один из упомянутых языков: ${\displaystyle 20+15+11-7-5-3+2=33.}$ Следовательно, ответ: ${\displaystyle 40-33=7.}$

Правило деления

Основная статья: Правило деления^[англ.]

Комбинаторное определение: если задача решается с помощью процедуры, которая может быть выполнена ${\displaystyle n}$ способами, причём для каждого способа существуют ${\displaystyle d-1}$ неразличимых с ним результата, то всего существуют ${\displaystyle n/d}$ различных способов выполнить задачу.

На языке теории множеств: если конечное множество ${\displaystyle A}$ является объединением ${\displaystyle n}$ попарно непересекающихся подмножеств, каждое из которых содержит ${\displaystyle d}$ элементов, то ${\displaystyle n=|A|/d.}$

На языке функций: если функция ${\displaystyle f}$ отображает конечное множество ${\displaystyle A}$ на конечное множество ${\displaystyle B,}$ причём прообраз каждого значения ${\displaystyle b\in B}$ содержит ровно ${\displaystyle d}$ значений из A, то ${\displaystyle |B|=|A|/d.}$

Пример. Сколько существует различных способов усадить четырёх человек за круглый стол? Способы считаются различными, если хотя бы у одного человека сосед слева или справа отличается. Решение: если отбросить условие, то существует ${\displaystyle 4!=24}$ способа, но каждый способ имеет 3 «двойника», отличающиеся поворотом вокруг стола, и по условию задачи все они считаются за один способ. В итоге имеем ${\displaystyle 24/4=6}$ различных способа.

Принцип Дирихле

Основная статья: Принцип Дирихле (комбинаторика)

Принцип Дирихле в комбинаторике в простейшей формулировке гласит, что если ${\displaystyle a}$ объектов разместить в ${\displaystyle b}$ ящиках, причём ${\displaystyle a>b,}$ то по крайней мере один ящик будет содержать более одного объекта[6]. С помощью этого принципа и его обобщений можно, например, продемонстрировать существование в множестве элемента с некоторыми специфическими свойствами.

Пример. Часть компании из ${\displaystyle N}$ людей ${\displaystyle (N>1)}$ обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий[7]. Доказательство. Определим ${\displaystyle N}$ «ящиков» ${\displaystyle H_{0},H_{1}\dots H_{N-1}}$ и занесём в ящик ${\displaystyle H_{k}}$ тех участников компании, которые совершили ${\displaystyle k}$ рукопожатий. Если ящик ${\displaystyle H_{0}}$ не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик ${\displaystyle H_{N-1}}$ тогда пуст, потому что число совершивших рукопожатия получается тогда меньше ${\displaystyle N.}$ Отсюда следует, что непустых ящиков всегда меньше, чем ${\displaystyle N,}$ и, следовательно, по крайней мере один ящик соответствует двум или более людям. ■

Биективное доказательство

Основная статья: Биективное доказательство

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

Пример. Докажем один из вариантов правила Паскаля: ${\displaystyle C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k},}$ где ${\displaystyle 0\leqslant k\leqslant n-1,}$ а биномиальный коэффициент ${\displaystyle C_{n}^{m}}$ одновременно характеризует число ${\displaystyle m}$-элементных подмножеств натурального интервала ${\displaystyle \mathbb {R_{n}} =\{1,2,\dots n\}}$. Сопоставим каждому ${\displaystyle (k+1)}$элементному подмножеству интервала ${\displaystyle \mathbb {R_{n+1}} }$ само это подмножество, если оно не содержит числа ${\displaystyle n+1,}$ или его же за вычетом ${\displaystyle n+1,}$ если содержит. Несложно показать, что для каждого ${\displaystyle k}$ получается биекция ${\displaystyle (k+1)}$-элементных подмножеств ${\displaystyle \mathbb {R_{n+1}} ,}$ с одной стороны, и подмножеств ${\displaystyle \mathbb {R_{n}} }$ длины ${\displaystyle k+1}$ и ${\displaystyle k}$, с другой стороны. Этот факт и отражает правило Паскаля[8].

Умножение 5 на 3 даёт тот же результат, как и умножение 3 на 5

Двойной подсчёт

Основная статья: Двойной подсчёт

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

Простейший пример (см. рисунок): подсчёт объектов в прямоугольной таблице по строкам и по столбцам приводит к одному и тому же результату, откуда следует коммутативность умножения.

Метод выделенного элемента

Основная статья: Метод выделенного элемента^[англ.]

Метод выделенного элемента отмечает некоторый «выделенный элемент» множества для доказательства нужного результата.

Производящая функция

Основная статья: Производящая функция последовательности

Производящая функция последовательности ${\displaystyle \{a_{1},a_{2},a_{3}\dots \}}$ — это степенной ряд, коэффициенты которых соответствуют членам заданной последовательности.

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$

Это представление часто позволяет применить к комбинаторным задачам мощные методы математического анализа[10].

Рекуррентное соотношение

Основная статья: Рекуррентная формула

Рекуррентное соотношение определяет каждый член последовательности, кроме начального, через предыдущие члены[11]. Пример: числа Фибоначчи.

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

Примечания

1. Окулов, 2012, с. 25.
2. Комбинаторика: правила суммы и произведения  (неопр.). Фоксфорд. Дата обращения: 21 ноября 2020. Архивировано 21 января 2021 года.
3. Окулов, 2012, с. 49, 285.
4. Окулов, 2012, с. 26—28.
5. Яковлев И. В. Формула включений и исключений  (неопр.). Дата обращения: 21 ноября 2020. Архивировано 20 октября 2019 года.
6. Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2. — С. 182.
7. Принцип Дирихле  (неопр.). Дата обращения: 30 марта 2020. Архивировано 24 сентября 2020 года.
8. Глибичук и др., 2016, с. 9—10.
9. Глибичук и др., 2016, с. 18—20.
10. Окулов, 2012, с. 90.
11. Окулов, 2012, с. 76.

Литература

• Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. — М.: МЦНМО, 2016. — 174 с. — ISBN 978-5-4439-3024-4.
• Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. — 2-е изд. — М.: БИНОМ. Лаборатория знаний, 2012. — 422 с. — (Педагогическое образование). — ISBN 978-5-9963-0893-4.
• J. H. van Lint, R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. ISBN 0-521-00601-5.

Ссылки

• Useful Identities in Combinatorics (англ.). Дата обращения: 19 ноября 2020.