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

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

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

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

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

${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 мають однакову кількість елементів, відповідні біномні коефіцієнти мають бути рівними.

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

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

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

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

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

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

${n-1 \choose k}$

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

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

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

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

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

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

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

Див. також

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

Література

• Nicholas A. Loehr. Bijective Combinatorics. — CRC Press, 2011. — ISBN 978-1439848845. [[url=https://wayback.archive-it.org/all/20151023194824/http://www.math.vt.edu/people/nloehr/bijbook.html Архівовано] 2015-10-23 у wayback.archive-it.org]

Посилання

• «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» — Ігор Пак.
• Weisstein, Eric W. Принцип інволюції Гарсії — Мілна(англ.) на сайті Wolfram MathWorld.