XXV OM - II - Zadanie 1

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

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.