podzbior

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Doktór Piter
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 10 sty 2007, o 15:29
Płeć: Mężczyzna
Lokalizacja: wawa
Podziękował: 3 razy

podzbior

Post autor: Doktór Piter »

Ile podzbiorów ma zbior n-elementowy, w odp jest takie wzor 2^n. moglby ktos wytlumaczyc dlaczego????
Awatar użytkownika
bartholdy
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 14 gru 2006, o 19:35
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 49 razy

podzbior

Post autor: bartholdy »

Tworzymy kolejne podzbior \(\displaystyle{ 0,1,2,3...n}\) elementowe wybierając spośród \(\displaystyle{ n}\) elementów .
\(\displaystyle{ 1^\circ {n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n}}\)
Korzystając ze wzoru Newtona.
\(\displaystyle{ 2^\circ {n \choose 0}a^n + {n \choose 1}a^{n-1}b + {n \choose 2}a^{n-2}b^2 + ... + {n \choose n}b^n = (a+b)^n}\)

Jak widać \(\displaystyle{ 1^\circ}\) jest \(\displaystyle{ 2^\circ}\), gdzie współczynniki \(\displaystyle{ a = 1, b = 1}\), stąd
\(\displaystyle{ {n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n} = (1+1)^n = 2^n}\)
bediej
Użytkownik
Użytkownik
Posty: 57
Rejestracja: 3 sty 2007, o 18:52
Płeć: Mężczyzna
Lokalizacja: zza płota
Pomógł: 7 razy

podzbior

Post autor: bediej »

tak jaśniej logiczniej: dla każego elementu ze zbioru n elementowego określasz czy dany element ma się znaleźć w podzbiorze czy nie.... czyli dwie możliwości do potegi liczebności zbioru czyli 2^n.. choć bartholdy rozpisał to bardziej formalnie
ODPOWIEDZ