Symbol Newtona i trójkąt Pascala - własności n po k z dowodami

Klasa 3 liceum i technikum

Symbol Newtona $\binom{n}{k}$, czytany „en po ka”, to liczba $\tfrac{n!}{k!\,(n-k)!}$ określona dla liczb całkowitych $0 \le k \le n$. Oznacza liczbę $k$-elementowych podzbiorów zbioru $n$-elementowego, czyli liczbę kombinacji. Nazywa się go też współczynnikiem dwumianowym, bo te same liczby są współczynnikami w rozwinięciu dwumianu Newtona $(a + b)^n$. Na przykład $\binom{5}{2} = \tfrac{5!}{2! \cdot 3!} = 10$.

W tej lekcji poznajemy własności symbolu Newtona i ich dowody. Każdą własność da się udowodnić na dwa sposoby: rachunkowo (ze wzoru z silniami) i kombinatorycznie (licząc ten sam zbiór na dwa sposoby). Ten drugi sposób jest zwykle krótszy i pokazuje, dlaczego wzór jest prawdziwy.

Jak obliczyć n po k

W liczniku zostawiamy $k$ czynników malejących od $n$, w mianowniku $k!$ - reszta silni się skraca:

$\binom{n}{k} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k!}.$

Przykład 1. $\binom{14}{4} = \dfrac{14 \cdot 13 \cdot 12 \cdot 11}{4 \cdot 3 \cdot 2 \cdot 1}$. Skracamy: $\tfrac{12}{4 \cdot 3} = 1$, a $\tfrac{14}{2} = 7$, więc zostaje $7 \cdot 13 \cdot 11 = 1001$.

Przykład 2. $\binom{25}{23} = \binom{25}{2} = \dfrac{25 \cdot 24}{2} = 300$ - z symetrii liczymy dwa czynniki zamiast dwudziestu trzech.

Wynik zawsze jest liczbą naturalną - jest przecież liczbą podzbiorów. Jeśli po skróceniu wychodzi ułamek, w rachunku jest błąd.

Symetria: n po k = n po (n − k)

Dowód rachunkowy. Podstawiamy $n - k$ w miejsce $k$:

$\binom{n}{n-k} = \frac{n!}{(n-k)! \cdot (n - (n-k))!} = \frac{n!}{(n-k)! \cdot k!} = \binom{n}{k}.$

Dowód kombinatoryczny. Wybrać $k$ osób do delegacji spośród $n$ to dokładnie to samo, co wybrać $n - k$ osób, które nie pojadą. Każdemu wyborowi „kto jedzie” odpowiada dokładnie jeden wybór „kto zostaje”, więc obu wyborów jest tyle samo.

Stąd biorą się wartości szczególne: $\binom{n}{n} = \binom{n}{0} = 1$ (jest jeden zbiór pusty i jeden zbiór „wszystko”) oraz $\binom{n}{n-1} = \binom{n}{1} = n$.

Reguła Pascala

Dowód rachunkowy. Sprowadzamy oba ułamki do wspólnego mianownika $(k+1)!\,(n-k)!$:

$\binom{n}{k} + \binom{n}{k+1} = \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k+1)!\,(n-k-1)!} = \frac{n! \cdot (k+1)}{(k+1)!\,(n-k)!} + \frac{n! \cdot (n-k)}{(k+1)!\,(n-k)!}.$

Wyłączamy $n!$ w liczniku: $(k+1) + (n-k) = n + 1$, a $n! \cdot (n+1) = (n+1)!$:

$\binom{n}{k} + \binom{n}{k+1} = \frac{(n+1)!}{(k+1)!\,(n-k)!} = \binom{n+1}{k+1}.$

Dowód kombinatoryczny. W klasie jest $n + 1$ osób, w tym Kasia. Wybieramy delegację $(k+1)$-osobową - na $\binom{n+1}{k+1}$ sposobów. Policzmy te same delegacje inaczej, dzieląc je na dwa rozłączne przypadki:

• delegacje z Kasią - Kasia już jest, dobieramy $k$ osób z pozostałych $n$: $\binom{n}{k}$;
• delegacje bez Kasi - wszystkie $k + 1$ osób z pozostałych $n$: $\binom{n}{k+1}$.

