Biyektiv sübut
Biyektiv sübut — iki sonlu A və B çoxluğu arasında f : A → B bijektiv funksiyasının və ya iki kombinator sinfi arasında ölçüsü qoruyan bijective funksiyasının tapıldığı sübut üsuludur və bununla da eyni sayda elementi sübut edir, |A| = |B|. Texnikanın faydalı olduğu yer A-nın ölçüsünü bilmək istədiyimiz, lakin çoxluğun elementlərini saymaq üçün birbaşa yol tapa bilmədiyimiz zamandır. Bu halda, B çoxluğunun elementlərinin sayını hesablamaq daha asan olarsa, A və bəzi B çoxluğu arasında bijection qurmaq problemi həll edir. Bu texnikanın digər faydalı xüsusiyyəti ondan ibarətdir ki, bijeksiyanın təbiəti çox vaxt iki dəstdən hər biri haqqında güclü məlumat verir.
Əsas nümunələr redaktə
Binom əmsallarının simmetriyasının sübutu redaktə
Binom əmsallarının simmetriyası bildirir ki
Bu o deməkdir ki, n elementdən ibarət çoxluqda n − k elementin birləşmələri qədər k elementin kombinasiyası var.
Biyektiv sübut Nəzərə alın ki, bərabərliyini sübut etdiyimiz iki kəmiyyət istənilən n elementli S çoxluğunun müvafiq olaraq k və n − k ölçülü alt çoxluqlarının sayını hesablayır. S alt çoxluqlarının iki ailəsi Fk və Fn − k arasında sadə biyeksiya mövcuddur. — hər bir k elementli alt çoxluğu S çoxluğunun tam olaraq qalan n − k elementlərini ehtiva edən tamamlayıcısı ilə əlaqələndirir. Fk və Fn − k elementlərinin sayı eyni olduğundan, müvafiq binom əmsalları bərabər olmalıdır.
Ədəbiyyat redaktə
- Nicholas A. Loehr. Bijective Combinatorics. CRC Press. 2011. Arxivləşdirilib 2015-10-23 at Archive-It