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

История комбинаторики как самостоятельной дисциплины уходит корнями в античность: правила сложения и умножения неявно использовались уже в античных задачах на переборы. Явную комбинаторную форму они получили в XVII веке вместе с треугольником Паскаля^[6] и работами Г. В. Лейбница^[7] и Я. Бернулли^[8].

Формулу включений — исключений в вероятностной оболочке дал А. де Муавр в «The Doctrine of Chances» (1718)^[9]; теоретико-множественную редакцию связывают с Ж. Ж. да Силвой (1854)^[10] и Дж. Дж. Сильвестром (1883)^[11]. Производящие функции систематически применял Л. Эйлер^[12]; в XX веке метод был кодифицирован в монографии «generatingfunctionology» Г. Уилфа^[13].

Принцип ящиков Дирихле (1834)^[14] стал стандартным инструментом доказательства существования. Биективная комбинаторика как программа — явно строить соответствия, а не только сравнивать формулы — сложилась во второй половине XX века, в том числе в трудах Р. Стенли^[15]. Приёмы двойного счёта и «выделенного элемента» — старые школьные методы, возведённые в ранг полноценного инструмента в современных курсах дискретной математики.

Если объект можно выбрать либо ${\displaystyle a}$ способами либо ${\displaystyle b}$ способами, и эти семейства способов не пересекаются, то всего ${\displaystyle a+b}$ способов^[16][17][18]. На языке множеств: для конечных непересекающихся ${\displaystyle A}$ и ${\displaystyle B}$

${\displaystyle A\cap B=\varnothing \;\Longrightarrow \;|A\cup B|=|A|+|B|,}$

где ${\displaystyle |A|}$ — число элементов конечного множества ${\displaystyle A}$ (а не множества «${\displaystyle |A|}$»). Для конечного семейства попарно непересекающихся множеств мощности складываются.

Смешение с языком теории вероятностей («событие ${\displaystyle A}$ имеет ${\displaystyle a}$ исходов») не обязательно: речь о разбиении множества объектов на несовместные случаи.

Пример. Сколько трёхзначных чисел в десятичной записи содержат ровно две цифры 9. Три непересекающихся формата:

• ${\displaystyle 9n9}$, ${\displaystyle n=0,1,\dots ,8}$ (иначе три девятки) — 9 чисел;
• ${\displaystyle 99n}$, ${\displaystyle n=0,1,\dots ,8}$ — 9 чисел;
• ${\displaystyle n99}$, ${\displaystyle n=1,\dots ,8}$ (нуль сделал бы запись двузначной) — 8 чисел.

Итого ${\displaystyle 9+9+8=26}$.

Если объект строится за два шага, причём первый шаг выполняется ${\displaystyle a}$ способами, а второй — ${\displaystyle b}$ способами при любом исходе первого, то всего ${\displaystyle ab}$ способов^[19][20]. Это мощность декартова произведения ${\displaystyle |A\times B|=|A|\,|B|}$. Условие «при любом исходе первого шага число продолжений одно и то же» существенно: если оно зависит от предыдущего выбора, простое произведение неприменимо (нужно суммировать по ветвям).

Пример. Трёхзначные десятичные числа: первая цифра — 9 вариантов (${\displaystyle 1,\dots ,9}$), вторая и третья — по 10 (${\displaystyle 0,\dots ,9}$). Всего ${\displaystyle 9\cdot 10\cdot 10=900}$.

Распространённый контрпример двусмысленности: «6 красных, 8 синих и 10 зелёных кубиков разложить в два ящика». Если кубики одного цвета неразличимы, а ящики различимы, красные дают 7 распределений (${\displaystyle 0+6,\dots ,6+0}$), синие — 9, зелёные — 11, и по правилу умножения ${\displaystyle 7\cdot 9\cdot 11=693}$ способов. Если же все кубики различимы, каждый независимо попадает в один из двух ящиков, и ответ ${\displaystyle 2^{24}}$. Без оговорки о неразличимости пример некорректен.

Правило сложения требует непересечения. Если множества пересекаются, элементы пересечения посчитаны дважды, и их нужно вычесть^[21][22][3]:

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.}$

