Suma współczynników dwumianowych

Wszystkie symbole Newtona z jednego wiersza trójkąta Pascala dają razem 2n2^n. Tyle podzbiorów ma zbiór nn-elementowy, więc wzór pozwala policzyć je bez dodawania kolejnych składników.

∑k=0n(nk)=2n\sum_{k=0}^{n} \binom{n}{k} = 2^n

bez zbioru pustego

∑k=1n(nk)=2n−1\displaystyle \sum_{k=1}^{n} \binom{n}{k} = 2^n - 1

tylko parzyste k, dla n ≥ 1

(n0)+(n2)+…=2n−1\displaystyle \binom{n}{0} + \binom{n}{2} + \ldots = 2^{n-1}

na przykład

1+4+6+4+1=241 + 4 + 6 + 4 + 1 = 2^4
Suma przebiega po kk od 0 do nn, czyli (n0)+(n1)+…+(nn)\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}: to cały wiersz nn trójkąta Pascala. Składnik (nk)\binom{n}{k} to liczba podzbiorów kk-elementowych zbioru nn-elementowego.

Skąd się bierze ten wzór?

Weź zbiór {A,B,C,D}\{A, B, C, D\} i policz jego podzbiory na dwa sposoby. Pierwszy sposób to podział według liczby elementów: jeden podzbiór pusty, cztery jednoelementowe, sześć dwuelementowych, cztery trzyelementowe i cały zbiór. Te liczby to kolejne symbole Newtona z wiersza n=4n = 4.

Drugi sposób to decyzja o każdym elemencie osobno: bierzesz go do podzbioru albo nie. Masz dwie możliwości dla A, dwie dla B, dwie dla C i dwie dla D, a każdy układ tych decyzji daje inny podzbiór.

Oba sposoby liczą te same podzbiory, więc wyniki są równe. Tak samo jest dla zbioru nn-elementowego:

  1. (n0)+(n1)+…+(nn)=2n\displaystyle \binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n} = 2^n

