algorytm.org

Symbol Newtona

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Symbol Newtona
Ocena użytkowników:***** / 24
SłabyŚwietny 
Wpisany przez Bartosz Bednarczyk, 11 lipca 2011 10:51

Definicja Symbolu Newtona

Symbol Newtona jest to funkcja dwóch argumentów. Definiujemy ją jako:
{n\choose k}=\frac{n!}{k!(n-k)!}
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:
{4\choose 2} = \frac{4!}{2!(4-2)!} = \frac{2*3*4}{2*2}=2*3 = 6

Wyznaczanie wartości Symbolu Newtona

Zanim pokażę, jak szybko obliczać wartość Symbolu Newtona, trzeba przytoczyć kilka istotnych własności tej funkcji. Otóż:
{n\choose 0}={n\choose n}=1\\\\\\ {n\choose k}={n\choose n-k}\\\\\\ {n\choose k}+{n\choose k+1}={n+1\choose k+1}


Bardzo interesującą własnością Symbolu Newtona jest to, ze jego wartości układają tzw. Trójkąt Pascala:
\begin{array}{ccccccccccc} & & & & &1& & & & &\\ & & & &1& &1& & & &\\ & & &1& &2& &1& & &\\ & &1& &3& &3& &1& &\\ &1& &4& &6& &4& &1&\\ 1& &5& &10& &10& &5& &1 \end{array}

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:
{n \choose k}=\begin{cases} 1& \text{dla } k=0 \vee n=k\\ {n-1 \choose k-1} + {n-1 \choose k}& \text{dla } 0 < k < n\\ \end{cases}

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.

{5 \choose 3} = \frac{5!}{3!(5-3)!} = \frac{1*2*3*4*5}{1*2*3*1*2} = \frac{2*2*2*3*5}{2*2*3}

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)n w sumę jednomianów.
Postać takiego jednomianu to axkyl, 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:

\begin{array}{ccccccccccc} & & & & &1& & & & &\\ & & & &1& &1& & & &\\ & & &1& &2& &1& & &\\ & &1& &3& &3& &1& &\\ &1& &4& &6& &4& &1&\\ 1& &5& &10& &10& &5& &1 \end{array}

Dla (a + b)n sa to współczynniki n+1 wiersza. Przykłady:
1. (a + b)2 = a2 + 2ab + b2
2. (a + b)3 = a3 + 3a2b + 3ab2 + b3

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Bartosz BednarczykC#obliczanie wartości iteracyjnie
.cs
.cs
***** / 3
Bartosz BednarczykC#sprawdzanie parzystości (bitowo)
.cs
.cs
***** / 1
Bartosz BednarczykC#sprawdzanie parzystości (tw. Lagrange'a)
.cs
.cs
***** / 1
Bartosz BednarczykC/C++obliczanie wartości iteracyjnie
.cpp
.cpp
***** / 5
Bartosz BednarczykC/C++C++ obliczanie wartości iteracyjnie
.cpp
.cpp
***** / 21
Bartosz BednarczykC/C++sprawdzanie parzystości (bitowo)
.cpp
.cpp
***** / 0
Bartosz BednarczykC/C++C++ sprawdzanie parzystości (bitowo)
.cpp
.cpp
***** / 1
Bartosz BednarczykC/C++sprawdzanie parzystości (tw. Lagrange'a)
.cpp
.cpp
***** / 0
Bartosz BednarczykC/C++C++ sprawdzanie parzystości (tw. Lagrange'a)
.cpp
.cpp
***** / 1
Bartosz BednarczykJavaobliczanie wartości iteracyjnie
.java
.java
***** / 5
Bartosz BednarczykJavasprawdzanie parzystości (bitowo)
.java
.java
***** / 0
Bartosz BednarczykJavasprawdzanie parzystości (tw. Lagrange'a)
.java
.java
***** / 0
Bartosz BednarczykPythonobliczanie wartości iteracyjnie
.py
.py
***** / 2
Bartosz BednarczykPythonsprawdzanie parzystości (bitowo)
.py
.py
***** / 1
Bartosz BednarczykPythonsprawdzanie parzystości (tw. Lagrange'a)
.py
.py
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 stycznia 2013 22:46
Dodaj komentarz