Биективное доказательство - Bijective proof
В комбинаторике , Биективное доказательство является доказательством метода , который находит биективна функцию (то есть, один-к-одному , и на функцию) F : A → B между двумя конечными множествами A и B , или размером сохраняющего биективной функцией между два комбинаторные классы , тем самым доказывая, что они имеют одинаковое количество элементов, | А | = | B | . Единственное место, где эта техника полезна, - это когда мы хотим узнать размер A , но не можем найти прямого способа подсчета его элементов. Установление биекции от A к некоторому B решает проблему, если B более легко счетно. Еще одна полезная особенность этой техники заключается в том, что сама природа взаимного однозначного соответствия часто дает мощное понимание каждого или обоих наборов.
Основные примеры
Доказательство симметрии биномиальных коэффициентов
Симметрия биномиальных коэффициентов утверждает, что
Это означает, что существует ровно столько комбинаций из k вещей в наборе размера n, сколько комбинаций из n - k вещей в наборе размера n .
Биективное доказательство
Ключевая идея доказательства может быть понятна на простом примере: выбор из группы n детей, k которых наградить рожками мороженого, имеет точно такой же эффект, как и выбор n - k детей, которым будет отказано.
Более абстрактно и , как правило, эти две величины утверждали , равным считать подмножеств размера к и п - к , соответственно, любого п - элементного множества S . Пусть A - множество всех k -элементных подмножеств S , множество A имеет размер. Пусть B - множество всех n − k подмножеств S , множество B имеет размер . Между двумя наборами A и B существует простая биекция : оно связывает каждое k -элементное подмножество (то есть член A ) с его дополнением , которое содержит в точности оставшиеся n - k элементов S , и, следовательно, является членом из B . Более формально, это можно записать с помощью функционального обозначения , как, F : → B определяется F ( X ) = Х с для Х любого к -элементное подмножество S и дополнение берется в S . Чтобы показать, что f является биекцией, сначала предположим, что f ( X 1 ) = f ( X 2 ) , то есть X 1 c = X 2 c . Возьмите дополнения каждой стороны (в S ), используя тот факт, что дополнение дополнения набора является исходным набором, чтобы получить X 1 = X 2 . Это показывает , что е является один-к-одному . Теперь возьмет любой п-к элементному подмножеству S в B , скажем , Y . Его дополнение в S , Y C , является к -элементное подмножество, и так, элемент A . Поскольку f ( Y c ) = ( Y c ) c = Y , f также на и, следовательно, биекция. Результат следует из того факта, что существование биекции между этими конечными множествами показывает, что они имеют одинаковый размер, то есть .
Другие примеры
Задачи, допускающие биективные доказательства, не ограничиваются тождествами биномиальных коэффициентов. По мере увеличения сложности проблемы биективное доказательство может стать очень сложным. Этот метод особенно полезен в таких областях дискретной математики , как комбинаторика , теория графов и теория чисел .
К наиболее классическим примерам биективных доказательств в комбинаторике относятся:
- Последовательность Прюфера , дающая доказательство формулы Кэли для количества помеченных деревьев .
- Алгоритм Робинсона-Шенстеда , дающий доказательство формулы Бернсайда для симметрической группы .
- Сопряжение из диаграмм Юнга , что дает доказательство классического результата на количество определенных разбиений .
- Биективные доказательства теоремы о пятиугольном числе .
- Биективные доказательства формулы для каталонских чисел .
Смотрите также
- Биномиальная теорема
- Теорема Шредера – Бернштейна.
- Двойной счет (метод доказательства)
- Комбинаторные принципы
- Комбинаторное доказательство
- Категоризация
Ссылки
дальнейшее чтение
- Лоер, Николас А. (2011). Биективная комбинаторика . CRC Press . ISBN 143984884X , ISBN 978-1439848845 .
внешние ссылки
- «Разделение на три» - Дойл и Конвей .
- «Прямое биективное доказательство формулы длины крючка» - Новелли, Пак и Стояновский.
- «Биективная перепись и случайная генерация эйлеровых плоских карт с заданными степенями вершин» - Жиль Шеффер.
- «Конструктивное доказательство унимодальности гауссовских многочленов Кэти О'Хара» - Дорон Зейлбергер .
- «Разделение биекций, обзор» - Игорь Пак .
- Принцип инволюции Гарсиа-Милна - из MathWorld .