Udowodnij, że zbiór n-elemntowy ma ...

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kamil13151
Użytkownik
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 ...

Post autor: kamil13151 »

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ą?
szw1710

Udowodnij, że zbiór n-elemntowy ma ...

Post autor: szw1710 »

Zbiór niepusty to taki, który nie jest pusty , czyli zawiera co najmniej jeden element.
kamil13151
Użytkownik
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 ...

Post autor: kamil13151 »

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?
Awatar użytkownika
kropka+
Użytkownik
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 ...

Post autor: kropka+ »

\(\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.
ODPOWIEDZ