XXV OM - II - Zadanie 1

Niech $ Z $ będzie zbiorem $ n $-elementowym. Znaleźć liczbę takich par zbiorów $ (A, B) $, że $ A $ zawiera się w $ B $ i $ B $ zawiera się w $ Z $. Przyjmujemy, że każdy zbiór zawiera także siebie i zbiór pusty.

Rozwiązanie

Jak wiadomo, jeżeli $ 0 \leq r \leq s $, to liczba podzbiorów $ r $-elementowych zbioru $ s $-elementowego jest równa $ \binom{s}{r} $, a liczba
wszystkich podzbiorów zbioru $ s $-elementowego jest równa $ 2^s $.

Podzbiór $ k $-elementowy $ A $, gdzie $ 0 \leq k \leq n $, można wybrać ze zbioru $ Z $ na $ \binom{n}{k} $ sposobów. Po ustaleniu zbioru $ A $ zbiór $ B-A $ jest pewnym podzbiorem zbioru $ Z-A $, który ma $ n - k $ elementów. Zbiór $ B-A $ może więc być wybrany na $ 2^{n-k} $ sposobów. Różnym wyborom zbioru $ B-A $ odpowiadają przy tym różne zbiory $ B $ zawierające zbiór $ A $. Zatem liczba par zbiorów $ (A,B) $ spełniających warunki zadania jest równa

\[<br />
\sum_{k=0}^n \binom{n}{k} 2^{n-k} =<br />
\sum_{k=0}^n \binom{n}{k} 1^k \cdot 2^{n-k} = (1+2)^n = 3^n<br />
\]

na mocy wzoru dwumianowego.

Komentarze

Dodaj nową odpowiedź