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

Binom əmsallarının simmetriyasının sübutu

Binom əmsallarının simmetriyası bildirir ki

${n \choose k}={n \choose n-k}.$

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 F_k və F_n − 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

• Nicholas A. Loehr. Bijective Combinatorics. CRC Press. 2011. Arxivləşdirilib 2015-10-23 at Archive-It