Suma współczynników dwumianowych
gdzie n to liczba naturalna, a sumowanie obejmuje wszystkie symbole Newtona od C(n,0) do C(n,n)
Czym jest suma współczynników dwumianowych?
Suma współczynników dwumianowych to jedna z najważniejszych tożsamości kombinatorycznych. Mówi, że suma wszystkich symboli Newtona w n-tym wierszu trójkąta Pascala jest równa 2n. Innymi słowy, jeśli dodamy do siebie C(n,0) + C(n,1) + C(n,2) + ... + C(n,n), zawsze otrzymamy potęgę dwójki.
Wynik ten ma piękną interpretację kombinatoryczną: 2n to łączna liczba wszystkich podzbiorów zbioru n-elementowego, wliczając zbiór pusty i cały zbiór. Każdy element może być albo wybrany, albo pominięty (2 możliwości), a te decyzje podejmujemy niezależnie dla n elementów, co daje 2 · 2 · ... · 2 = 2n podzbiorów.
Elementy wzoru
Symbol sumy - sumujemy po k od 0 do n, czyli po wszystkich możliwych rozmiarach podzbiorów.
Symbol Newtona - liczba k-elementowych podzbiorów zbioru n-elementowego. Kolejne składniki sumy to C(n,0), C(n,1), ..., C(n,n).
Liczba elementów zbioru. Musi to być liczba naturalna (n ≥ 0). Wyznacza wiersz trójkąta Pascala, którego elementy sumujemy.
Wynik sumy - łączna liczba wszystkich podzbiorów zbioru n-elementowego (wliczając zbiór pusty i cały zbiór).
Interpretacja i dowody
Lewa strona liczy podzbiory według rozmiaru: C(n,0) pustych + C(n,1) jednoelementowych + ... + C(n,n) pełnych = wszystkie podzbiory. Prawa strona liczy je inaczej: dla każdego elementu decydujemy "bierz" lub "nie bierz" (2 opcje), więc jest 2n podzbiorów. Oba sposoby liczą to samo.
Dwumian Newtona mówi, że (a+b)n = suma C(n,k) · ak · bn-k. Podstawiając a = 1 i b = 1 otrzymujemy (1+1)n = suma C(n,k) · 1 · 1 = suma C(n,k) = 2n.
W trójkącie Pascala suma elementów każdego wiersza jest podwojeniem sumy wiersza poprzedniego. Wiersz 0: suma = 1 = 20. Wiersz 1: suma = 2 = 21. Wiersz 2: suma = 4 = 22. Wzór potwierdzony indukcyjnie.
Wizualizacja
Poniższy wykres zestawia sumę elementów wiersza trójkąta Pascala (czyli sumę symboli Newtona) z odpowiadającą jej potęgą 2n. Obie wartości pokrywają się idealnie, co potwierdza tożsamość.
Potęga dwójki rośnie wykładniczo: 1, 2, 4, 8, 16, 32, 64, ...
Zbiór 10-elementowy ma 210 = 1 024 podzbiory
Kiedy stosować ten wzór?
- Zliczanie wszystkich podzbiorów - gdy pytanie brzmi "ile jest łącznie podzbiorów zbioru n-elementowego?", odpowiedź to 2n
- Weryfikacja trójkąta Pascala - sprawdzenie, czy suma elementów wiersza daje 2n, pozwala szybko wykryć błędy w obliczeniach
- Rachunek prawdopodobieństwa - obliczanie przestrzeni próby w eksperymentach z wyborem podzbiorów (np. ile jest możliwych zestawów odpowiedzi w teście wielokrotnego wyboru)
- Upraszczanie sum kombinatorycznych - gdy w wyrażeniu pojawia się suma wszystkich symboli Newtona, można ją zastąpić przez 2n
Przykłady obliczeniowe
Przykład 1: Weryfikacja dla n = 4
Zadanie: Sprawdź, że suma symboli Newtona w wierszu n = 4 trójkąta Pascala wynosi 24 = 16.
Rozwiązanie:
Wiersz n = 4 trójkąta Pascala to: 1, 4, 6, 4, 1. Obliczamy sumę:
Odpowiedź: Suma wynosi 16 = 24, co potwierdza wzór.
Przykład 2: Liczba podzbiorów
Zadanie: Ile łącznie podzbiorów (wliczając pusty i pełny) ma zbiór {a, b, c, d, e}?
Rozwiązanie:
Zbiór ma n = 5 elementów. Łączna liczba podzbiorów to:
Możemy to rozłożyć według rozmiaru podzbiorów:
Odpowiedź: Zbiór 5-elementowy ma 32 podzbiory.
Przykład 3: Podzbiory niepuste
Zadanie: Ile niepustych podzbiorów ma zbiór 8-elementowy?
Rozwiązanie:
Wszystkich podzbiorów jest 28. Odejmujemy 1 (zbiór pusty):
Odpowiedź: Zbiór 8-elementowy ma 255 niepustych podzbiorów.
Przykład 4: Test wielokrotnego wyboru
Zadanie: W teście jest 6 pytań. Na każde pytanie można odpowiedzieć "tak" lub "nie". Ile jest różnych zestawów odpowiedzi?
Rozwiązanie:
Każdy zestaw odpowiedzi to podzbiór pytań, na które odpowiedziano "tak". Mamy n = 6 pytań:
Alternatywnie: dla każdego pytania mamy 2 opcje (tak/nie), a decyzje są niezależne:
Odpowiedź: Istnieje 64 różne zestawy odpowiedzi.
Częste błędy
Pomijanie zbioru pustego lub pełnego
Suma C(n,0) + C(n,1) + ... + C(n,n) = 2n obejmuje zbiór pusty (C(n,0) = 1) i cały zbiór (C(n,n) = 1). Jeśli pytanie dotyczy podzbiorów właściwych lub niepustych, musisz odjąć odpowiednie składniki.
Mylenie 2n z 2n
Suma współczynników to 2n (potęga), a nie 2n (podwojenie). Dla n = 10 mamy 210 = 1 024 podzbiorów, nie 20. Różnica rośnie dramatycznie z n.
Sumowanie od k = 1 zamiast k = 0
Wzór wymaga sumowania od k = 0 (nie od k = 1). Suma od k = 1 do n daje 2n - 1 (bez zbioru pustego). Zawsze zwracaj uwagę na granice sumowania.
Stosowanie wzoru do sum częściowych
Wzór dotyczy sumy WSZYSTKICH symboli Newtona w wierszu. Suma częściowa, np. C(n,0) + C(n,1) + C(n,2), NIE jest równa prostej potędze dwójki. Do sum częściowych nie ma tak prostego wzoru zamkniętego.
Porady i wskazówki
Myśl o podzbiorach: Gdy widzisz 2n w kontekście kombinatoryki, pomyśl "podzbiory". Zbiór n-elementowy ma 2n podzbiorów, bo dla każdego z n elementów podejmujesz binarną decyzję: wziąć lub nie wziąć.
Kontrola w trójkącie Pascala: Po wyznaczeniu wiersza trójkąta Pascala sprawdź, czy suma elementów daje 2n. Na przykład wiersz n = 5: 1+5+10+10+5+1 = 32 = 25. Jeśli suma się nie zgadza, masz błąd.
Potęgi 2 warto znać: 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16, 25 = 32, 26 = 64, 27 = 128, 28 = 256, 29 = 512, 210 = 1 024. Te wartości pojawiają się często na maturze.
Powiązana tożsamość: Podstawiając a = 1, b = -1 do dwumianu Newtona, otrzymujemy sumę naprzemienną: C(n,0) - C(n,1) + C(n,2) - ... = 0. To oznacza, że suma współczynników na pozycjach parzystych równa się sumie na nieparzystych.
Przypadki szczególne
Zbiór pusty (n = 0)
Zbiór pusty ma dokładnie jeden podzbiór - samego siebie (zbiór pusty). Suma zawiera jeden składnik: C(0,0) = 1.
Podzbiory niepuste
Liczbę niepustych podzbiorów otrzymujemy, odejmując 1 od pełnej sumy (usuwając zbiór pusty).
Przykład: Zbiór 5-elementowy ma 25 - 1 = 31 niepustych podzbiorów.
Suma naprzemienna
Podstawiając a = 1, b = -1 do dwumianu Newtona, otrzymujemy sumę naprzemienną symboli Newtona, która wynosi 0.
Przykład: C(3,0) - C(3,1) + C(3,2) - C(3,3) = 1 - 3 + 3 - 1 = 0.
Podzbiory właściwe
Podzbiory właściwe to wszystkie podzbiory oprócz całego zbioru. Ich liczba to 2n - 1 (odejmujemy sam zbiór pełny).
Przykład: Zbiór {a, b, c} ma 23 - 1 = 7 podzbiorów właściwych.