6. Feladat: Összes részhalmaz kombinatorikusan
Feladat:
Egy 5 elemű halmaz esetén számítsa ki a 0, 1, 2, 3, 4 és 5 elemű részhalmazok számát, majd igazolja, hogy összegük megegyezik a halmaz összes részhalmazának számával!
Megoldás:
A binomiális együtthatók kiszámítása:
- 0 elemű: \( \binom{5}{0} = 1 \)
- 1 elemű: \( \binom{5}{1} = 5 \)
- 2 elemű: \( \binom{5}{2} = 10 \)
- 3 elemű: \( \binom{5}{3} = 10 \)
- 4 elemű: \( \binom{5}{4} = 5 \)
- 5 elemű: \( \binom{5}{5} = 1 \)
Ezek összege: \( 1 + 5 + 10 + 10 + 5 + 1 = 32 \).
Az összes részhalmaz száma képlettel: \( 2^5 = 32 \). A két érték megegyezik.