Для трёх множеств

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.}$

В общем виде для конечных ${\displaystyle A_{1},\dots ,A_{n}}$

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{i}|A_{i}|-\sum _{i<j}|A_{i}\cap A_{j}|+\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}|A_{1}\cap \cdots \cap A_{n}|.}$

Знак определяется чётностью числа пересекаемых множеств. Формула обобщает правило суммы и восходит к А. де Муавру (1718); в XIX веке её разрабатывали Д. да Силва и Дж. Дж. Сильвестр^[23].

Пример. В группе 40 туристов: английский знают 20, французский — 15, испанский — 11; английский и французский — 7, английский и испанский — 5, французский и испанский — 3; все три языка — 2. Число владеющих хотя бы одним языком

${\displaystyle 20+15+11-7-5-3+2=33,}$

следовательно, ${\displaystyle 40-33=7}$ не знают ни одного из трёх. Числа пересечений согласованы: ${\displaystyle 7,5,3\geq 2}$.

Если процедура порождает ${\displaystyle n}$ помеченных исходов, причём каждый различимый результат представлен ровно ${\displaystyle d}$ пометками, то различных результатов ${\displaystyle n/d}$ (предполагается, что ${\displaystyle d}$ делит ${\displaystyle n}$)^[15].

Эквивалентные формулировки:

• если конечное ${\displaystyle A}$ разбито на ${\displaystyle n}$ равномощных классов по ${\displaystyle d}$ элементов, то ${\displaystyle n=|A|/d}$;
• если сюръекция ${\displaystyle f\colon A\to B}$ имеет все слои мощности ${\displaystyle d}$, то ${\displaystyle |B|=|A|/d}$.

Формулировка «для каждого способа есть ${\displaystyle d-1}$ неразличимых с ним результата» имеет в виду остальные представители того же класса (всего в классе ${\displaystyle d}$ штук, включая исходный)^[24].

Пример. Рассадить четырёх различимых людей за круглый стол; рассадки, получающиеся вращением, отождествляются, отражения — нет (левый и правый сосед различны). Линейных рассадок ${\displaystyle 4!=24}$; у каждого класса ровно 4 вращения, поэтому различных ${\displaystyle 24/4=(4-1)!=6}$. В общем случае ${\displaystyle n}$ людей дают ${\displaystyle (n-1)!}$ циклических расстановок.

Принцип Дирихле (также известный как принцип ящиков или голубятни) — это фундаментальный комбинаторный принцип, который утверждает, что если больше объектов размещается в меньшем количестве контейнеров, то хотя бы один контейнер должен содержать более одного объекта^[25][26][27].

Принцип инварианта заключается в поиске величины или свойства, которое не меняется при допустимых преобразованиях системы. Если начальное и целевое состояния имеют разные значения этого инварианта, переход между ними невозможен^[28].

Пример. На доске выписаны числа ${\displaystyle 1,2,\dots ,2n}$. Разрешается стереть любые два числа ${\displaystyle a}$ и ${\displaystyle b}$ и записать вместо них ${\displaystyle |a-b|}$. Можно ли получить в итоге одно число ${\displaystyle 0}$ при нечётном ${\displaystyle n}$? Сумма всех чисел на доске изначально равна ${\displaystyle n(2n+1)}$, что при нечётном ${\displaystyle n}$ является нечётным числом. Замена ${\displaystyle a,b}$ на ${\displaystyle |a-b|}$ изменяет общую сумму на ${\displaystyle a+b-|a-b|=2\min(a,b)}$, то есть на чётное число. Следовательно, чётность суммы (инвариант) сохраняется. Ноль имеет чётную сумму, поэтому получить его из нечётной суммы невозможно.

Принцип крайнего (или принцип экстремума) предполагает рассмотрение элемента множества, обладающего максимальным или минимальным значением некоторой характеристики (например, наибольший угол, кратчайший путь, вершина графа максимальной степени). Анализ свойств этого «крайнего» элемента часто приводит к доказательству требуемого утверждения или к противоречию^[29].

