Podzbiory zbioru skończonego (treść rozszerzona) - Zintegrowana Platforma Edukacyjna

W tym materiale zawarte są wiadomości na temat sposobów wyznaczania podzbiorów zbioru skończonego. Poznasz:

wzór na liczbę podzbiorów zbioru n – elementowego,
definicję kombinacji,
wzór na liczbę k – elementowych kombinacji zbioru n – elementowego,
wzór dwumianowy Newtona.

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 zbiór dziewięcioelementowy ma $2^{9} = 512$ podzbiorów.

Ustalając liczbę podzbiorów, można zauważyć, ż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}, \dots, 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}, \dots, 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 \dots \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

Często spotykamy sie 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}, \dots, a_{n}\}$ elementów. Wtedy:

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$ .

Zgodnie z metodą dopełniania podzbiorów do całego zbioru i zasadą równoliczności, możemy stwierdzić 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}, \dots, a_{n}\}$ , który ma $n (n ⩾ 1)$ elementów.

Symbolem $(\begin{matrix} n \\ k \end{matrix})$ oznaczamy liczbę jego wszystkich podzbiorów $k$ – elementowych $(k ⩾ 0)$ i $(k ⩽ n)$ .

Zapis symboliczny $(\begin{matrix} n \\ k \end{matrix})$ odczytujemy „ $n$ po $k$ ”, stąd np.:

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

Stosując to oznaczenie, stwierdzimy, że:

(\begin{matrix} n \\ 0 \end{matrix}) = (\begin{matrix} n \\ n \end{matrix}) = 1

(\begin{matrix} n \\ 1 \end{matrix}) = (\begin{matrix} n \\ n - 1 \end{matrix}) = n

(\begin{matrix} n \\ 2 \end{matrix}) = (\begin{matrix} n \\ n - 2 \end{matrix}) = \frac{n \cdot (n - 1)}{2}

gdy $n ⩾ 2$ .

W szczególności:

(\begin{matrix} 5 \\ 2 \end{matrix}) = \frac{5 \cdot 4}{2} = 10

(\begin{matrix} 5 \\ 3 \end{matrix}) = 10

(\begin{matrix} 7 \\ 1 \end{matrix}) = 7

(\begin{matrix} 7 \\ 6 \end{matrix}) = 7

(\begin{matrix} 6 \\ 0 \end{matrix}) = (\begin{matrix} 6 \\ 6 \end{matrix}) = 1

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

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

Kombinacje

k

–elementowa kombinacja zbioru

n

– elementowego

Definicja:

k

–elementowa kombinacja zbioru

n

– elementowego

Każdy $k$ – elementowy podzbiór zbioru $n$ – elementowego $(0 ⩽ k ⩽ 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}, \dots, a_{n}\}$ liczącego $n$ elementów, jest równa $\frac{n!}{k! \cdot (n - k)!}$ .

Przypomnijmy, że przez $(\begin{matrix} n \\ k \end{matrix})$ 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 \dots \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 \dots \cdot 1}} \cdot (\begin{matrix} n \\ k \end{matrix})

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 \dots \cdot 1}}

sposobów.

Otrzymujemy więc równość

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

stąd

