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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как правило, согласно этому принципу, если А₁, ..., А_п конечные множества, то

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

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

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

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

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

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

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

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

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

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

Принцип голубятни

Основная статья: Принцип голубятни

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

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

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

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

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

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

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

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

Отношение рецидива

Основная статья: Отношение рецидива

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

использованная литература

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