Liczba wszystkich podzbiorów zbioru skończonego

Można obliczyć, ile jest wszystkich podzbiorów pewnych zbiorów skończonych.

pewien zbiór dwuelementowy ma $2^{2} = 4$ podzbiory,
pewien zbiór czteroelementowy ma $2^{4} = 16$ podzbiorów,
pewien zbiór pięcioelementowy ma $2^{5} = 32$ podzbiory,
pewien podzbiór dziewięcioelementowy ma $2^{9} = 512$ podzbiorów.

Ustalając liczbę podzbiorów zauważaliśmy, że w stosunku do każdego elementu zbioru możemy na dwa sposoby podjąć decyzję o jego wyborze do tworzonego podzbioru.

Przykład 1

Rozpatrzmy teraz zbiór $A = \{a_{1}, a_{2}, . . ., a_{n}\}$ , który ma $n$ elementów. Dowolny podzbiór zbioru $A$ tworzymy, podejmując decyzję, czy każdy z kolejnych elementów zbioru $A$ : $a_{1}, a_{2}, . . ., a_{n}$ należy do tego podzbioru, czy nie należy. Można to zrobić na $\underset{n czynników}{\underset{⏟}{2 \cdot 2 \cdot . . . \cdot 2}} = 2^{n}$ sposobów.
Zatem liczba wszystkich podzbiorów zbioru $A$ , który ma $n$ elementów, jest równa $2^{n}$ .

Liczba kombinacji

W przykładach prezentowanych w tym rozdziale często spotykaliśmy się z koniecznością obliczenia, na ile sposobów możemy z ustalonego zbioru wybrać podzbiór o konkretnej liczbie elementów.

Przykład 2

Rozpatrzmy zbiór $A = \{a_{1}, a_{2}, . . ., a_{n}\}$ , który ma $n$ elementów. Wtedy, jak to już pokazywaliśmy w rozwiązaniach przykładów tego rozdziału:

jest jeden podzbiór zbioru $A$ , do którego nie wybierzemy żadnego elementu ze zbioru $A$ (tym podzbiorem jest zbiór pusty),
jest jeden podzbiór zbioru $A$ , do którego wybierzemy każdy element zbioru $A$ (tym podzbiorem jest cały zbiór $A$ ),
jest $n$ wszystkich podzbiorów jednoelementowych zbioru $A$ ,
jest $\frac{n \cdot (n - 1)}{2}$ wszystkich podzbiorów dwuelementowych zbioru $A$ .

Rozumując podobnie jak w rozwiązaniu metodą dopełniania podzbiorów do całego zbioru i zasadą równoliczności, stwierdzimy też, że

jest $n$ wszystkich podzbiorów ( $n - 1$ )-elementowych zbioru $A$ ,
jest $\frac{n \cdot (n - 1)}{2}$ wszystkich podzbiorów ( $n - 2$ )-elementowych zbioru $A$ .

liczba k–elementowych podzbiorów zbioru n–elementowego

Definicja: liczba k–elementowych podzbiorów zbioru n–elementowego

Rozpatrzmy zbiór $A = \{a_{1}, a_{2}, . . ., a_{n}\}$ , który ma $n (n \geq 1)$ elementów.
Symbolem $(\begin{array}{l} n \\ k \end{array})$ oznaczamy liczbę jego wszystkich podzbiorów k–elementowych $(k \geq 0$ i $k \leq n)$ .
Zapis symboliczny $(\begin{array}{l} n \\ k \end{array})$ odczytujemy „ $n$ po $k$ ”, stąd np.:

$(\begin{array}{l} 5 \\ 2 \end{array})$ czytamy „pięć po dwa”,
$(\begin{array}{l} 7 \\ 1 \end{array})$ czytamy „siedem po jeden”,
$(\begin{array}{l} 6 \\ 0 \end{array})$ czytamy „sześć po zero”.

