Proszę o pomoc
Zad
Podać kombinatoryczne uzasadnienie wzoru: \(\displaystyle{ \sum_{l=0}^{n} {n \choose l} = 2^{n}}\)
kombinatoryczne uzasadnienie wzoru
-
Errichto
- Użytkownik
- Posty: 1629
- Rejestracja: 17 mar 2011, o 18:55
- Płeć: Mężczyzna
- Lokalizacja: Suwałki
- Podziękował: 28 razy
- Pomógł: 272 razy
kombinatoryczne uzasadnienie wzoru
Masz zbiór \(\displaystyle{ n}\)-elementowy. Liczymy, ile podzbiorów ma ten zbiór.
1. Lewa strona:
Podzbiór może mieć 0, 1, 2, ..., n elementów.
\(\displaystyle{ k}\)-elementowych podzbiorów jest oczywiście \(\displaystyle{ {n \choose k}}\). Mamy zatem \(\displaystyle{ {n \choose 0}+ {n \choose 1}+ {n \choose 2}+...+ {n \choose n}}\) podzbiorów czyli sumę po lewej.
2. Prawa strona:
Każdy element może być w podzbiorze albo nie. Takie 2 możliwości ma każdy z \(\displaystyle{ n}\) elementów - razem \(\displaystyle{ 2^n}\) możliwości.
1. Lewa strona:
Podzbiór może mieć 0, 1, 2, ..., n elementów.
\(\displaystyle{ k}\)-elementowych podzbiorów jest oczywiście \(\displaystyle{ {n \choose k}}\). Mamy zatem \(\displaystyle{ {n \choose 0}+ {n \choose 1}+ {n \choose 2}+...+ {n \choose n}}\) podzbiorów czyli sumę po lewej.
2. Prawa strona:
Każdy element może być w podzbiorze albo nie. Takie 2 możliwości ma każdy z \(\displaystyle{ n}\) elementów - razem \(\displaystyle{ 2^n}\) możliwości.