k elemű részhalmazok

Jelölések: Legyen (Hk) (olvasata H alatt k) a H halmaz k elemű részhalmazainak halmaza. Legyen (nk) egy n elemű halmaz k elemű részhalmazainak száma.

Az ilyen alakú számokat binomiális együtthatóknak nevezzük. Az elnevezés indoka csak később derül ki.

Példa: (n0)=1, (nn)=1, (nK)=0, ha K>n.

Rekurzió:

Tétel: (nk)= (n-1k)+(n-1k-1).

Bizonyítás: Legyen H egy n elemeű halmaz egy speciális s elemmel. Legyen H'=H-{s} egy n-1 elemű halmaz. (Hk) elemeit osszuk két diszjunkt osztályba aszerint, hogy s eleme a megfelelő részhalmaznak vagy sem. Az s-et nem tartalmazó k elemű részhalmazok (H'k) halmazt adják ki, azaz számuk (n-1k). Az s-et tartalmazó k elemű részhalmazok párbaállíthatók (H'k-1) elemeivel, azaz számuk (n-1k-1). A párbaállításnál egy R részhalmaz párja R-{s} (inverze (H'k-1) egy eleméhez azt a párt rendeli, amelyet az s elem hozzáadásaval kapunk.) Így adódik az állítás.

Megjegyzés: Az (nk) számok egy ``kétirányban végtelen téglalap'' alakú táblázatba sorolhatók:
 
k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9
n=0 1 0 0 0 0 0 0 0 0 0
n=1 1 1 0 0 0 0 0 0 0 0
n=2 1 2 1 0 0 0 0 0 0 0
n=3 1 3 3 1 0 0 0 0 0 0
n=4 1 4 6 4 1 0 0 0 0 0
n=5 1 5 10 10 5 1 0 0 0 0
n=6 1 6 15 20 15 6 1 0 0 0
n=7 1 7 21 35 35 21 7 1 0 0
n=8 1 8 28 56 70 56 28 8 1 0
n=9 1 9 36 84 126 126 84 36 9 1
A korábbi példa és a fenti rekurzió módot ad a táblázat kitöltésére. A táblázat nem 0 elemeit át szokás rendezni egy tetszetősebb formába: a Pascal-háromszög megszokott formájába:
 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
 

A Maple program   külön utasítással rendelkezik a binomiális együtthatók kiszámítására.

A Pascal-háromszög figyelmes tanulmányozása nagyon sok érdekes megfigyeléshez vezethet. Ezek közül néhány az interneten is elérhető: