Введение
Методы, используемые в комбинаторике
При доказательстве результатов в комбинаторике обычно признаются и используются несколько полезных комбинаторных правил или принципов. Правило суммы, правило произведения и принцип включения-исключения часто применяются для задач на перечисление. Биективные доказательства используются для демонстрации того, что два множества имеют одинаковое число элементов. Принцип Дирихле часто устанавливает существование чего-либо или используется для определения минимального или максимального количества чего-либо в дискретном контексте. Многие комбинаторные тождества возникают из методов двойного счета или метода выделенного элемента. Генерирующие функции и рекуррентные соотношения являются мощными инструментами, которые можно использовать для работы с последовательностями и позволяют описывать, а иногда и решать, многие комбинаторные задачи.
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have the same number of elements. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context. Many combinatorial identities arise from double counting methods or the method of distinguished element. Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.
Правило суммы
Правило суммы - это интуитивный принцип, утверждающий, что если существуют возможные результаты для одного события (или способы сделать что-то) и b возможных результатов для другого события (или способов сделать что-то другое), и два события не могут произойти одновременно (или две вещи не могут быть сделаны одновременно), то существуют a + b возможных результатов для событий (или возможных способов сделать одну из вещей). Более формально, сумма размеров двух разрозненных множеств равна размеру их союза.
Правило продукта
Правило произведения — еще один интуитивно понятный принцип, утверждающий, что если существует a способов сделать одно, и b способов сделать другое, то существует a · b способов сделать и то, и другое.
Правило деления
Правило деления утверждает, что существует n/d способов выполнить задачу, если она может быть выполнена процедурой, которую можно осуществить n способами, и для каждого способа w ровно d из этих n способов соответствуют способу w.
Объективное доказательство
Биективные доказательства показывают, что два множества равномощны, находя биекцию (взаимно однозначное соответствие) между ними.
Двойной подсчет
Двойной подсчёт — это приём, который приравнивает два выражения, подсчитывающих мощность множества двумя различными способами.
Принцип "голубиной дыры"
Принцип голубиной ямы гласит, что если каждый из элементов помещен в один из ящиков b, где a > b, то один из ящиков содержит более одного элемента. Используя это можно, например, продемонстрировать существование какого-то элемента в множестве с некоторыми специфическими свойствами.
Метод выделенного элемента
Метод выделенного элемента выделяет "выделенный элемент" множества для доказательства некоторого результата.
Функция генерации
Генерирующие функции можно рассматривать как многочлены с бесконечным числом членов, коэффициенты которых соответствуют членам последовательности. Это новое представление последовательности открывает новые методы для нахождения тождеств и явных формул для определенных последовательностей. (Обычная) генерирующая функция последовательности an —
Отношение повторения
Рекуррентное соотношение определяет каждый член последовательности через предыдущие члены. Рекуррентные соотношения могут выявлять ранее неизвестные свойства последовательности, но, как правило, предпочтительнее формулы общего члена для членов последовательности.