Stosując to oznaczenie, stwierdzimy, że:

(\begin{array}{l} n \\ 0 \end{array}) = (\begin{array}{l} n \\ n \end{array}) = 1

(\begin{array}{l} n \\ 1 \end{array}) = (\begin{array}{l} n \\ n - 1 \end{array}) = n

(\begin{array}{l} n \\ 2 \end{array}) = (\begin{array}{l} n \\ n - 2 \end{array}) = \frac{n \cdot (n - 1)}{2},

gdy $n \geq 2$
W szczególności:

(\begin{array}{l} 5 \\ 2 \end{array}) = \frac{5 \cdot 4}{2} = 10, (\begin{array}{l} 5 \\ 3 \end{array}) = 10,

(\begin{array}{l} 7 \\ 1 \end{array}) = 7, (\begin{array}{l} 7 \\ 6 \end{array}) = 7,

(\begin{array}{l} 6 \\ 0 \end{array}) = (\begin{array}{l} 6 \\ 6 \end{array}) = 1

Rozszerza się też (z czego my nie będziemy korzystać) stosowanie tego symbolu na:

podzbiór pusty zbioru pustego, przyjmując $(\begin{array}{l} 0 \\ 0 \end{array}) = 1$ ,
przypadek, gdy $k > n$ , wtedy przyjmujemy $(\begin{array}{l} n \\ k \end{array}) = 0$ .

iyyZQTCUNb_d5e363

Kombinacje

k‑elementowa kombinacja zbioru n‑elementowego

Definicja: k‑elementowa kombinacja zbioru n‑elementowego

Każdy $k$ -elementowy podzbiór zbioru $n$ -elementowego $(0 \leq k \leq n)$ nazywa się zwyczajowo $k$ -elementową kombinacją zbioru $n$ -elementowego.

Pokażemy, że liczba wszystkich $k -$ elementowych podzbiorów, które można wybrać ze zbioru $A = \{a_{1}, a_{2}, . . ., a_{n}\}$ liczącego $n$ elementów, jest równa $\frac{n!}{k! \cdot (n - k)!}$ . Przypomnijmy, że przez $(\begin{array}{l} n \\ k \end{array})$ umówiliśmy się oznaczać liczbę wszystkich możliwych $k -$ elementowych podzbiorów zbioru $A$ .

Dla dowodu zauważmy, że liczba wszystkich możliwych $k -$ elementowych ciągów utworzonych z różnych elementów zbioru $A$ jest z jednej strony równa

\underset{k czynników}{\underset{⏟}{n \cdot (n - 1) \cdot (n - 2) \cdot . . . \cdot (n - k + 1)}} = \frac{n!}{(n - k)!}

a z drugiej strony – jest równa

\underset{k czynników}{\underset{⏟}{k \cdot (k - 1) \cdot (k - 2) \cdot . . . \cdot 1}} \cdot (\begin{array}{l} n \\ k \end{array})

ponieważ w każdym z $k$ –elementowych podzbiorów zbioru $A$ możemy ustalić kolejność elementów na

k! = \underset{k czynników}{\underset{⏟}{k \cdot (k - 1) \cdot (k - 2) \cdot . . . \cdot 1}}

sposobów.
Otrzymujemy więc równość

\frac{n!}{(n - k)!} = k! \cdot (\begin{array}{l} n \\ k \end{array})

stąd

(\begin{array}{l} n \\ k \end{array}) = \frac{n!}{k! \cdot (n - k)!}

Na podstawie spostrzeżenia poczynionego powyżej mamy twierdzenie.

liczba k‑elementowych kombinacji zbioru n‑elementowego

Twierdzenie: liczba k‑elementowych kombinacji zbioru n‑elementowego

Liczba $(\begin{array}{l} n \\ k \end{array})$ wszystkich $k$ -elementowych kombinacji zbioru $n -$ elementowego jest równa

\frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n - 1) \cdot (n - 2) \cdot . . . \cdot (n - k + 1)}{k \cdot (k - 1) \cdot (k - 2) \cdot . . . \cdot 1} .

Przykład 3

Pokażemy kilka zastosowań twierdzenia o liczbie kombinacji.

Do turnieju koszykówki, rozgrywanego systemem „każdy z każdym” (bez rewanżów), zgłosiło się $12$ drużyn.
Liczba wszystkich meczów do rozegrania w tym turnieju jest zatem równa $(\begin{array}{l} 12 \\ 2 \end{array})$ , czyli $\frac{12 \cdot 11}{2} = 66$ .
Z pudełka, w którym znajduje się $20$ kul ponumerowanych od $1$ do $20$ mamy wylosować $3$ kule.
Każdy wynik takiego losowania to trzyelementowy podzbiór zbioru dwudziestoelementowego, zatem liczba sposobów, na które można to zrobić, jest równa $(\begin{array}{l} 20 \\ 3 \end{array})$ . Ta liczba jest więc równa $\frac{20!}{3! \cdot 17!} = \frac{20 \cdot 19 \cdot 18}{3 \cdot 2 \cdot 1} = 1140$ .
Na okręgu zaznaczono $11$ różnych punktów. Obliczamy, ile jest wszystkich czworokątów wypukłych, których wierzchołkami są punkty wybrane spośród tych zaznaczonych.
Ponieważ wybierając dowolne cztery z tych jedenastu punktów na dokładnie jeden sposób, połączymy je tak, aby otrzymać kolejne boki czworokąta wypukłego, więc szukana liczba wszystkich czworokątów to $(\begin{array}{l} 11 \\ 4 \end{array})$ , co jest równe $\frac{11!}{4! \cdot 7!} = \frac{11 \cdot 10 \cdot 9 \cdot 8}{4 \cdot 3 \cdot 2 \cdot 1} = 330$ .
Spośród uczniów $37 -$ osobowej klasy należy wybrać $5$ -osobową delegację.
Można to zrobić na $(\begin{array}{l} 37 \\ 5 \end{array})$ sposobów, co jest równe $\frac{37!}{5! \cdot 32!} = \frac{37 \cdot 36 \cdot 35 \cdot 34 \cdot 33}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 435 897$ (to prawie pół miliona sposobów).
W pewnej grze losowej należy wybrać $6$ liczb ze zbioru {1, 2, 3, ..., 49}. Liczba sposobów, na które można tego dokonać jest równa $(\begin{array}{l} 49 \\ 6 \end{array})$ , czyli $\frac{49!}{6! \cdot 43!} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13 983 816$ (to liczba bliska $14$ milionom).
W rozdaniu brydżowym gracz otrzymuje $13$ kart wybranych losowo z talii $52$ kart. Liczba wszystkich układów kart możliwych do otrzymania przez brydżystę jest więc równa $(\begin{array}{l} 52 \\ 13 \end{array})$ , czyli $\frac{52!}{13! \cdot 39!} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43 \cdot 42 \cdot 41 \cdot 40}{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 635 013 559 600$ (to ponad 635 miliardów układów).

Przykład 4

Rozpatrzmy równanie

x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 10

gdzie każda z liczb $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}$ jest całkowita i nieujemna.
Wykażemy, że jest $3003$ wszystkich rozwiązań tego równania.

Skorzystamy z pomysłu przedstawionego w Uwadze do podpunktu a) przykładu $13$ .
Rozpatrzmy pomocniczo wszystkie wyniki piętnastokrotnego rzutu monetą, w których wypadło dokładnie $10$ orłów. Oznaczmy przez:
$x_{1}$ – liczbę orłów uzyskanych w kolejnych rzutach do momentu, w którym wyrzucono pierwszą reszkę,
$x_{2}$ – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono pierwszą reszkę, do momentu, w którym wyrzucono drugą reszkę,
$x_{3}$ – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono drugą reszkę, do momentu, w którym wyrzucono trzecią reszkę,
$x_{4}$ – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono trzecią reszkę, do momentu, w którym wyrzucono czwartą reszkę,
$x_{5}$ – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono czwartą reszkę, do momentu, w którym wyrzucono piątą reszkę,
$x_{6}$ – liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono piątą reszkę.
Wtedy

