Бієкти́вне дове́дення — це техніка доведення, за якої знаходиться бієктивна функція f : A → B між двома скінченними множинами A і B або бієктивна функція, що зберігає розмір, між двома [en], чим доводиться однаковість числа елементів, |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 ≤ k ≤ n − 1, можна фіксувати елемент e з n-елементної множини, так що підмножина, що залишилася, не порожня. Для кожної k-елементної множини, якщо e вибрано, існує
способів вибору решти k − 1 елементів серед n − 1 можливостей. В іншому випадку є
способів вибору решти k елементів серед n − 1 можливостей, що залишилися. Тоді є
способів вибору k елементів.
Інші приклади
Задачі, що дозволяють комбінаторне доведення, не обмежені біноміальними коефіцієнтами. У міру зростання складності задачі комбінаторне доведення стає дедалі витонченішим. Техніка бієктивного доведення корисна в галузях дискретної математики, таких як комбінаторика, теорія графів та теорія чисел.
Класичні приклади бієктивних доведень у комбінаториці:
- Код Прюфера, що дає доведення формули Келі для числа позначених дерев.
- [ru], що дає доведення формули Бернсайда для симетричної групи.
- (Спряження) діаграм Юнга, що дає доведення класичного результату про кількість деяких розбиттів цілих чисел.
- Бієктивні доведення [en].
- Бієктивні доведення формули для чисел Каталана.
Див. також
Примітки
Література
- Nicholas A. Loehr. Bijective Combinatorics. — CRC Press, 2011. — . [[url=https://wayback.archive-it.org/all/20151023194824/http://www.math.vt.edu/people/nloehr/bijbook.html Архівовано] 2015-10-23 у wayback.archive-it.org]
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Biyekti vne dove dennya ce tehnika dovedennya za yakoyi znahoditsya biyektivna funkciya f A B mizh dvoma skinchennimi mnozhinami A i B abo biyektivna funkciya sho zberigaye rozmir mizh dvoma en chim dovoditsya odnakovist chisla elementiv A B Cya tehnika korisna koli mi hochemo znati rozmir A ale ne mozhemo znajti pryamogo sposobu pidrahunku elementiv mnozhini U comu vipadku vstanovlennya biyekciyi mizh A i deyakoyu mnozhinoyu B rozv yazuye zadachu yaksho chislo elementiv mnozhini B obchisliti prostishe Insha korisna vlastivist ciyeyi tehniki priroda biyekciyi sama po sobi chasto daye vazhlivu informaciyu pro kozhnu z dvoh mnozhin Bazovi prikladiDovedennya simetriyi binomnih koeficiyentiv Simetriya binomnih koeficiyentiv stverdzhuye sho n k n n k displaystyle n choose k n choose n k Ce oznachaye sho ye rivno stilki kombinacij k elementiv iz mnozhini sho mistit n elementiv yak i kombinacij n k elementiv Biyektivne dovedennya Zauvazhimo sho dvi velichini dlya yakih mi dovodimo rivnist pidrahovuyut kilkist pidmnozhin rozmiru k i n k vidpovidno bud yakoyi n elementnoyi mnozhini S Isnuye prosta biyekciya mizh dvoma simejstvami Fk ta Fn k pidmnozhin S vona pov yazuye kozhnu k elementnu pidmnozhinu z yiyi dopovnennyam yake mistit rivno n k elementiv mnozhini S Oskilki Fk ta Fn k mayut odnakovu kilkist elementiv vidpovidni binomni koeficiyenti mayut buti rivnimi Rekurentne vidnoshennya trikutnika Paskalya n k n 1 k 1 n 1 k displaystyle n choose k n 1 choose k 1 n 1 choose k dlya 1 k n 1 displaystyle 1 leq k leq n 1 Biyektivne dovedennya Dovedennya Pidrahuyemo chislo sposobiv vibrati k elementiv iz n elementnoyi mnozhini Znovu za viznachennyam liva chastina rivnosti dorivnyuye chislu sposobiv viboru k elementiv iz n Oskilki 1 k n 1 mozhna fiksuvati element e z n elementnoyi mnozhini tak sho pidmnozhina sho zalishilasya ne porozhnya Dlya kozhnoyi k elementnoyi mnozhini yaksho e vibrano isnuye n 1 k 1 displaystyle n 1 choose k 1 sposobiv viboru reshti k 1 elementiv sered n 1 mozhlivostej V inshomu vipadku ye n 1 k displaystyle n 1 choose k sposobiv viboru reshti k elementiv sered n 1 mozhlivostej sho zalishilisya Todi ye n 1 k 1 n 1 k displaystyle n 1 choose k 1 n 1 choose k sposobiv viboru k elementiv displaystyle Box Inshi prikladiZadachi sho dozvolyayut kombinatorne dovedennya ne obmezheni binomialnimi koeficiyentami U miru zrostannya skladnosti zadachi kombinatorne dovedennya staye dedali vitonchenishim Tehnika biyektivnogo dovedennya korisna v galuzyah diskretnoyi matematiki takih yak kombinatorika teoriya grafiv ta teoriya chisel Klasichni prikladi biyektivnih doveden u kombinatorici Kod Pryufera sho daye dovedennya formuli Keli dlya chisla poznachenih derev ru sho daye dovedennya formuli Bernsajda dlya simetrichnoyi grupi Spryazhennya diagram Yunga sho daye dovedennya klasichnogo rezultatu pro kilkist deyakih rozbittiv cilih chisel Biyektivni dovedennya en Biyektivni dovedennya formuli dlya chisel Katalana Div takozhBinom Nyutona Teorema Kantora Bernshtejna Kombinatorni principi en en PrimitkiLiteraturaNicholas 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 Arhivovano 2015 10 23 u wayback archive it org Posilannya Division by three Dojl i Konvej Novelli en i Stoyanovskij Zhil Sheffer en Partition Bijections a Survey en Weisstein Eric W Princip involyuciyi Garsiyi Milna angl na sajti Wolfram MathWorld