Введение
Техника доказательства равенства мощности множеств
В комбинаторике биективное доказательство — это метод доказательства того, что два множества имеют одинаковое число элементов или что множества в двух комбинаторных классах имеют одинаковую мощность, путем нахождения биекции, которая устанавливает взаимно однозначное соответствие между элементами этих множеств. Этот метод может быть полезен для нахождения формулы для числа элементов определенных множеств, путем установления соответствия между ними и другими множествами, которые легче посчитать. Кроме того, сама природа биекции часто дает глубокое понимание структуры одного или обоих множеств.
In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one to one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.
Биективное доказательство
Ключевая идея доказательства может быть понята из простого примера: выбор k детей, которые будут вознаграждены мороженым, из группы n детей, имеет точно такой же эффект, как выбор вместо этого n − k детей, которым в мороженом будет отказано. Более абстрактно и в общем случае, две величины, которые утверждается равными, подсчитывают подмножества размера k и n − k, соответственно, любого множества S из n элементов. Пусть A будет множеством всех k-элементных подмножеств S, размер множества A равен. Пусть B будет множеством всех (n − k)-элементных подмножеств S, размер множества B равен. Между двумя множествами A и B существует простое взаимно однозначное соответствие (биекция): оно сопоставляет каждое k-элементное подмножество (то есть элемент A) с его дополнением, которое содержит ровно оставшиеся n − k элементов S и, следовательно, является элементом B. Более формально это можно записать с помощью функциональной нотации как f : A → B, определяемую как f(X) = X^(c) для любого k-элементного подмножества X множества S, где дополнение берется в S. Чтобы показать, что f является биекцией, сначала предположим, что f(X1) = f(X2), то есть X1^(c) = X2^(c). Возьмем дополнения обеих частей (в S), используя тот факт, что дополнение дополнения множества является исходным множеством, чтобы получить X1 = X2. Это показывает, что f является инъекцией (одно-к-одному). Теперь возьмем любое (n − k)-элементное подмножество S из B, скажем Y. Его дополнение в S, Y^(c), является k-элементным подмножеством и, следовательно, элементом A. Поскольку f(Y^(c)) = (Y^(c))^(c) = Y, f также является сюръекцией (отображением на), и, следовательно, биекцией. Результат теперь следует из того, что существование биекции между этими конечными множествами показывает, что они имеют одинаковый размер, то есть .