Dany jest zbiór \(\displaystyle{ A=\left\{ 1,2,3,4,5\right\}}\). Oblicz liczbę wszystkich dwuelementowych podzbiorów zbioru A.
Prosiłbym o szczegółowe wytłumaczenie, nie bardzo rozumiem do czego są podzbiory.
Dwuelementowe podzbiory
-
kamil13151
- 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
-
Mistrz
- Użytkownik
- Posty: 637
- Rejestracja: 10 sie 2009, o 09:56
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz / Warszawa
- Podziękował: 19 razy
- Pomógł: 135 razy
Dwuelementowe podzbiory
Udowodnimy, że dla dowolnego \(\displaystyle{ n \in \mathbb{N}}\) oraz \(\displaystyle{ k=0,1,...,n}\) liczba k-elementowych podzbiorów dowolnego zbioru n-elementowego wynosi \(\displaystyle{ \frac{n \cdot (n-1) \cdot ... \cdot (n-k+1)}{1 \cdot 2 \cdot ... \cdot k}}\).
Weźmy dowolne \(\displaystyle{ n \in \mathbb{N}}\).
Dowód indukcyjny po \(\displaystyle{ k}\):
Dla \(\displaystyle{ k=0}\) jest to prawdą, gdyż powyższy ułamek jest równy 1, a jest właśnie dokładnie jeden zbiór pusty (0-elementowy).
Teraz dla \(\displaystyle{ k>0}\) przypuśćmy, że liczba (k-1)-elementowych podzbiorów dowolnego zbioru n-elementowego wynosi \(\displaystyle{ \frac{n \cdot (n-1) \cdot ... \cdot (n-k+2)}{1 \cdot 2 \cdot ... \cdot (k-1)}}\). Wówczas możemy policzyć k-elementowe podzbiory następująco: do każdego (k-1)-elementowego podzbioru dodajemy po jednym z pozostałych n-k+1 elementów tworząc w ten sposób n-k+1 pozbiorów k-elementowych z każdego pozbioru (k-1)-elementowego. Teraz, aby ostatecznie obliczyć liczbę wszystkich k-elementowych pozbiorów należy iloczyn \(\displaystyle{ \frac{n \cdot (n-1) \cdot ... \cdot (n-k+2)}{1 \cdot 2 \cdot ... \cdot (k-1)} \cdot (n-k+1)}\) podzielić przez \(\displaystyle{ k}\), bo każdy podzbiór k-elementowy policzyliśmy w powyższy sposób dokładnie k razy (po razie dla każdego jego elementu). Daje nam to tezę indukcyjną.
Stosując to do Twojego problemu (n=5, k=2) otrzymujemy, że liczba 2-elementowych podzbiorów zbioru 5-elementowego wynosi \(\displaystyle{ \frac{5 \cdot 4}{1 \cdot 2} = 10}\).
Jeśli nie rozumiesz podzbiorów, spróbuj spojrzeć w ten sposób: zamiast podzbioru \(\displaystyle{ Y}\) zbioru \(\displaystyle{ X}\) pomyśl o funkcji \(\displaystyle{ f}\) z \(\displaystyle{ X}\) w \(\displaystyle{ \{0,1\}}\) z następującą równoważnością: \(\displaystyle{ x \in Y \Leftrightarrow f(x)=1}\). Zamiast liczyć, ile jest podzbiorów zbioru \(\displaystyle{ X}\), policz, ile można określić na \(\displaystyle{ X}\) różnych funkcji tego typu.
Weźmy dowolne \(\displaystyle{ n \in \mathbb{N}}\).
Dowód indukcyjny po \(\displaystyle{ k}\):
Dla \(\displaystyle{ k=0}\) jest to prawdą, gdyż powyższy ułamek jest równy 1, a jest właśnie dokładnie jeden zbiór pusty (0-elementowy).
Teraz dla \(\displaystyle{ k>0}\) przypuśćmy, że liczba (k-1)-elementowych podzbiorów dowolnego zbioru n-elementowego wynosi \(\displaystyle{ \frac{n \cdot (n-1) \cdot ... \cdot (n-k+2)}{1 \cdot 2 \cdot ... \cdot (k-1)}}\). Wówczas możemy policzyć k-elementowe podzbiory następująco: do każdego (k-1)-elementowego podzbioru dodajemy po jednym z pozostałych n-k+1 elementów tworząc w ten sposób n-k+1 pozbiorów k-elementowych z każdego pozbioru (k-1)-elementowego. Teraz, aby ostatecznie obliczyć liczbę wszystkich k-elementowych pozbiorów należy iloczyn \(\displaystyle{ \frac{n \cdot (n-1) \cdot ... \cdot (n-k+2)}{1 \cdot 2 \cdot ... \cdot (k-1)} \cdot (n-k+1)}\) podzielić przez \(\displaystyle{ k}\), bo każdy podzbiór k-elementowy policzyliśmy w powyższy sposób dokładnie k razy (po razie dla każdego jego elementu). Daje nam to tezę indukcyjną.
Stosując to do Twojego problemu (n=5, k=2) otrzymujemy, że liczba 2-elementowych podzbiorów zbioru 5-elementowego wynosi \(\displaystyle{ \frac{5 \cdot 4}{1 \cdot 2} = 10}\).
Jeśli nie rozumiesz podzbiorów, spróbuj spojrzeć w ten sposób: zamiast podzbioru \(\displaystyle{ Y}\) zbioru \(\displaystyle{ X}\) pomyśl o funkcji \(\displaystyle{ f}\) z \(\displaystyle{ X}\) w \(\displaystyle{ \{0,1\}}\) z następującą równoważnością: \(\displaystyle{ x \in Y \Leftrightarrow f(x)=1}\). Zamiast liczyć, ile jest podzbiorów zbioru \(\displaystyle{ X}\), policz, ile można określić na \(\displaystyle{ X}\) różnych funkcji tego typu.