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

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

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

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

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

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

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

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

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

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$ для ${\displaystyle 1\leq k\leq n-1.}$

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

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

${\displaystyle {n-1 \choose k-1}}$

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

${\displaystyle {n-1 \choose k}}$

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

${\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}$

способов выбора k элементов. ${\displaystyle \Box }$

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

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

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

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

См. также

• Бином Ньютона
• Теорема Кантора — Бернштейна
• Комбинаторные принципы

Примечания

Литература

Ссылки

• – by Doyle and Conway .
• – by Novelli, Pak and Stoyanovsky.
• – by Gilles Schaeffer.
• – by Doron Zeilberger.
• – by Igor Pak.
• – from MathWorld .