Z reguły dodawania obie strony liczą to samo. Na przykład $\binom{5}{2} + \binom{5}{3} = 10 + 10 = 20 = \binom{6}{3}$.

Trójkąt Pascala

Jeśli symbole Newtona ułożymy wierszami - w wierszu $n$ liczby $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ - powstaje trójkąt Pascala. Reguła Pascala mówi, że każda liczba w środku trójkąta jest sumą dwóch liczb stojących bezpośrednio nad nią, a każdy wiersz zaczyna się i kończy jedynką. Dzięki temu kolejne wiersze dopisujemy bez liczenia silni.

W trójkącie widać wszystkie własności naraz:

• symetria - każdy wiersz czyta się tak samo od lewej i od prawej, bo $\binom{n}{k} = \binom{n}{n-k}$;
• druga przekątna to kolejne liczby naturalne $1, 2, 3, 4, \ldots$, bo $\binom{n}{1} = n$;
• trzecia przekątna to $1, 3, 6, 10, 15, 21$, czyli $\binom{n}{2}$ - liczba par (uścisków dłoni) wśród $n$ osób; to tak zwane liczby trójkątne;
• wiersz $n$ to współczynniki rozwinięcia $(a + b)^n$, np. $(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$.

Trójkąt opisał Blaise Pascal w 1654 roku, ale znali go wcześniej matematycy chińscy, perscy i włoscy - stąd inne nazwy, np. trójkąt Tartaglii.

Suma wiersza: 2 do potęgi n

Dodajmy liczby w kolejnych wierszach trójkąta:

Dowód kombinatoryczny. Policzmy wszystkie podzbiory zbioru $n$-elementowego na dwa sposoby.

• Sposób 1 (reguła mnożenia). O każdym elemencie decydujemy osobno: należy do podzbioru albo nie - $2$ możliwości. Decyzji jest $n$, więc podzbiorów jest $2^n$.
• Sposób 2 (reguła dodawania). Dzielimy podzbiory według liczby elementów: $\binom{n}{0}$ podzbiorów pustych, $\binom{n}{1}$ jednoelementowych, …, $\binom{n}{n}$ z wszystkimi elementami. Razem $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}$.

Oba sposoby liczą to samo, więc suma wiersza wynosi $2^n$. Na przykład zbiór $\{a, b, c, d, e\}$ ma $2^5 = 32$ podzbiory, w tym $\binom{5}{2} = 10$ dwuelementowych.

Równania z symbolem Newtona

Niewiadomą jest $n$, więc $n$ musi być liczbą naturalną i spełniać $n \ge k$ dla każdego symbolu $\binom{n}{k}$ w równaniu. Symbol rozpisujemy jako iloczyn i dostajemy zwykłe równanie wielomianowe.

Przykład 3. Rozwiąż równanie $\binom{n}{2} = 28$.

Krok 1. Dziedzina: $n \in \mathbb{N}$, $n \ge 2$.

Krok 2. Rozpisujemy: $\tfrac{n(n-1)}{2} = 28$, czyli $n^2 - n - 56 = 0$.

Krok 3. Rozwiązujemy: $\Delta = 1 + 224 = 225$, $\sqrt{\Delta} = 15$, więc $n = \tfrac{1 + 15}{2} = 8$ lub $n = \tfrac{1 - 15}{2} = -7$.

Krok 4. Sprawdzamy dziedzinę: $-7$ odrzucamy. Odpowiedź: $n = 8$. Interpretacja: w grupie $8$ osób jest $28$ par.

Przykład 4. Rozwiąż równanie $\binom{n}{1} + \binom{n}{2} = 21$.

Dziedzina $n \ge 2$. Rozpisujemy: $n + \tfrac{n(n-1)}{2} = 21$, mnożymy przez $2$: $2n + n^2 - n = 42$, czyli $n^2 + n - 42 = 0$, skąd $(n + 7)(n - 6) = 0$. Zostaje $n = 6$. Sprawdzenie: $6 + 15 = 21$. Krócej - z reguły Pascala $\binom{n}{1} + \binom{n}{2} = \binom{n+1}{2}$, więc $\tfrac{(n+1)n}{2} = 21$ i $n = 6$.

