Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: Lokman Gökçe - Eylül 04, 2022, 09:43:26 ös
-
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.
-
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.