Меню Главная Случайная статья Настройки Биективное доказательство Материал из https://ru.wikipedia.org Биективное доказательство — это техника доказательства, при которой находится биективная функция f : A B между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя комбинаторными классами[англ.], чем доказывается одинаковость числа элементов, |A| = |B|. Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств. Содержание 1 Базовые примеры 1.1 Доказательство симметрии биномиальных коэффициентов 1.1.1 Биективное доказательство 1.2 Рекуррентное отношение треугольника Паскаля 1.2.1 Биективное доказательство 2 Другие примеры 3 См. также 4 Примечания 5 Литература 6 Ссылки Базовые примеры Доказательство симметрии биномиальных коэффициентов Симметрия биномиальных коэффициентов утверждает, что ${\displaystyle {n \choose k}={n \choose n-k}.}$ Это означает, что имеется точно столько же комбинаций k элементов из множества, содержащего n элементов, как и комбинаций n  k элементов. Заметим, что две величины, для которых мы доказываем равенство, подсчитывают число подмножеств размера k и n  k соответственно любого n-элементного множества S. Существует простая биекция между двумя семействами Fk и Fn  k подмножеств S — она связывает каждое k-элементное подмножество с его дополнением, которое содержит в точности оставшиеся n  k элементов множества S. Поскольку Fk и Fn  k имеют одинаковое число элементов, соответствующие биномиальные коэффициенты должны быть равны. Рекуррентное отношение треугольника Паскаля ${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$ для ${\displaystyle 1\leq k\leq n-1.}$ Доказательство. Мы считаем число способов выбрать k элементов из n-элементного множества. Снова, по определению, левая часть равенства равна числу способов выбора k элементов из n. Поскольку 1 k n 1, мы можем фиксировать элемент e из n-элементного множества, так что оставшееся подмножество не пусто. Для каждого k-элементного множества, если e выбрано, существует ${\displaystyle {n-1 \choose k-1}}$ способов выбора оставшихся k  1 элементов среди оставшихся n  1 возможностей. В противном случае имеется ${\displaystyle {n-1 \choose k}}$ способов выбора оставшихся k элементов среди оставшихся n 1 возможностей. Тогда есть ${\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}$ способов выбора k элементов.${\displaystyle \Box }$ Другие примеры Задачи, позволяющие комбинаторное доказательство, не ограничены биномиальными коэффициентами. По мере возрастания сложности задачи комбинаторное доказательство становится всё более изощрённым. Техника биективного доказательства полезно в областях дискретной математики, таких как комбинаторика, теория графов и теория чисел. Наиболее классические примеры биективных доказательств в комбинаторике: Код Прюфера, дающий доказательство формулы Кэли для числа помеченных деревьев. Алгоритм Робинсона — Шенстеда, дающий доказательство формулы Бёрнсайда для симметрической группы. Сопряжение диаграмм Юнга, дающее доказательство классического результата о числе некоторых разбиений целых чисел. Биективные доказательства теоремы о пятиугольных числах[англ.]. Биективные доказательства формулы для чисел Каталана. См. также Бином Ньютона Теорема Кантора — Бернштейна Двойной подсчёт Комбинаторные принципы Примечания Литература Nicholas A. Loehr. Bijective Combinatorics. — CRC Press, 2011. — ISBN 978-1439848845. — [Архивировано 23 октября 2015 года.] Ссылки "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.