Ten sam wynik daje dwumian Newtona, gdy podstawisz a=b=1a = b = 1. Każda potęga jedynki to 1, więc zostają same symbole Newtona:

  1. (1+1)n=∑k=0n(nk)⋅1n−k⋅1k\displaystyle (1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1^{n-k} \cdot 1^k
  2. 2n=∑k=0n(nk)\displaystyle 2^n = \sum_{k=0}^{n} \binom{n}{k}

W trójkącie Pascala widać to jeszcze inaczej. Każda liczba wiersza trafia do dwóch sum w wierszu pod nią (wzór Pascala), więc suma każdego wiersza jest dwa razy większa od sumy wiersza nad nim.

Jak korzystać ze wzoru krok po kroku

Ile podzbiorów co najmniej dwuelementowych ma zbiór sześcioelementowy? Policzymy to w czterech krokach.

Zadanie n=6, k≥2n = 6, \ k \geq 2 26=642^6 = 64 64−7=5764 - 7 = 57
  1. Zapisz szukaną sumę

    Podzbiory co najmniej dwuelementowe mają 2, 3, 4, 5 albo 6 elementów. Szukasz więc sumy symboli Newtona od k=2k = 2 do k=6k = 6.

    1. ∑k=26(6k)=\displaystyle \sum_{k=2}^{6} \binom{6}{k} =
    2. (62)+(63)+…+(66)\displaystyle \binom{6}{2} + \binom{6}{3} + \ldots + \binom{6}{6}

    k=m,…,nk = m, \ldots, n bez kilku pierwszych liczb

    Nasze zadanie: k=2,…,6k = 2, \ldots, 6

    Policz cały wiersz, a potem odejmij składniki, których brakuje. Jest ich mniej niż tych, które zostają.

    k=0,1,…,nk = 0, 1, \ldots, n cały wiersz

    Wynik to od razu 2n2^n. Tak liczysz wszystkie podzbiory zbioru, razem z pustym i z całym zbiorem.

    Przykład: wszystkie podzbiory

    k=0,2,4,…k = 0, 2, 4, \ldots co drugi składnik

    Podzbiory o parzystej i o nieparzystej liczbie elementów dzielą wszystkie podzbiory po połowie. Każdej grupy jest 2n−12^{n-1}, gdy n≥1n \geq 1.

    Przykład: parzyste podzbiory

  2. Policz wszystkie podzbiory

    Suma całego wiersza n=6n = 6 to liczba wszystkich podzbiorów zbioru sześcioelementowego.

    1. ∑k=06(6k)=26\displaystyle \sum_{k=0}^{6} \binom{6}{k} = 2^6
    2. 26=642^6 = 64
  3. Odejmij brakujące składniki

    Brakuje podzbioru pustego (60)\binom{6}{0} i podzbiorów jednoelementowych (61)\binom{6}{1}. Odejmij oba składniki od 64.

    1. (60)+(61)=1+6=7\displaystyle \binom{6}{0} + \binom{6}{1} = 1 + 6 = 7
    2. 64−7=5764 - 7 = 57
  4. Sprawdź, dodając składniki

    Wypisz wiersz n=6n = 6 trójkąta Pascala: 1, 6, 15, 20, 15, 6, 1. Dodaj liczby od trzeciej do ostatniej, czyli składniki od (62)\binom{6}{2} do (66)\binom{6}{6}.

    1. 15+20+15+6+1=5715 + 20 + 15 + 6 + 1 = 57

    Odpowiedź: zbiór sześcioelementowy ma 5757 podzbiorów co najmniej dwuelementowych.

Więcej przykładów

Najpierw rozwiąż każde zadanie sam, a dopiero potem porównaj wynik z rozwiązaniem.

Przykład 1. Wszystkie podzbiory

Ile podzbiorów ma zbiór {a,b,c,d,e}\{a, b, c, d, e\}? Liczą się też zbiór pusty i cały zbiór.

Przykład 2. Pizza z dodatkami

Do pizzy możesz wybrać dowolne z 8 dodatków, ale co najmniej jeden. Ile różnych zestawów dodatków możesz zamówić?

Przykład 3. Parzyste podzbiory

Ile podzbiorów o parzystej liczbie elementów ma zbiór pięcioelementowy? Zbiór pusty ma 0 elementów, więc też się liczy.

Przykład 4. Odpowiedzi tak albo nie

Test ma 6 pytań, a na każde odpowiadasz „tak” albo „nie”. Ile jest różnych zestawów odpowiedzi?

Przykład 5. Równanie z sumą

Rozwiąż równanie (n1)+(n2)+…+(nn)=127\binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n} = 127.

Najczęstsze błędy

Unikaj ich w każdym zadaniu z sumą symboli Newtona.

Przypadki szczególne

Te sumy liczysz od razu, bez dodawania składników.

Zbiór pusty (00)=1=20\displaystyle \binom{0}{0} = 1 = 2^0
Dla n=0n = 0 wiersz ma jedną liczbę. Zbiór pusty ma jeden podzbiór: samego siebie.
Podzbiory niepuste ∑k=1n(nk)=2n−1\displaystyle \sum_{k=1}^{n} \binom{n}{k} = 2^n - 1
Odejmujesz tylko zbiór pusty. Na przykład zbiór pięcioelementowy ma 25−1=312^5 - 1 = 31 podzbiorów niepustych.
Podzbiory właściwe ∑k=0n−1(nk)=2n−1\displaystyle \sum_{k=0}^{n-1} \binom{n}{k} = 2^n - 1
Odejmujesz tylko cały zbiór. Zbiór {a,b,c}\{a, b, c\} ma 23−1=72^3 - 1 = 7 podzbiorów właściwych.
Suma ze zmianą znaków ∑k=0n(−1)k(nk)=0\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0
Dla n≥1n \geq 1 wynika z dwumianu Newtona dla a=1a = 1 i b=−1b = -1. Dlatego składniki o parzystym kk dają razem tyle samo co składniki o nieparzystym kk, po 2n−12^{n-1}. Na przykład 1−3+3−1=01 - 3 + 3 - 1 = 0.

Powiązane wzory

Pytania i odpowiedzi

Masz pytanie do tego wzoru albo przykładu? Zadaj je tutaj. Odpowiadają inni użytkownicy i redakcja.

Twoje pytanie

Szukaj wzoru

Wpisz nazwę wzoru. Polskie znaki są opcjonalne. Strzałkami wybierzesz wynik, Enter go otworzy.