De ce contează?
Imaginează-ți un panou cu 3 comutatoare, fiecare pornit sau oprit. O „submulțime" e o configurație a panoului: alegi care comutatoare sunt pornite. Câte panouri diferite poți forma? Primul comutator: 2 variante. Al doilea: tot 2. Al treilea: tot 2. Cum alegerile sunt independente, numărul total se înmulțește: 2·2·2 = 8. Asta sunt toate submulțimile unei mulțimi cu 3 elemente.
Intuiția
O submulțime a lui {a, b, c} se construiește răspunzând la o întrebare pentru
fiecare element: „îl includ sau nu?". Sunt n întrebări independente, fiecare cu
2 răspunsuri. Numărul de moduri în care poți răspunde la toate este produsul
alegerilor: 2 · 2 · ... · 2 de n ori, adică 2^n. Nu trebuie să listezi
nimic — numeri direct deciziile.