В комбинаторике биективное доказательство — это метод доказательства того, что два множества имеют одинаковое количество элементов или что множества в двух комбинаторных классах имеют одинаковый размер, путем нахождения биективной функции, которая отображает одно множество один к одному на другое. Этот метод может быть полезен как способ нахождения формулы для числа элементов определенных множеств, путем сопоставления их с другими множествами, которые легче подсчитать. Кроме того, сама природа биекции часто дает мощные идеи относительно каждого или обоих множеств.
Симметрия биномиальных коэффициентов утверждает, что
Это означает, что в наборе размера n имеется ровно столько же комбинаций из k вещей , сколько имеется комбинаций из n − k вещей в наборе размера n .
Основную идею доказательства можно понять на простом примере: выбор k детей из группы, состоящей из n детей, для вознаграждения рожками мороженого имеет точно такой же эффект, как выбор вместо этого n − k детей, которым будет отказано в рожках мороженого.
Более абстрактно и в общем, [1] две величины, которые, как утверждается, равны, подсчитывают подмножества размера k и n − k , соответственно, любого n -элементного множества S . Пусть A будет множеством всех k -элементных подмножеств S , множество A имеет размер Пусть B будет множеством всех n − k подмножеств S , множество B имеет размер . Существует простая биекция между двумя множествами A и B : она связывает каждое k -элементное подмножество (то есть элемент A ) с его дополнением , которое содержит в точности оставшиеся n − k элементов S , и, следовательно, является элементом B . Более формально, это можно записать с помощью функциональной нотации как, f : A → B , определяемое формулой f ( X ) = X c для X любого k -элементного подмножества S и дополнения, взятого в S . Чтобы показать, что f является биекцией, сначала предположим, что f ( X 1 ) = f ( X 2 ) , то есть X 1 c = X 2 c . Возьмем дополнения каждой стороны (в S ), используя тот факт, что дополнение дополнения множества является исходным множеством, чтобы получить X 1 = X 2 . Это показывает, что f является взаимно-однозначным . Теперь возьмем любое n−k -элементное подмножество S в B , скажем Y . Его дополнение в S , Y c , является k -элементным подмножеством и, таким образом, элементом A . Поскольку f ( Y c ) = ( Y c ) c = Y , f также является на и, таким образом, является биекцией. Результат теперь следует, поскольку существование биекции между этими конечными множествами показывает, что они имеют одинаковый размер, то есть,.
Проблемы, допускающие биективные доказательства, не ограничиваются тождествами биномиальных коэффициентов. По мере увеличения сложности проблемы биективное доказательство может стать очень сложным. Этот метод особенно полезен в таких областях дискретной математики, как комбинаторика , теория графов и теория чисел .
Наиболее классические примеры биективных доказательств в комбинаторике включают в себя:
