Бієктивне доведення

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

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

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

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

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{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 мають однакову кількість елементів, відповідні біномні коефіцієнти мають бути рівними.

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

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$ для $1\le k\le n-1.$

Бієктивне доведення

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

$(\genfrac{}{}{0ex}{}{n-1}{k-1})$

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

$(\genfrac{}{}{0ex}{}{n-1}{k})$

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

$(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$

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

Інші приклади

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

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

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

Див. також

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

Література

• Шаблон:Книга Шаблон:Webarchive

Посилання

• «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» — Шаблон:Нп.
• Шаблон:MathWorld