Бієкти́вне дове́дення — це техніка доведення, за якої знаходиться бієктивна функція f : A → B між двома скінченними множинами A і B або бієктивна функція, що зберігає розмір, між двома , чим доводиться однаковість числа елементів, |A| = |B|. Ця техніка корисна, коли ми хочемо знати розмір A, але не можемо знайти прямого способу підрахунку елементів множини. У цьому випадку встановлення бієкції між A і деякою множиною B розв'язує задачу, якщо число елементів множини B обчислити простіше. Інша корисна властивість цієї техніки — природа бієкції сама по собі часто дає важливу інформацію про кожну з двох множин.

Базові приклади

Доведення симетрії біномних коефіцієнтів
Симетрія біномних коефіцієнтів стверджує, що

: 

Це означає, що є рівно стільки комбінацій k елементів із множини, що містить n елементів, як і комбінацій n − k елементів.

Бієктивне доведення
Зауважимо, що дві величини, для яких ми доводимо рівність, підраховують кількість підмножин розміру k і n − k відповідно будь-якої n-елементної множини S. Існує проста бієкція між двома сімействами F'k та Fn − k підмножин S'' — вона пов'язує кожну k-елементну підмножину з її доповненням, яке містить рівно n − k елементів множини S. Оскільки F'k та Fn − k мають однакову кількість елементів, відповідні біномні коефіцієнти мають бути рівними.

Рекурентне відношення трикутника Паскаля

:  для 

Бієктивне доведення
Доведення. Підрахуємо число способів вибрати k елементів із n-елементної множини. Знову, за визначенням, ліва частина рівності дорівнює числу способів вибору k елементів із n. Оскільки 1 ≤ k ≤ n − 1, можна фіксувати елемент e з n-елементної множини, так що підмножина, що залишилася, не порожня. Для кожної k-елементної множини, якщо e вибрано, існує

: 

способів вибору решти k − 1 елементів серед n − 1 можливостей. В іншому випадку є

: 

способів вибору решти k елементів серед n − 1 можливостей, що залишилися. Тоді є

: 

способів вибору k елементів.

Інші приклади
Задачі, що дозволяють комбінаторне доведення, не обмежені біноміальними коефіцієнтами. У міру зростання складності задачі комбінаторне доведення стає дедалі витонченішим. Техніка бієктивного доведення корисна в галузях дискретної математики, таких як комбінаторика, теорія графів та теорія чисел.

Класичні приклади бієктивних доведень у комбінаториці:

* Код Прюфера, що дає доведення формули Келі для числа позначених дерев.
* , що дає доведення формули Бернсайда для симетричної групи.
* Спряження діаграм Юнга, що дає доведення класичного результату про кількість деяких розбиттів цілих чисел.
* Бієктивні доведення .
* Бієктивні доведення формули для чисел Каталана.

Див. також

* Біном Ньютона
* Теорема Кантора — Бернштейна
* Подвійний підрахунок (техніка доведення)
* Комбінаторні принципи
* 
* 

Примітки


Література

*  


Посилання
*  «Division by three» — Дойль і Конвей.
*  «A direct bijective proof of hook-length formula» — Новеллі,  і Стояновський.
*  «Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees» — Жиль Шеффер.
*  «Kathy O'Hara's Constructive Proof of Unimodality of Gaussian Polynomials» — .
*  «Partition Bijections, a Survey»'' — .
* 


