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

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

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

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

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

Правило произведения — еще один интуитивный принцип, гласящий, что если существует a способов сделать что-то и b способов сделать что-то другое, то существует a  ·  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{align}}}$

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

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

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

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

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

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

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

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

• van Lint, JH; Wilson, RM (2001). Курс комбинаторики (2-е изд.). Cambridge University Press. ISBN 0-521-00601-5.