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

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

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

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

Шаблон:Main Интуитивно правило сложения утверждает, что если событие A имеет $a$ возможных исходов, а событие B имеет $b$ возможных исходов, причём только одно из этих событий может произойти, то общее число возможных результатов равноШаблон:Sfn $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.$

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

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

ПримерШаблон:Sfn. Имеется 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$ способа.

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

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

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

$|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{array}{cc}\left|\bigcup _{i=1}^n{A}_i\right|& =\sum _{i=1}^n\left|A_i\right|-\sum _{i,j:1\le i<j\le n}|A_i\cap A_j|\\ & +\sum _{i,j,k:1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots +{(-1)}^{n-1}|A_1\cap \cdots \cap A_n|.\end{array}$

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

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

Шаблон:Main Комбинаторное определение: если задача решается с помощью процедуры, которая может быть выполнена $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$ различных способа.

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

Шаблон:Main Принцип Дирихле в комбинаторике в простейшей формулировке гласит, что если $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,$ и, следовательно, по крайней мере один ящик соответствует двум или более людям. Шаблон:ЧТД

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

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

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

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

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

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

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

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

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

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

Шаблон:Main Производящая функция последовательности $\{a_1,a_2,a_3\dots \}$ — это степенной ряд, коэффициенты которых соответствуют членам заданной последовательности.

$G(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n.$

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• J. H. van Lint, R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. Шаблон:ISBN.

Ссылки

• Шаблон:Cite web