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

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

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

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

Правило суммы

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

Правило суммы — это интуитивный принцип, гласящий, что если существуют возможные исходы события (или способов сделать что-то) и b возможных исходов другого события (или способов сделать другое дело), ​​то эти два события не могут произойти одновременно ( или обе вещи не могут быть выполнены одновременно), тогда существует a + b всех возможных результатов для событий (или всего возможных способов сделать одну из вещей). Более формально, сумма размеров двух непересекающихся множеств равна размеру их объединения.

Правило продукта

Основная статья: Правило продукта

Правило продукта — еще один интуитивный принцип, гласящий, что если есть сделать одно и b способов сделать другое, то существует · способы b способов сделать оба дела.

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

Включение-исключение проиллюстрировано для трех наборов

Основная статья: Принцип включения-исключения

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

Вообще говоря, согласно этому принципу, если A ₁ , …, An _то конечные множества,

${\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\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}}$

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

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

Правило деления гласит, что существует n/d способов выполнить задачу, если ее можно выполнить с помощью процедуры, которую можно выполнить n способами, и для каждого способа w ровно d из n способов соответствует способу w .

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

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

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

Двойной счет

Основная статья: Двойной счет (техника доказательства)

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

Принцип «ячейки»

Основная статья: Принцип ячейки

Принцип «ячейки» гласит, что если каждый предмет помещен в одну из b коробок, где a > b , то одна из коробок содержит более одного предмета. Используя это, можно, например, продемонстрировать существование некоторого элемента в наборе с некоторыми конкретными свойствами.

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

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

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

Генерирующая функция

Основная статья: Генерирующая функция

Производящие функции можно рассматривать как многочлены с бесконечным числом членов, коэффициенты которых соответствуют членам последовательности. Это новое представление последовательности открывает новые методы поиска тождеств и замкнутых форм, относящихся к определенным последовательностям. (Обычная) производящая функция последовательности a _n равна

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

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

Основная статья: Рекуррентное соотношение

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

Ссылки

• ван Линт, Дж. Х.; Уилсон, Р.М. (2001). Курс комбинаторики (2-е изд.). Издательство Кембриджского университета. ISBN  0-521-00601-5 .