Véges halmaz részhalmazainak száma
Határozza meg egy véges halmaz részhalmazainak számát!
Egy n elemű halmaznak 2^n szám különböző részhalmaza van.
Bizonyítása:
Tekintsük az (a ={{a1,a2,…,An}}) halmazt! Egy részhalmazt megadhatunk oly módon, hogy az a1, a2, … , aN elemekről rendre megmondjuk, hogy benne vannak-e a részhalmazban, vagy sem. Ennek alapján az A halmaz részhalmazait megfeleltetjük 0 és 1 számjegyekből álló n tagú számsorozatoknak: a k-adik helyre aszerint írunk 0-át vagy 1-et, hogy a(k) benne van-e a részhalmazban. Ha nincs benne, 0-át; ha benne van, 1-et írunk. Ez a megfeleltetés kölcsönösen egyértelmű, így pontosan annyi részhalmaza van az A halmaznak, mint ahány 0-ákból és 1-esekből álló n tagú számsorozat van. Minden hely kitöltésére egymástól függetlenül 2 lehetőségünk van [0-át vagy 1-et írhatunk]. Így a lehetőségek száma 2^n.
