Русская Википедия:Биективное доказательство
Биективное доказательство — это техника доказательства, при которой находится биективная функция f : A → B между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя Шаблон:Не переведено 5, чем доказывается одинаковость числа элементов, |A| = |B|. Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств.
Базовые примеры
Доказательство симметрии биномиальных коэффициентов
Симметрия биномиальных коэффициентов утверждает, что
- <math> {n \choose k} = {n \choose n-k}. </math>
Это означает, что имеется точно столько же комбинаций k элементов из множества, содержащего n элементов, как и комбинаций n − k элементов.
Биективное доказательство
Заметим, что две величины, для которых мы доказываем равенство, подсчитывают число подможеств размера k и n − k соответственно любого n-элементного множества S. Существует простая биекция между двумя семействами Fk и Fn − k подмножеств S — она связывает каждое k-элементное подмножество с его дополнением, которое содержит в точности оставшиеся n − k элементов множества S. Поскольку Fk и Fn − k имеют одинаковое число элементов, соответствующие биномиальные коэффициенты должны быть равны.
Рекуррентное отношение треугольника Паскаля
- <math> {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}</math> для <math>1 \le k \le n - 1. </math>
Биективное доказательство
Доказательство. Мы считаем число способов выбрать k элементов из n-элементного множества. Снова, по определению, левая часть равенства равна числу способов выбора k элементов из n. Поскольку 1 ≤ k ≤ n − 1, мы можем фиксировать элемент e из n-элементного множества, так что оставшееся подмножество не пусто. Для каждого k-элементного множества, если e выбрано, существует
- <math>{n-1 \choose k-1}</math>
способов выбора оставшихся k − 1 элементов среди оставшихся n − 1 возможностей. В противном случае имеется
- <math>{n-1 \choose k}</math>
способов выбора оставшихся k элементов среди оставшихся n − 1 возможностей. Тогда есть
- <math>{n-1 \choose k-1} + {n-1 \choose k}</math>
способов выбора k элементов.<math>\Box</math>
Другие примеры
Задачи, позволяющие комбинаторное доказательство, не ограничены биномиальными коэффициентами. По мере возрастания сложности задачи комбинаторное доказательство становится всё более изощрённым. Техника биективного доказательства полезно в областях дискретной математики, таких как комбинаторика, теория графов и теория чисел.
Наиболее классические примеры биективных доказательств в комбинаторике:
- Код Прюфера, дающий доказательство формулы Кэли для числа помеченных деревьев.
- Алгоритм Робинсона — Шенстеда, дающий доказательство формулы Бёрнсайда для симметрической группы.
- Сопряжение диаграмм Юнга, дающее доказательство классического результата о числе некоторых разбиений целых чисел.
- Биективные доказательства Шаблон:Не переведено 5.
- Биективные доказательства формулы для чисел Каталана.
См. также
- Бином Ньютона
- Теорема Кантора — Бернштейна
- Двойной подсчёт (техника доказательства)
- Комбинаторные принципы
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
Примечания
Литература
Ссылки
- "Division by three" – by Doyle and Conway.
- "A direct bijective proof of the hook-length formula" – by Novelli, Pak and Stoyanovsky.
- "Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees" – by Gilles Schaeffer.
- "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – by Doron Zeilberger.
- "Partition Bijections, a Survey" – by Igor Pak.
- Garsia-Milne Involution Principle – from MathWorld.
