Alt Küme sayısı formulü ispatı

Bir kümenin bütün elemanları o kümeden farklı olan başka bir kümenin de aynen elemanları oluyorsa bu küme diğer kümenin alt kümesi olur. Alt küme sayısı kümenin eleman sayısı n olmak üzere, 

2ⁿ  formülü ile hesaplanır. 

A={a,b,c} kümesinin alt küme sayısı 2³=8 olarak bulunur.  Bu formülün ispatında kombinasyon konusundan yararlanılır. Kümenin alt kümelerini seçerken önce hiç elemanı olmayan boş küme seçilir. 

Hiç elemanı olmayan alt küme sayısı= C(n,0) 

Daha sonra sırasıyla 1 elemanlı alt küme sayısı= C(n,1) 

2 elemanlı alt küme sayısı= C(n,2) 

3 elemanlı alt küme sayısı= C(n,3) 

4 elemanlı alt küme sayısı= C(n,4) 

...................................................... 

...................................................... 

n elemanlı alt küme sayısı= C(n,n) şeklinde devam edildiğinde en son kümenin kendisi de bir alt küme olacağından en son olarak C(n,n) seçimi yapılır.

Buna göre yukarıda yazılan tüm alt kümeleri sayısı toplandığında; C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)+....................+C(n,n) toplamı elde edilir. 

Bu toplam da Hayyam üçgeni olarak bilinen Pascal özdeşliğindeki katsayıları ifade eder ki bu katsayılar aynı zamanda Her hangi iki terimli ifadenin toplamı ya da farkının belli bir kuvvetini ifade eden Binom açılımın katsayılarını verir.  Aşağıdaki Hayyam Üçgeni ile ilgili tablodan da alt küme sayısının ispatı görülebilir.  (Bkz. Hayyam üçgeni)

(1+x)n=C(n,0)⋅xn+C(n,1)⋅xn−1+............+C(n,n)  (Binom Açılımı)

Bu açılımda özel olarak bilinmeyen yerine (x=1) yazıldığında, n elemanlı bir küme için, alt küme sayısı: 2ⁿ formulü elde edilmiş olur.