Пример. В любом конечном ориентированном ациклическом графе (DAG) существует хотя бы одна вершина с нулевой полустепенью исхода (сток) и хотя бы одна с нулевой полустепенью захода (исток). Доказательство: рассмотрим самый длинный простой путь в графе. Его конечная вершина не может иметь исходящих рёбер, иначе путь можно было бы продолжить, что противоречит его максимальности (принцип крайнего).

Чтобы установить ${\displaystyle |A|=|B|}$ для конечных множеств, достаточно построить биекцию ${\displaystyle A\to B}$. Приём особенно полезен, когда одну мощность считать легче, чем другую, или когда прямое вычисление одной из них требует сложных алгебраических выкладок^[15][30].

Пример (симметрия биномиальных коэффициентов). Пусть ${\displaystyle A}$ — множество всех ${\displaystyle k}$-элементных подмножеств ${\displaystyle n}$-элементного множества ${\displaystyle X}$, а ${\displaystyle B}$ — множество всех его ${\displaystyle (n-k)}$-элементных подмножеств. Сопоставим каждому подмножеству ${\displaystyle S\in A}$ его дополнение ${\displaystyle X\setminus S}$. Очевидно, что дополнение ${\displaystyle k}$-элементного множества состоит ровно из ${\displaystyle n-k}$ элементов, и операция взятия дополнения обратима (является инволюцией). Таким образом, мы построили естественную биекцию между ${\displaystyle A}$ и ${\displaystyle B}$, что без всяких алгебраических преобразований доказывает равенство ${\displaystyle |A|=|B|}$, то есть ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$.

Пример (двоичные строки и подмножества). Пусть ${\displaystyle A}$ — множество всех подмножеств ${\displaystyle n}$-элементного множества ${\displaystyle X}$. Если группировать подмножества по их размеру, то мощность ${\displaystyle |A|}$ выражается суммой ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}}$. С другой стороны, каждому подмножеству ${\displaystyle S\subseteq X}$ можно поставить в соответствие его характеристический вектор — двоичную строку длины ${\displaystyle n}$, в которой на ${\displaystyle i}$-й позиции стоит 1, если ${\displaystyle i}$-й элемент входит в ${\displaystyle S}$, и 0 в противном случае. Множество ${\displaystyle B}$ всех таких двоичных строк имеет очевидную мощность ${\displaystyle 2^{n}}$. Построенная биекция между ${\displaystyle A}$ и ${\displaystyle B}$ мгновенно доказывает фундаментальное тождество ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}}$.

Одно и то же конечное множество считают двумя способами; полученные выражения равны. Так получают комбинаторные тождества^[31].

Простейший пример: клетки прямоугольника ${\displaystyle 3\times 5}$ можно сгруппировать по строкам (${\displaystyle 3\cdot 5}$) или по столбцам (${\displaystyle 5\cdot 3}$). Отсюда коммутативность умножения натуральных чисел — арифметический факт, а не свойство коммутативного кольца как алгебраической структуры.

В множестве фиксируют один элемент и разбивают конфигурации на те, что его содержат, и те, что не содержат. Часто это частный случай биекции на дизъюнктное объединение и одновременно двойного счёта^[32].

Пример (правило Паскаля). Пусть ${\displaystyle [n]=\{1,2,\dots ,n\}}$ (не отрезок вещественной прямой и не ${\displaystyle \mathbb {R} _{n}}$). Число ${\displaystyle (k+1)}$-элементных подмножеств множества ${\displaystyle [n+1]}$ равно ${\displaystyle C_{n+1}^{k+1}}$. Выделим элемент ${\displaystyle n+1}$:

• подмножества, его не содержащие, — это ${\displaystyle (k+1)}$-подмножества ${\displaystyle [n]}$, их ${\displaystyle C_{n}^{k+1}}$;
• содержащие его — после удаления ${\displaystyle n+1}$ остаются ${\displaystyle k}$-подмножества ${\displaystyle [n]}$, их ${\displaystyle C_{n}^{k}}$.

Классы не пересекаются и покрывают все ${\displaystyle (k+1)}$-подмножества, поэтому

${\displaystyle C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k}}$

при ${\displaystyle 0\leq k\leq n}$ (с соглашением ${\displaystyle C_{n}^{n+1}=0}$, ${\displaystyle C_{n}^{-1}=0}$). Тождество есть и биекция с дизъюнктным объединением, и применение выделенного элемента.

Обыкновенная производящая функция последовательности ${\displaystyle (a_{n})_{n=0}^{\infty }}$ — степенной ряд

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

Индексация начинается с ${\displaystyle n=0}$: записывать ${\displaystyle \{a_{1},a_{2},\dots \}}$ и суммировать с нуля нельзя без оговорки ${\displaystyle a_{0}}$. Коэффициенты кодируют комбинаторные количества; алгебра рядов переводит свёртки, сдвиги и рекурсии в уравнения на ${\displaystyle G}$. Пример: ${\displaystyle (1+x)^{n}=\sum _{k}C_{n}^{k}x^{k}}$.

Помимо обыкновенных, широко применяются экспоненциальные производящие функции вида ${\displaystyle \sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$. Они являются основным инструментом для перечисления помеченных (labelled) структур (где элементы различимы, например, графы с пронумерованными вершинами), в то время как обыкновенные производящие функции естественным образом работают с непомеченными (unlabelled) структурами^[33].

Рекуррентное соотношение выражает член последовательности через предыдущие (и фиксирует начальные данные)^[15]. Классический пример — числа Фибоначчи ${\displaystyle F_{0}=0}$, ${\displaystyle F_{1}=1}$, ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ при ${\displaystyle n\geq 2}$.

Рекуррентность может открыть новые свойства, но обычно ищут явную (замкнутую) формулу; калька «закрытая форма» с англ. closed form в русском языке нестандартна^[34][35].

Частный, но исключительно мощный случай биективного доказательства. Используется для подсчёта путей на решётке, удовлетворяющих определённым ограничениям (например, не пересекающих главную диагональ). Неудачные (пересекающие барьер) пути биективно отображаются в множество всех путей между другими, более простыми для подсчёта точками, путём отражения части траектории относительно барьера. Классическое применение — вывод формулы для чисел Каталана и решение задачи о баллотировке^[15].

Сложение. Числа от 1 до 100, делящиеся на 2 или на 5, но не на оба сразу: чётных 50, кратных 5 — 20, кратных 10 — 10, значит ${\displaystyle 50+20-10=60}$ делятся хотя бы на одно, из них делятся ровно на одно из этих чисел (но не на оба сразу): ${\displaystyle 60-10=50}$. Здесь уже нужна формула включений — исключений, а не голое сложение.

Умножение. Пароль из 4 символов: первая позиция — буква из 26, остальные — цифра из 10. Итого ${\displaystyle 26\cdot 10^{3}=26000}$, если регистр не различается.

Включения — исключения, беспорядки. Число перестановок без неподвижных точек порядка ${\displaystyle n}$

${\displaystyle n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

получается, если из ${\displaystyle n!}$ вычесть те, что фиксируют хотя бы одну точку^[3].

Деление. Ожерелье из 3 разных бусин с учётом вращений, но без отражений: ${\displaystyle 3!/3=2}$.

Дирихле. Среди любых 367 человек хотя бы двое имеют общий день рождения (366 возможных дат с 29 февраля).

Двойной счёт. Сумма степеней вершин графа равна удвоенному числу рёбер (каждая дуга учитывается с двух концов) — лемма о рукопожатиях.

• Перечислительная комбинаторика — подсчёт слов, деревьев, разбиений, графов; правила сложения и умножения — каркас, формула включений — исключений — учёт ограничений^[15].
• Теория чисел. Функция Эйлера ${\displaystyle \varphi (n)}$ считается включением — исключением по простым делителям ${\displaystyle n}$; принцип Дирихле — в диофантовых приближениях.
• Теория вероятностей. Равновероятное пространство сводит вероятности к мощностям; та же формула включений — исключений для вероятностей объединения.
• Информатика. Хеширование и коллизии — принцип Дирихле; оценка числа состояний автомата, паролей, маршрутов — правила произведения; анализ рекурсивных алгоритмов — рекуррентности и производящие функции.
• Теория кодирования и Рамсея. Существование повторяющихся конфигураций и монохроматических подструктур — усиления принципа Дирихле.