Udowodnij, że zbiór n-elementowy ma \(\displaystyle{ 2^n}\) podzbiorów.
Wskazówka: Zastosuj wzór Newtona dla \(\displaystyle{ (1+1)^n}\).
\(\displaystyle{ {n \choose k} ={n \choose 0}+{n \choose 1} +...+{n \choose n} = 2^n}\)
Jak dalej to udowodnić, że druga część równania jest równa trzeciej?
Mam jeszcze problem ze zrobieniem jednego podpunktu zadania: wykorzystując podaną równość \(\displaystyle{ {n \choose 0}+{n \choose 1} +...+{n \choose n} = 2^n}\), oblicz liczbę wszystkich niepustych podzbiorów zbioru sześcioelementowego?
Niepuste podzbiory, nie bardzo wiem jakie to są?
Udowodnij, że zbiór n-elemntowy ma ...
-
- Użytkownik
- Posty: 5018
- Rejestracja: 28 wrz 2009, o 16:53
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 459 razy
- Pomógł: 912 razy
Udowodnij, że zbiór n-elemntowy ma ...
Zbiór niepusty to taki, który nie jest pusty , czyli zawiera co najmniej jeden element.
-
- Użytkownik
- Posty: 5018
- Rejestracja: 28 wrz 2009, o 16:53
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 459 razy
- Pomógł: 912 razy
Udowodnij, że zbiór n-elemntowy ma ...
He, ale mi to wiele nie mówi
Możesz podać przykład? Żeby nie było tam wyrazu "niepuste" to by było \(\displaystyle{ 2^6}\), to jakie są tam elementy puste?
Możesz podać przykład? Żeby nie było tam wyrazu "niepuste" to by było \(\displaystyle{ 2^6}\), to jakie są tam elementy puste?
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Udowodnij, że zbiór n-elemntowy ma ...
\(\displaystyle{ {n \choose k}}\) to ilość k-elementowych podzbiorów zbioru n-elementowego.
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}}\) to ilość wszystkich podzbiorów zbioru n-elementowego (łącznie z podzbiorem pustym dla k=0)
Mamy udowodnić, że \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\)
Dowód:
\(\displaystyle{ P=2 ^{n}=(1+1) ^{n}= {n \choose 0} 1 ^{n}1 ^{0}+ {n \choose 1}1 ^{n-1}1 ^{1}+...+ {n \choose n}1 ^{0}1 ^{n}= \sum_{k=0}^{n} {n \choose k} =L}\)
Co do drugiego pytania- z każdego zbioru można utworzyć jeden podzbiór pusty (zero-elementowy) więc ze zbioru 6-elementowego można utworzyć \(\displaystyle{ 2 ^{6}-1}\) niepustych podzbiorów.
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}}\) to ilość wszystkich podzbiorów zbioru n-elementowego (łącznie z podzbiorem pustym dla k=0)
Mamy udowodnić, że \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\)
Dowód:
\(\displaystyle{ P=2 ^{n}=(1+1) ^{n}= {n \choose 0} 1 ^{n}1 ^{0}+ {n \choose 1}1 ^{n-1}1 ^{1}+...+ {n \choose n}1 ^{0}1 ^{n}= \sum_{k=0}^{n} {n \choose k} =L}\)
Co do drugiego pytania- z każdego zbioru można utworzyć jeden podzbiór pusty (zero-elementowy) więc ze zbioru 6-elementowego można utworzyć \(\displaystyle{ 2 ^{6}-1}\) niepustych podzbiorów.