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

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

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

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

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

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

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

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

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

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

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

Обычно, согласно этому принципу, если A ₁ ,…, A _n - конечные множества, то

${\ displaystyle {\ begin {align} \ 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 {выравнивается}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение повторения

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

Рекомендации

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