Hogyan adhatjuk meg egy n elemű halmaz összes részhalmazát?

Ki lehet. Vegyünk egy 3 elemű halmazt: {1;2;3}

Az a kérdés, hogy ennek hány részhalmaza van. Készítsünk táblázatot:

1 | 2 | 3 | halmaz

Amelyik tagot szeretnénk belevenni a halmazba, oda írjunk egy I betűt, ha nem, akkor egy N betűt:

I | N | I |, ebből egyértelműen meghatározható a halmaz: {1;3}

Ha egy másikat akarunk:

N | N | I |, ebből {3} lesz a részhalmaz.

Már csak az a kérdés, hogy hány sort tudunk ezzel a metódussal feltölteni. Ha jobban belegondolunk, visszavezethető ez a probléma egy alapfeladatra:

"Hányféleképpen színezhetünk ki egy 3-sávos zászlót 2 színnel (a színismétlés megengedett)?"

Erre tudjuk a választ: 2^3=8. Minden színezés megfeleltethető egy I-N kitöltésnek, tehát a 3 elemű halmaznak 8 részhalmaza van.

Ugyanezt a gondolatmenetet követve beláthatjuk, hogy az n elemű halmaz részhalmazainak száma 2^n.