Биективное доказательство (>nytmnfuky ;ktg[gmyl,vmfk)

Перейти к навигации Перейти к поиску

Биективное доказательство — это техника доказательства, при которой находится биективная функция f : AB между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя комбинаторными классами[англ.], чем доказывается одинаковость числа элементов, |A| = |B|. Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств.

Базовые примеры

[править | править код]

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

[править | править код]

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

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

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

[править | править код]

Заметим, что две величины, для которых мы доказываем равенство, подсчитывают число подмножеств размера k и n − k соответственно любого n-элементного множества S. Существует простая биекция между двумя семействами Fk и Fn − k подмножеств S — она связывает каждое k-элементное подмножество с его дополнением, которое содержит в точности оставшиеся n − k элементов множества S. Поскольку Fk и Fn − k имеют одинаковое число элементов, соответствующие биномиальные коэффициенты должны быть равны.

Рекуррентное отношение треугольника Паскаля

[править | править код]
для

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

[править | править код]

Доказательство. Мы считаем число способов выбрать k элементов из n-элементного множества. Снова, по определению, левая часть равенства равна числу способов выбора k элементов из n. Поскольку 1 ≤ kn − 1, мы можем фиксировать элемент e из n-элементного множества, так что оставшееся подмножество не пусто. Для каждого k-элементного множества, если e выбрано, существует

способов выбора оставшихся k − 1 элементов среди оставшихся n − 1 возможностей. В противном случае имеется

способов выбора оставшихся k элементов среди оставшихся n − 1 возможностей. Тогда есть

способов выбора k элементов.

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

[править | править код]

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

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

Примечания

[править | править код]

Литература

[править | править код]
  • Nicholas A. Loehr. Bijective Combinatorics. — CRC Press, 2011. — ISBN 978-1439848845. Архивировано 23 октября 2015 года.