każdemu wynikowi takiego rzutu monetą odpowiada dokładnie jeden ciąg $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}),$
każdemu ciągowi $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6})$ odpowiada jeden wynik piętnastokrotnego rzutu monetą, w którym wypadło dokładnie $10$ orłów.

Ponieważ jest $(\begin{array}{l} 15 \\ 10 \end{array}) = \frac{15!}{10! \cdot 5!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 3003$ wszystkich wyników piętnastokrotnego rzutu monetą, w których wypadło dokładnie $10$ orłów, więc również tyle jest rozwiązań równania $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 10$ w nieujemnych liczbach całkowitych.
Rozumując podobnie, można też wykazać, że równanie $x_{1} + x_{2} + x_{3} + . . . + x_{n} = k$ , gdzie $k$ jest dodatnią liczbą całkowitą, a każda z liczb $x_{1}, x_{2}, x_{3}, . . ., x_{n}$ jest całkowita i nieujemna, ma dokładnie $(\begin{array}{l} n + k - 1 \\ k \end{array})$ rozwiązań.

iyyZQTCUNb_d5e542

Współczynniki dwumianowe, wzór dwumianowy Newtona

Przykład 5

Wykażemy, że dla dowolnej liczby rzeczywistej $x$ :
${(x + 1)}^{4} = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1$

sposób $I$ (algebraiczny)
Zapisujemy równość
${(x + 1)}^{4} = (x + 1) \cdot (x + 1) \cdot (x + 1) \cdot (x + 1)$ .
Po wymnożeniu wyrażeń zapisanych w nawiasach po prawej stronie tej równości i pogrupowaniu wyrazów podobnych otrzymamy wyrażenie (wielomian zmiennej $x$ ), w którym wystąpią jednomiany zmiennej $x$ .
Czynność taką można wykonać, korzystając ze wzoru na sześcian sumy:
${(x + 1)}^{4} = ((x + 1) \cdot (x + 1) \cdot (x + 1)) \cdot (x + 1) = {(x + 1)}^{3} \cdot (x + 1) = (x^{3} + 3 x^{2} + 3 x + 1) \cdot (x + 1) =$ $= (x^{3} + 3 x^{2} + 3 x + 1) \cdot x + (x^{3} + 3 x^{2} + 3 x + 1) \cdot 1 =$ $x^{4} + 3 x^{3} + 3 x^{2} + x + x^{3} + 3 x^{2} + 3 x + 1 = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1$ lub ze wzoru skróconego mnożenia na kwadrat sumy:
${(x + 1)}^{4} = {({(x + 1)}^{2})}^{2} = {(x^{2} + 2 x + 1)}^{2} = {(x^{2} + (2 x + 1))}^{2} = {(x^{2})}^{2} + 2 \cdot x^{2} \cdot (2 x + 1) + {(2 x + 1)}^{2} =$ $= x^{4} + 4 x^{3} + 2 x^{2} + 4 x^{2} + 4 x + 1 = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1 .$
sposób $II$ (kombinatoryczny)
Zauważmy, że mnożąc wyrażenia wybierane z każdego z kolejnych nawiasów iloczynu
$(x + 1) \cdot (x + 1) \cdot (x + 1) \cdot (x + 1),$ dostaniemy za każdym razem mnożenie czterech czynników. Wynikiem każdego takiego mnożenia jest wyrażenie $x^{k}$ , gdzie $k$ jest równe $4, 3, 2, 1$ lub $0$ . Wykonajmy więc wszystkie możliwe mnożenia wyrażeń wybieranych z kolejnych nawiasów – możemy to zrobić na $2^{4} = 16$ sposobów.
Rozróżniamy pięć przypadków:

ze wszystkich nawiasów wybraliśmy $x -$ można to zrobić na jeden sposób, a w wyniku otrzymamy $x^{4}$ , co można też zapisać jako $(\begin{array}{l} 4 \\ 4 \end{array}) \cdot x^{4} \cdot 1^{0}$ ,
z dokładnie trzech nawiasów wybraliśmy $x -$ wtedy z dokładnie jednego nawiasu wybraliśmy $1$ , a więc można to zrobić na $4$ sposoby. Zatem łącznie otrzymamy $4 x^{3}$ , co można też zapisać jako $(\begin{array}{l} 4 \\ 3 \end{array}) \cdot x^{3} \cdot 1^{1}$ ,
z dokładnie dwóch nawiasów wybraliśmy $x$ – można to zrobić na $\frac{4 \cdot 3}{2} = 6$ sposobów. Łącznie otrzymamy więc $6 x^{2}$ , co można też zapisać jako $(\begin{array}{l} 4 \\ 2 \end{array}) \cdot x^{2} \cdot 1^{2}$ ,
z dokładnie jednego nawiasu wybraliśmy $x -$ można to zrobić na $4$ sposoby. Łącznie otrzymamy więc $4 x$ , co można też zapisać jako $(\begin{array}{l} 4 \\ 1 \end{array}) \cdot x^{1} \cdot 1^{3}$ ,
z żadnego z nawiasów nie wybraliśmy $x -$ można to zrobić na $1$ sposób. Wtedy z każdego z nawiasów musimy wybrać jedynkę, więc w wyniku mnożenia otrzymamy $1$ , co można też zapisać jako $(\begin{array}{l} 4 \\ 0 \end{array}) \cdot x^{0} \cdot 1^{4}$ .
Ostatecznie stwierdzamy, że
${(x + 1)}^{4} = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1 .$ Otrzymaną tożsamość możemy też zapisać w postaci
${(x + 1)}^{4} = (\begin{array}{l} 4 \\ 4 \end{array}) \cdot x^{4} \cdot 1^{0} + (\begin{array}{l} 4 \\ 3 \end{array}) \cdot x^{3} \cdot 1^{1} + (\begin{array}{l} 4 \\ 2 \end{array}) \cdot x^{2} \cdot 1^{2} + (\begin{array}{l} 4 \\ 1 \end{array}) \cdot x^{1} \cdot 1^{3} + (\begin{array}{l} 4 \\ 0 \end{array}) \cdot x^{0} \cdot 1^{4}$

Przykład 6

Wykażemy, że dla dowolnej liczby rzeczywistej $x$ :
${(x + 1)}^{5} = x^{5} + 5 x^{4} + 10 x^{3} + 10 x^{2} + 5 x + 1$ .

sposób $I$ (algebraiczny)
${(x + 1)}^{5} = {(x + 1)}^{4} \cdot (x + 1) = (x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1) \cdot (x + 1)$ $= x^{5} + 4 x^{4} + 6 x^{3} + 4 x^{2} + x + x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1 =$ $x^{5} + 5 x^{4} + 10 x^{3} + 10 x^{2} + 5 x + 1$ .
sposób $II$ (kombinatoryczny)
Zauważmy, że mnożąc wyrażenia wybierane z każdego z kolejnych nawiasów iloczynu
$(x + 1) \cdot (x + 1) \cdot (x + 1) \cdot (x + 1) \cdot (x + 1)$
dostaniemy za każdym razem do pomnożenia pięć czynników, przy czym każdy z nich to x albo 1. Zatem wynikiem każdego takiego mnożenia jest wyrażenie $x^{k}$ , gdzie k jest równe $5, 4, 3, 2, 1$ lub $0$ . Wykonajmy więc wszystkie możliwe mnożenia wyrażeń wybieranych z kolejnych nawiasów – możemy to zrobić na $2^{5} = 32$ sposoby.
Rozróżniamy sześć przypadków:

ze wszystkich nawiasów wybraliśmy $x -$ można to zrobić na jeden sposób, a w wyniku otrzymamy $x^{5}$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 5 \end{array}) \cdot x^{5} \cdot 1^{0}$ ,
z dokładnie czterech nawiasów wybraliśmy $x -$ wtedy z dokładnie jednego nawiasu wybraliśmy $1$ , a więc można to zrobić na $5$ sposobów. Zatem łącznie otrzymamy $5 x^{4}$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 4 \end{array}) \cdot x^{4} \cdot 1^{1}$ ,
z dokładnie trzech nawiasów wybraliśmy $x -$ można to zrobić na $(\begin{array}{l} 5 \\ 3 \end{array}) = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2} = 10$ sposobów. Łącznie otrzymamy więc $10 x^{3}$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 3 \end{array}) \cdot x^{3} \cdot 1^{2}$ ,
z dokładnie dwóch nawiasów wybraliśmy $x -$ można to zrobić na $\frac{5 \cdot 4}{2} = 10$ sposobów. Łącznie otrzymamy więc $10 x^{2}$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 2 \end{array}) \cdot x^{3} \cdot 1^{2}$ ,
z dokładnie jednego nawiasu wybraliśmy $x -$ można to zrobić na 5 sposobów. Łącznie otrzymamy więc $5 x$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 1 \end{array}) \cdot x^{1} \cdot 1^{4}$ ,
z żadnego z nawiasów nie wybraliśmy x – można to zrobić na $1$ sposób. Wtedy z każdego z nawiasów musimy wybrać jedynkę, więc w wyniku mnożenia otrzymamy $1$ , co można też zapisać jako $(\begin{array}{l} 5 \\ 0 \end{array}) \cdot x^{0} \cdot 1^{5}$ .
Ostatecznie stwierdzamy, że
${(x + 1)}^{5} = x^{5} + 5 x^{4} + 10 x^{3} + 10 x^{2} + 5 x + 1$ .
Otrzymaną tożsamość możemy też zapisać w postaci
${(x + 1)}^{5} = (\begin{array}{l} 5 \\ 5 \end{array}) \cdot x^{5} \cdot 1^{0} + (\begin{array}{l} 5 \\ 4 \end{array}) \cdot x^{4} \cdot 1^{1} + (\begin{array}{l} 5 \\ 3 \end{array}) \cdot x^{3} \cdot 1^{2} + (\begin{array}{l} 5 \\ 2 \end{array}) \cdot x^{2} \cdot 1^{3} + (\begin{array}{l} 5 \\ 1 \end{array}) \cdot x^{1} \cdot 1^{4} + (\begin{array}{l} 5 \\ 0 \end{array}) \cdot x^{0} \cdot 1^{5}$ .

