Kombinatorik Bir Özdeşliğin İspatı-2 {Çözüldü}

[Lokman Gökçe]

Problem: $A \neq \emptyset $ kümesinin bir $B \neq \emptyset$ altkümesi için $|A| = n$ ve $|B| = m$ dir. $ A = \{ a_1, a_2, \dots a_m, a_{m+1}, \dots , a_n \}$ ve $B = \{ a_1, a_2, \dots , a_m \}$ diyelim. $m \leq k \leq n$ olmak üzere, $A$ kümesinin $k$ elemanlı altkümelerinden kaçı $B$ yi bir altküme olarak içerir?

Ayrıca, $m, k, n \in \mathbb{Z^+}$ ve $m \leq k \leq n$ ise,
$$  \dbinom{n-m}{k-m} = \sum_{r=0}^{m}(-1)^r\dbinom{m}{r}\dbinom{n-r}{k}$$
özdeşliğini ispatlayınız.

[Lokman Gökçe]

Problemin ilk kısmı basit olmakla beraber, ikinci kısmı daha uzun düşündürdü. Çözdükten sonra "ikinci kısım da basitmiş" dedirtiyor. Tabii çözdükten sonra...

Çözüm: $B \subseteq X \subseteq A$ ve $|X|=k$ olacak şekilde $X$ kümelerinin sayısını bulmak istiyoruz. $B$'deki $m$ tane elemanın tümünün $X$'te de bulunması gerekir. O halde $X$ için $k-m$ tane daha eleman seçmemiz gerekiyor. Bunları da $A-B$ fark kümesinden seçmeliyiz. $|A-B| = n-m$ tane elemandan $k-m$ tanesinin seçim sayısı $$\dbinom{n-m}{k-m}$$ olur. Böylece ilk kısmı çözmüş oluyoruz. Burasının, problemin kalan kısmındaki özdeşliğin ispatlanabilmesi için verilmiş bir ipucu olduğunu anlayabiliyoruz.


Şimdi ikinci kısma geçelim. Elbette $|X|$'i farklı bir yolla daha hesaplamamız gerekiyor. Verilen özdeşliğin alterne biçimde olduğunu göz önüne alırsak bu farklı sayma yolunun içerme dışarma prensibi olduğunu anlayabiliriz. Başlayalım:

$\dbinom{m}{r}$ ile $B$ kümesindeki elemanlardan $r$ tanesinin $X$ kümesine alınmama sayısını gösterelim. $r=0,1,2,\dots , m$ biçiminde değişmektedir. $\dbinom{n-r}{k}$ ile, $B$ den seçilmemiş olan belirli $r$ tanesi eleman haricinde, geriye kalan $n-r$ elemandan $k$ tanesinin seçilme sayısını gösterelim.

$\bullet $ $r=0$ iken, $\dbinom{m}{0}$ oluşur ve $B$ den seçilmeyen belirli bir eleman yoktur. Hesaplamalar içinde $B$ de bulunmayan elemanlardan oluşan alt kümeler de gelebilir ancak, başlangıçta biz $B$'deki belirli elemanların $X$'e katılmasını engelleme yönünde bir irade göstermedik. (Bu kısmı düşünmek benim için vakit alıcı olmuştu.) Devam edelim. $\dbinom{n}{k}$ ile $k$ elemanlı altkümeleri $A$ dan seçmiş olduk. $\dbinom{m}{0}\dbinom{n}{k} = \dbinom{n}{k}$ olur. Bunlar açıkça $k$ elemanlı tüm alt kümelerin sayısıdır. Bazıları $B$'yi kapsarken bazıları da $B$ yi kapsamayacaktır. Yani bu  $\dbinom{n}{k}$ kobminasyonu, tüm durumların sayısını gösteriyor.

$\bullet $ $r=1$ iken,  $\dbinom{m}{1}$ oluşur ve $B$ den seçilmeyen belirli bir elemana karar vereceğiz. $\dbinom{n-1}{k}$ ile, $B$ den seçmemeye karar verdiğimiz eleman haricinde geri kalan $n-1$ eleman arasından $k$ tanesini seçiyoruz. $\dbinom{m}{1}\dbinom{n-1}{k}$ tane istenmeyen durum oluştu. Bunları tüm durumlardan çıkarmalıyız.
$$\dbinom{m}{0}\dbinom{n}{k} - \dbinom{m}{1}\dbinom{n-1}{k}$$
elde ederiz.

$\bullet $ $r=2$ iken, $\dbinom{m}{2}$ oluşur ve $B$ den seçilmeyen belirli iki elemana karar vereceğiz. $\dbinom{n-2}{k}$ ile, $B$ den seçmemeye karar verdiğimiz iki eleman haricinde geri kalan $n-2$ eleman arasından $k$ tanesini seçiyoruz. $\dbinom{m}{2}\dbinom{n-2}{k}$ tane istenmeyen durum oluştu. Fakat bunlar önceki istenmeyen durum hesabımız içinde de görüldüğü için, içerme dışarma prensibi gereğince tekrar eklememiz gereken durumlar olurlar.
$$\dbinom{m}{0}\dbinom{n}{k} - \dbinom{m}{1}\dbinom{n-1}{k} + \dbinom{m}{2}\dbinom{n-2}{k}$$
elde ederiz.

Bu şekilde, $r=3,4,\dots, m$ için içerme dışarma prensibini uygulamaya devam edersek, sonuçta istenen özellikteki $X$ kümelerinin sayısı

$$  \dbinom{m}{0}\dbinom{n}{k} - \dbinom{m}{1}\dbinom{n-1}{k} + \dbinom{m}{2}\dbinom{n-2}{k} - \cdots + (-1)^m \dbinom{m}{m}\dbinom{n-m}{k}$$

olur. Bu iki sayma sonucunu eşitlersek,

$$ \dbinom{n-m}{k-m} = \sum_{r=0}^{m}(-1)^r\dbinom{m}{r}\dbinom{n-r}{k} $$

elde edilir.