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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Мазур, Дэвид Р. (2010), Комбинаторика / Экскурсия, Математическая ассоциация Америки, стр. 28, ISBN  978-0-88385-762-5

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

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

внешняя ссылка

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