Definicja Symbolu Newtona

Symbol Newtona jest to funkcja dwóch argumentów. Definiujemy ją jako: Zapis taki czytamy n po k lub n nad k. Warto zapamiętać, że n oraz k są liczbami naturalnymi, oraz n ≥ k.

Zastosowanie Symbolu Newtona

Dzięki Symbolowi Newtona, możemy wyznaczyć liczbę kombinacji, czyli liczbę podzbiorów k-wyrazowych danego zbioru n-elementowego. Może to się wydawać trudne, ale postaram się to zilustrować przykładem:

Wyobraźmy sobie, że posiadamy półkę na której są cztery książki - biała, zielona, niebieska i czerwona. Na ile sposobów możemy z niej zdjąć dwie książki?
Do tego właśnie przydaje się wzór, który podałem powyżej. Oczywiście możemy liczyć to ręcznie, wtedy powinniśmy dostać dokładnie 6 kombinacji. Skąd się wzięła ta liczba? Już tłumaczę.

Zdefiniujmy najpierw sobie naszą półkę, czyli zbiór {b, z, n, c}.
Elementami są pierwsze litery kolorów książek. Wszystkie kombinacje to:

1. {b, z}
2. {b, n}
3. {b, c}
4. {z, n}
5. {z, c}
6. {n, c}

Wcale nie trzeba tutaj rozpisywać wszystkich kombinacji, by poznać ich ilość. Wystarczy umiejętnie podstawić liczby do wzoru:

Wyznaczanie wartości Symbolu Newtona

Zanim pokażę, jak szybko obliczać wartość Symbolu Newtona, trzeba przytoczyć kilka istotnych własności tej funkcji. Otóż:

Bardzo interesującą własnością Symbolu Newtona jest to, ze jego wartości układają tzw. Trójkąt Pascala:
Każdy numer kolumny oznacza n, a wiersz k

Na podstawie tych spostrzeżeń, możemy ułożyć wzór iteracyjny oraz rekurencyjny.

Wzór iteracyjny opera się o założenie o występowaniu czynników pierwszych w ciągach kolejnych liczb.

{n \choose k} = \frac{1*2*... * n}{1*2* ... * n * (1*2*... * (n-k))} = \frac{n(n-1)...(n-k+1)}{1*2*...*k}

Wartość Symbolu Newtona możemy również policzyć rekurencyjnie ze wzoru:

Sprawdzanie parzystości Symbolu Newtona

Kolejnym problemem związanym z Symbolem Newtona jest sprawdzanie czy jego wartość jest parzysta.
Można oczywiście obliczać całe wyrażenie i ocenić jego podzielność przez dwa, ale jest dużo prostszy sposób:

Twierdzenie Lagrange'a
Jeżeli liczba dwójek w rozkładzie n! jest większa od liczby dwójek w rozkładzie k!(n-k)! to wartość symbolu newtona jest parzysta.
Wytłumaczę to twierdzenie na przykładzie:
Zapiszmy sobie przykładowy symbol i rozbijmy go na czynniki pierwsze.


Następnie zliczamy ilość dwójek i zapisujemy.
Stosunek dwójek: 3/2
Licznik jest większy od mianownika, więc wartość symbolu jest parzysta.
Jest jednak jeszcze szybszy sposób na sprawdzanie tej własności.

Twierdzenie
Jeżeli n|k = n to wartość symbolu newtona jest nieparzysta.
Teraz wystarczy tylko, że użyjemy alternatywy bitowej i od razu wiemy, czy wartość symbolu jest parzysta czy nie.
Czyli jeżeli weźmiemy symbol z przykładu powyżej otrzymamy: 5|3 = 7, zatem wartość symbolu jest parzysta.

Dwumian Newtona i trójkąt Pascala

Dwumian Newtona jest to wzór, dzięki któremu możemy rozwinąć potęgę dwumianu (a + b)ⁿ w sumę jednomianów.
Postać takiego jednomianu to ax^ky^l, przy czym zachodzi własność: k + l = n. Oczywiście pamiętamy, ze a jest liczbą naturalną. Taki współczynnik jest nazywany współczynnikiem dwumianowym. Jest on także symbolem Newtona.
Bardzo interesująca własnością jest, ze współczynniki dwumianowe układają tzw. trójkąt Pascala:


Dla (a + b)ⁿ sa to współczynniki n+1 wiersza. Przykłady:
1. (a + b)² = a² + 2ab + b²
2. (a + b)³ = a³ + 3a²b + 3ab² + b³