(\begin{matrix} n \\ k \end{matrix}) = \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{matrix} n \\ k \end{matrix})$ 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 \dots \cdot (n - k + 1)}{k \cdot (k - 1) \cdot (k - 2) \cdot \dots \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{matrix} 12 \\ 2 \end{matrix})$ , 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{matrix} 20 \\ 3 \end{matrix})$ . 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{matrix} 11 \\ 4 \end{matrix})$ , 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{matrix} 37 \\ 5 \end{matrix})$ 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, \dots, 49\}$ . Liczba sposobów, na które można tego dokonać jest równa $(\begin{matrix} 49 \\ 6 \end{matrix})$ , 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} = 13983816$ (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{matrix} 52 \\ 13 \end{matrix})$ , 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} = 635013559600$ (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.

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{matrix} 15 \\ 10 \end{matrix}) = \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} + \dots + x_{n} = k$ , gdzie $k$ jest dodatnią liczbą całkowitą, a każda z liczb $x_{1}, x_{2}, x_{3}, \dots, x_{n}$ jest całkowita i nieujemna, ma dokładnie $(\begin{matrix} n + k - 1 \\ k \end{matrix})$ rozwiązań.

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{matrix} 4 \\ 4 \end{matrix}) \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{matrix} 4 \\ 3 \end{matrix}) \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{matrix} 4 \\ 2 \end{matrix}) \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{matrix} 4 \\ 1 \end{matrix}) \cdot x^{1} \cdot 1^{3}$ ,
z żadnego z nawiasów nie wybraliśmy $x$ – można to zrobić na $I$ 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{matrix} 4 \\ 0 \end{matrix}) \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{matrix} 4 \\ 4 \end{matrix}) \cdot x^{4} \cdot 1^{0} + (\begin{matrix} 4 \\ 3 \end{matrix}) \cdot x^{3} \cdot 1^{1} + (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot x^{2} \cdot 1^{2} +$
$+ (\begin{matrix} 4 \\ 1 \end{matrix}) \cdot x^{1} \cdot 1^{3} + (\begin{matrix} 4 \\ 0 \end{matrix}) \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{matrix} 5 \\ 5 \end{matrix}) \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{matrix} 5 \\ 4 \end{matrix}) \cdot x^{4} \cdot 1^{1}$ ,
z dokładnie trzech nawiasów wybraliśmy $x$ – można to zrobić na $(\begin{matrix} 5 \\ 3 \end{matrix}) = \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{matrix} 5 \\ 3 \end{matrix}) \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{matrix} 5 \\ 2 \end{matrix}) \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{matrix} 5 \\ 1 \end{matrix}) \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{matrix} 5 \\ 0 \end{matrix}) \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{matrix} 5 \\ 5 \end{matrix}) \cdot x^{5} \cdot 1^{0} + (\begin{matrix} 5 \\ 4 \end{matrix}) \cdot x^{4} \cdot 1^{1} + (\begin{matrix} 5 \\ 3 \end{matrix}) \cdot x^{3} \cdot 1^{2} +$
$+ (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot x^{2} \cdot 1^{3} + (\begin{matrix} 5 \\ 1 \end{matrix}) \cdot x^{1} \cdot 1^{4} + (\begin{matrix} 5 \\ 0 \end{matrix}) \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{matrix} 7 \\ 7 \end{matrix}) x^{7} \cdot 1^{0} + (\begin{matrix} 7 \\ 6 \end{matrix}) \cdot x^{6} \cdot 1^{1} + (\begin{matrix} 7 \\ 5 \end{matrix}) \cdot x^{5} \cdot 1^{2} + (\begin{matrix} 7 \\ 4 \end{matrix}) \cdot x^{4} \cdot 1^{3}$ $+ (\begin{matrix} 7 \\ 3 \end{matrix}) \cdot x^{3} \cdot 1^{4} + (\begin{matrix} 7 \\ 2 \end{matrix}) \cdot x^{2} \cdot 1^{5} + (\begin{matrix} 7 \\ 1 \end{matrix}) \cdot x^{1} \cdot 1^{6} + (\begin{matrix} 7 \\ 0 \end{matrix}) \cdot x^{0} \cdot 1^{7}$ .
Ponieważ $(\begin{matrix} 7 \\ 7 \end{matrix}) = (\begin{matrix} 7 \\ 0 \end{matrix}) = 1$ , $(\begin{matrix} 7 \\ 6 \end{matrix}) = (\begin{matrix} 7 \\ 1 \end{matrix}) = 7$ , $(\begin{matrix} 7 \\ 5 \end{matrix}) = (\begin{matrix} 7 \\ 2 \end{matrix}) = \frac{7 \cdot 6}{2} = 21$ , $(\begin{matrix} 7 \\ 4 \end{matrix}) = (\begin{matrix} 7 \\ 3 \end{matrix}) = \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{matrix} n \\ 0 \end{matrix}) a^{n} + (\begin{matrix} n \\ 1 \end{matrix}) a^{n - 1} b +$
$+ (\begin{matrix} n \\ 2 \end{matrix}) a^{n - 2} b^{2} + \dots + (\begin{matrix} n \\ n - 1 \end{matrix}) a^{1} b^{n - 1} + (\begin{matrix} n \\ n \end{matrix}) b^{n}$ .
Wzór ten jest nazywany wzorem dwumianowym Newtona.
W szczególności dla $a = b = 1$ otrzymujemy
$2^{n} = (\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + \dots + (\begin{matrix} n \\ n - 1 \end{matrix}) + (\begin{matrix} n \\ n \end{matrix})$ .
Otrzymana równość uzasadnia znany nam już fakt, że liczba wszystkich podzbiorów zbioru $n$ – elementowego jest równa $2^{n}$ .