Alt küme sayısı

Question

n elemanlı bir kümenin alt kümelerinden, hiçbiri bir diğerinin alt kümesi olmayacak şekilde 

n çiftse en çok  

$\left( \begin{matrix} n\\ \dfrac {n} {2}\end{matrix} \right)$

 n tekse en çok

$\left( \begin{matrix} n\\ \dfrac {n\mp 1} {2}\end{matrix} \right)$ küme seçilebilir.

Bu ifade nasıl kanıtlanabilir?

Öncelikle C(n,m) kombinasyonu kadar m  elemanlı alt kümeleri alalım.Cevaba  m elemanlılar dışında bir küme dahil edilemez.Çünkü m elemanlı kümeler içerisinde kendisinden daha az elaman sayısına sahip olan her alt kümeyi kapsayan  bir küme vardır.Kendisinden daha fazla elaman sayısına sahip olan kümelerin her biri de bu m elemanlılardan birini mutlaka kapsar.Önemli olan max sonuca ulaşmak adına alt küme için hangi eleman sayısını seçtiğimiz

Elimdeki kaynakta yukarıda yazdığım genelleme yapılmış.Fakat nasıl kanıtlanabileceğine dair fikir yürütemiyorum 

Answer 1

Ben bunu bir yerde ispatlamistim ama nerede, ne zaman hatirlamiyorum... 

Ipucu: Su sekilde yazmak yeterli ($n$ ve $m$ uygun olmak uzere) $$C(n,m)=\prod_{i=1}^{m}\frac{n+1-i}{i}$$ olur. 

Cevap icin islemler: $1\le i \le n$  icin $$\frac{n+1-i}{i}$$ degerini incelemek yeterli. Bu deger $\ge 1$ ise carpmaya katalim, degil ise duralim. Sunu gormek zor degil: $$\frac{n+1-i}{i}\ge 1 \iff i\le \frac{n+1}{2}$$ ve esitlik sadece $(n+1)/2$'de saglanir.