Typowe błędy

• Odczytywanie $\binom{n}{k}$ jako ułamka. $\binom{8}{2} = 28$, a nie $4$.
• Pełne silnie zamiast skracania. $\binom{14}{4}$ wymaga czterech czynników w liczniku, nie $14!$.
• Zapomniana dziedzina w równaniu. Rozwiązanie ujemne albo mniejsze od $k$ odrzucamy.
• Reguła Pascala z błędnymi indeksami. Dodajemy sąsiednie symbole z tego samego wiersza: $\binom{n}{k} + \binom{n}{k+1}$, a wynik ma górny indeks $n + 1$ i dolny $k + 1$ (większy z dwóch).

Najczęstsze pytania

Co to jest symbol Newtona? To liczba $\binom{n}{k} = \tfrac{n!}{k!\,(n-k)!}$, czytana „en po ka”, równa liczbie $k$-elementowych podzbiorów zbioru $n$-elementowego. Jest też współczynnikiem przy $a^{n-k}b^k$ w rozwinięciu $(a + b)^n$.

Jak obliczyć n po k? Zapisz w liczniku $k$ kolejnych liczb od $n$ w dół, w mianowniku $k!$, i skróć. Np. $\binom{7}{3} = \tfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$. Gdy $k$ jest bliskie $n$, użyj symetrii: $\binom{50}{48} = \binom{50}{2} = 1225$.

Ile wynosi n po 0?$\binom{n}{0} = 1$ dla każdego $n \ge 0$ - jest dokładnie jeden podzbiór pusty. Ze wzoru: $\tfrac{n!}{0! \cdot n!} = 1$, bo $0! = 1$. W szczególności $\binom{0}{0} = 1$.

Ile wynosi n po 2?$\binom{n}{2} = \tfrac{n(n-1)}{2}$, np. $\binom{10}{2} = 45$. Tyle jest par w zbiorze $n$-elementowym.

Do czego służy trójkąt Pascala? Pozwala szybko wypisać symbole Newtona bez liczenia silni: wiersz $n$ zawiera liczby $\binom{n}{0}, \ldots, \binom{n}{n}$, które są jednocześnie współczynnikami rozwinięcia $(a + b)^n$. Każdą liczbę w środku dostajemy, dodając dwie liczby nad nią.

Ile wynosi suma liczb w n-tym wierszu trójkąta Pascala?$2^n$. Suma $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}$ to liczba wszystkich podzbiorów zbioru $n$-elementowego, a tych jest $2^n$, bo o każdym elemencie decydujemy „bierzemy albo nie”.

Przećwicz

• Symbol Newtona i trójkąt Pascala - zadania → - obliczanie ze skracaniem i symetrią, upraszczanie wyrażeń z silnią, równania, reguła Pascala, liczba podzbiorów i dowody tożsamości (zadania z pełnym rozwiązaniem krok po kroku).
• Cały zestaw: kombinatoryka - zadania z rozwiązaniami →

Podsumowanie

• $\binom{n}{k} = \tfrac{n!}{k!\,(n-k)!}$ to liczba $k$-elementowych podzbiorów; liczymy ją przez skracanie.
• Symetria $\binom{n}{k} = \binom{n}{n-k}$: wybrać, kto jedzie, to wybrać, kto zostaje.
• Reguła Pascala $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$: delegacje z Kasią i bez Kasi.
• Trójkąt Pascala: każda liczba to suma dwóch nad nią; wiersz $n$ sumuje się do $2^n$.
• W równaniach z symbolem Newtona $n$ jest liczbą naturalną, $n \ge k$ - pozostałe rozwiązania odrzucamy.

Zobacz też

• Dwumian Newtona - następna lekcja: wiersze trójkąta Pascala jako współczynniki rozwinięcia $(a + b)^n$.
• Kombinacje - skąd się bierze wzór na $\binom{n}{k}$.
• Wzór Newtona - symbol Newtona i trójkąt Pascala - zestawienie wzorów i tabela współczynników dla $n$ od $0$ do $7$.