Inne, zadanie nr 530

Autor	Zadanie / Rozwiązanie
aaakuuus02 postów: 19	2012-10-09 16:11:22 Obliczyć, ile różnych podzbiorów można utworzyć ze zbioru n-elementowego :) z góry dziękuje i proszę o wyjaśnienie, dlaczego właśnie tak,a nie inaczej, pozdrawiam ;))

tumor postów: 8070	2012-10-09 16:45:28 Elementy w zbiorze n-elementowym możemy ponumerować. Każdy element może być w podzbiorze (to oznaczmy $1$), albo też może go nie być (to oznaczmy $0$). Wówczas np dla 3-elementowego zbioru $\{a,b,c\}$ podzbiory opisać można tak: $000$ - podzbiór pusty $001$ $010 = \{b\}$ $100$ $011 = \{b,c\}$ $101$ $110$ $111$ - cały zbiór Prawda? A ile jest ciągów o długości $n$, których wyrazy są $0$ lub $1$? Oczywiście $2^n$. To właśnie liczba podzbiorów zbioru n-elementowego. ---------- To samo osiągamy indukcyjnie. Zbiór 1-elementowy ma dwa podzbiory, czyli $2^1$. Jeśli zaś zbiór n-1-elementowy ma $2^{n-1}$ podzbiorów i dodamy do zbioru jeden nowy element, to liczba podzbiorów podwoi się (bo do każdego podzbioru możemy ten nowy element dodać otrzymując nowy podzbiór lub nie dodawać, dwa wyjścia). Czyli dla n-elementowego dostajemy $2^n$.

aaakuuus02 postów: 19	2012-10-09 17:01:19 oo, dziękuje bardzo za odpowiedź :) !

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj