Комбинаторные принципы (TkbQnugmkjudy hjnuenhd)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$|A\cup B|=|A|+|B|-|A\cap B|$

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

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

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

${\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}}$

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

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

Основная статья: Правило деления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. — М.: МЦНМО, 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.