Przykład 7

Wykażemy, że dla dowolnej liczby rzeczywistej $x$ :

{(x + 1)}^{7} = x^{7} + 7 x^{6} + 21 x^{5} + 35 x^{4} + 35 x^{3} + 21 x^{2} + 7 x + 1

sposób $I$
Najpierw pokazujemy, że
${(x + 1)}^{6} = {(x + 1)}^{5} \cdot (x + 1) = (x^{5} + 5 x^{4} + 10 x^{3} + 10 x^{2} + 5 x + 1) \cdot (x + 1) = x^{6} + 6 x^{5} + 15 x^{4} + 20 x^{3} + 15 x^{2} + 6 x + 1$ .
Stąd
${(x + 1)}^{7} = {(x + 1)}^{6} \cdot (x + 1) = (x^{6} + 6 x^{5} + 15 x^{4} + 20 x^{3} + 15 x^{2} + 6 x + 1) \cdot (x + 1) =$

$= x^{7} + 7 x^{6} + 21 x^{5} + 35 x^{4} + 35 x^{3} + 21 x^{2} + 7 x + 1$ .

sposób $II$
Korzystając z pomysłów przedstawionych w sposobie $II$ rozwiązania poprzednich podpunktów, pokazujemy, że
${(x + 1)}^{7} =$

