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

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

Основные примеры

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

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

${n \choose k}={n \choose n-k}.$

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

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

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

Более абстрактно и вообще, две величины, которые считаются равными, подсчитывают подмножества размера k и n − k соответственно любого n -элементного множества S . Пусть A — множество всех k -элементных подмножеств S , множество A имеет размер ${\tbinom {n}{k}}.$ Пусть B — множество всех n−k подмножеств S , множество B имеет размер ${\tbinom {n}{n-k}}$. существует простая биекция Между двумя множествами A и B : она связывает каждое подмножество k -элементов (то есть член A ) с его дополнением , которое содержит ровно оставшиеся n − k элементов S и, следовательно, является членом Б. ​ ​Более формально это можно записать, используя функциональные обозначения : f : A → B, определяемые формулой f ( X ) = X ^с для X любое k -элементное подмножество S и дополнение, взятое из S . Чтобы показать, что f является биекцией, сначала предположим, что f ( X ₁ ) = f ( X ₂ ) , то есть X ₁ ^с = _Х2 ^с . Возьмите дополнения каждой стороны (в S ), используя тот факт, что дополнение к множеству является исходным множеством, чтобы получить X ₁ = X ₂ . Это показывает, что f однозначно взаимно . Теперь возьмем любое n−k подмножество S в B , скажем Y. -элементное Его дополнение в S , Y ^с , является подмножеством k -элементов и, следовательно, элементом A . Поскольку f ( Y ^с ) = ( И ^с ) ^с = Y , f также является объектом и, следовательно, является биекцией. Результат теперь следует, поскольку существование биекции между этими конечными множествами показывает, что они имеют одинаковый размер, то есть ${\tbinom {n}{k}}={\tbinom {n}{n-k}}$.

Другие примеры

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

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

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

См. также

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

Дальнейшее чтение

• Лоер, Николас А. (2011). Биективная комбинаторика . ЦРК Пресс . ISBN   143984884X , ISBN   978-1439848845 .

Внешние ссылки

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