Trójkąt Pascala i liczba podzbiorów - ile podzbiorów ma zbiór 8-elementowy?

Krok 1. Budujemy trójkąt. Każdy wiersz zaczyna się i kończy jedynką, a każda liczba w środku jest sumą dwóch liczb nad nią. Wiersz $n = 7$ to $1, 7, 21, 35, 35, 21, 7, 1$, więc wiersz $n = 8$:

$1,\ \ 1+7 = 8,\ \ 7+21 = 28,\ \ 21+35 = 56,\ \ 35+35 = 70,\ \ 56,\ \ 28,\ \ 8,\ \ 1.$

Krok 2. Co oznaczają liczby w wierszu. Liczba na pozycji $k$ (liczymy od zera) to $\binom{8}{k}$ - liczba podzbiorów zbioru $A$, które mają dokładnie $k$ elementów. Na przykład $\binom{8}{0} = 1$ (zbiór pusty), $\binom{8}{1} = 8$ (zbiory jednoelementowe).

Krok 3. Przykład b). Wszystkich podzbiorów jest tyle, ile wynosi suma wiersza:

$1 + 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 256 = 2^8.$

To samo wynika z reguły mnożenia: o każdym z $8$ elementów decydujemy „bierzemy” albo „nie bierzemy”, więc podzbiorów jest $2^8 = 256$. Podzbiorów trzyelementowych jest $\binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{6} = 56$.

Krok 4. Przykład c) - dopełnienie. „Co najmniej dwa elementy” to wszystkie podzbiory oprócz tych, które mają $0$ albo $1$ element:

$2^8 - \binom{8}{0} - \binom{8}{1} = 256 - 1 - 8 = 247.$

Odpowiedź. a) $1, 8, 28, 56, 70, 56, 28, 8, 1$; b) $256$ podzbiorów, w tym $56$ trzyelementowych; c) $247$ podzbiorów.