$= (\begin{array}{l} 7 \\ 7 \end{array}) \cdot x^{7} \cdot 1^{0} + (\begin{array}{l} 7 \\ 6 \end{array}) \cdot x^{6} \cdot 1^{1} + (\begin{array}{l} 7 \\ 5 \end{array}) \cdot x^{5} \cdot 1^{2} + (\begin{array}{l} 7 \\ 4 \end{array}) \cdot x^{4} \cdot 1^{3} + (\begin{array}{l} 7 \\ 3 \end{array}) \cdot x^{3} \cdot 1^{4} + (\begin{array}{l} 7 \\ 2 \end{array}) \cdot x^{2} \cdot 1^{5} + (\begin{array}{l} 7 \\ 1 \end{array}) \cdot x^{1} \cdot 1^{6} + (\begin{array}{l} 7 \\ 0 \end{array}) \cdot x^{0} \cdot 1^{7}$ .
Ponieważ $(\begin{array}{l} 7 \\ 7 \end{array}) = (\begin{array}{l} 7 \\ 0 \end{array}) = 1$ , $(\begin{array}{l} 7 \\ 6 \end{array}) = (\begin{array}{l} 7 \\ 1 \end{array}) = 7$ , $(\begin{array}{l} 7 \\ 5 \end{array}) = (\begin{array}{l} 7 \\ 2 \end{array}) = \frac{7 \cdot 6}{2} = 21$ , $(\begin{array}{l} 7 \\ 4 \end{array}) = (\begin{array}{l} 7 \\ 3 \end{array}) = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$ , więc otrzymujemy
${(x + 1)}^{7} = x^{7} + 7 x^{6} + 21 x^{5} + 35 x^{4} + 35 x^{3} + 21 x^{2} + 7 x + 1$ .
Rozumując podobnie jak w sposobie $II$ rozwiązań przedstawionych w powyższym przykładzie, można pokazać, że dla dowolnej dodatniej liczby całkowitej $n$ oraz dowolnych liczb całkowitych $a$ oraz $b$ prawdziwa jest równość
${(a + b)}^{n} = (\begin{array}{l} n \\ 0 \end{array}) a^{n} + (\begin{array}{l} n \\ 1 \end{array}) a^{n - 1} b + (\begin{array}{l} n \\ 2 \end{array}) a^{n - 2} b^{2} + . . . + (\begin{array}{l} n \\ n - 1 \end{array}) a^{1} b^{n - 1} + (\begin{array}{l} n \\ n \end{array}) b^{n}$ .
Wzór ten jest nazywany wzorem dwumianowym Newtona.
W szczególności dla $a = b = 1$ otrzymujemy
$2^{n} = (\begin{array}{l} n \\ 0 \end{array}) + (\begin{array}{l} n \\ 1 \end{array}) + (\begin{array}{l} n \\ 2 \end{array}) + . . . + (\begin{array}{l} n \\ n - 1 \end{array}) + (\begin{array}{l} n \\ n \end{array})$ .
Otrzymana równość uzasadnia znany nam już fakt, że liczba wszystkich podzbiorów zbioru $n$ –elementowego jest równa $2^{n}$ .

Podzbiory zbioru skończonego (treść podstawowa)

Zadania

Podzbiory zbioru skończonego (treść rozszerzona)

Liczba wszystkich podzbiorów zbioru skończonego

Liczba kombinacji

Kombinacje

Współczynniki dwumianowe, wzór dwumianowy Newtona