logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Inne, zadanie nr 530

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj