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

В комбинаторике биективное доказательство - это метод доказательства, который находит биективное функция (то есть взаимно однозначное и на функцию ) f: A → B между двумя конечными наборами A и B, или сохраняющая размер биективная функция между двумя комбинаторными классами , тем самым доказывая, что они имеют одинаковое количество элементов, | A | = | B |. Единственное место, где эта техника полезна, - это когда мы хотим узнать размер A, но не можем найти прямого способа подсчета его элементов. Установление биекции от A к некоторому B решает проблему, если B более легко счетно. Еще одна полезная особенность этой техники заключается в том, что сама природа взаимного однозначного соответствия часто дает мощное понимание каждого или обоих наборов.

• 1 Основные примеры
  • 1.1 Доказательство симметрии биномиальных коэффициентов
    • 1.1.1 Биективное доказательство
• 2 Другие примеры
• 3 См. Также
• 4 Ссылки
• 5 Дополнительная литература
• 6 Внешние ссылки

Доказательство симметрии биномиальных коэффициентов

Симметрия биномиальных коэффициентов утверждает, что

$(nk)\; =\; (nn\; -\; к).\; \{\backslash \; displaystyle\; \{n\; \backslash \; choose\; k\}\; =\; \{n\; \backslash \; choose\; nk\}.\}$

Это означает, что существует ровно столько комбинаций из k элементов в наборе размера n, сколько и комбинаций n - k вещей в наборе размера n.

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

Ключевая идея доказательства может быть понята на простом примере: выбор из группы из n детей, которых k наградить рожками мороженого, имеет точно такой же эффект. как выбор вместо этого n - k детей, которым будет отказано.

Говоря более абстрактно и в общем, две величины, заявленные как равные, учитывают подмножества размера k и n - k, соответственно, любого n-элементного множества S. Пусть A будет множеством всех k-элементных подмножеств S множество A имеет размер $(nk).\; \{\backslash \; displaystyle\; \{\backslash \; tbinom\; \{n\}\; \{k\}\}.\}$Пусть B будет набором всех n − k подмножеств S, набор B имеет размер $(nn\; -\; k)\; \{\backslash \; displaystyle\; \{\backslash \; tbinom\; \{n\}\; \{nk\}\}\}$. Между двумя наборами A и B существует простое взаимно однозначное соответствие: оно связывает каждое k-элементное подмножество (то есть член A) с его дополнением, которое содержит в точности оставшиеся n - k элементов S, и, следовательно, является членом B. Более формально это может быть записано с использованием функциональной нотации как, f: A → B, определенное формулой f (X) = X для X любого k-элементного подмножества S и дополнение, взятое в S. Чтобы показать, что f является биекцией, сначала предположим, что f (X 1) = f (X 2), то есть X 1 = X 2. Возьмите дополнения каждой стороны (в S), используя тот факт, что дополнение дополнения набора является исходным набором, чтобы получить X 1 = X 2. Это показывает, что f однозначно. Теперь возьмем любое n − k-элементное подмножество S в B, скажем Y. Его дополнение в S, Y, является k-элементным подмножеством, а значит, элементом A. Поскольку f (Y) = (Y) = Y, f также является на и, следовательно, биекцией. Результат следует из того, что существование взаимно однозначного соответствия между этими конечными множествами показывает, что они имеют одинаковый размер, то есть $(nk)\; =\; (nn\; -\; k)\; \{\backslash \; displaystyle\; \{\backslash \; tbinom\; \{n\}\; \{k\}\}\; =\; \{\backslash \; tbinom\; \{n\}\; \{nk\}\}\}$.

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

Наиболее классические примеры биективного Доказательства в комбинаторике включают:

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

• Биномиальная теорема
• Теорема Шредера – Бернштейна
• Двойная подсчет (техника доказательства)
• Комбинаторные принципы
• Комбинаторное доказательство
• Категоризация

• Loehr, Nicholas A. (2011). Биективная комбинаторика. CRC Press. ISBN 143984884X, ISBN 978-1439848845.

• «Деление на три» - по Дойлу и Конвей.
• «Прямое биективное доказательство формулы длины крюка» - Новелли, Пак и Стояновский.
• «Биективная перепись и случайная генерация эйлеровых плоских карт с заданными степени вершин " - Жиль Шеффер.
• " Конструктивное доказательство унимодальности гауссовских многочленов Кэти О'Хара " - Дорон Зейлбергер.
• " Разделение биекций, обзор " - от Игоря Пак.
• Принцип инволюции Гарсиа-Милна - из MathWorld.