Symbol Newtona

dwuargumentowa funkcja matematyczna, zwykle zmiennych naturalnych

Symbol Newtona, współczynnik dwumianowy (dwumienny) Newtonafunkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako[1][2]:

   dla  

gdzie oznacza silnię liczby całkowitej nieujemnej

Symbol odczytuje się n nad k, n po k lub k z n.

Symbol Newtona można równoważnie wyrazić wzorem rekurencyjnym:

Symbol Newtona pojawia się we wzorze dwumiennym Newtona[3] jako współczynnik w -tym wyrazie rozwinięcia -tej potęgi sumy dwu składników – stąd jego druga nazwa współczynnik dwumienny Newtona.

Własności symbolu Newtona

edytuj

Związki kombinatoryczne

edytuj

Symbol Newtona równy jest liczbie wszystkich  -elementowych kombinacji bez powtórzeń ze zbioru  -elementowego ( -elementowych podzbiorów zbioru  -elementowego). Liczba ta jest też oznaczana jako   w literaturze angielskiej spotyka się oznaczenie   w amerykańskiej   (od wyrażenia „n choose k”, czyli „n brane po k”).

Zatem poniższe symbole są równoważnymi oznaczeniami liczby dwuelementowych kombinacji ze zbioru siedmioelementowego:

 

Pochodzenie wzoru iteracyjnego

edytuj

Każdą kombinację  -elementową ze zbioru  -elementowego   można utworzyć, wybierając kolejno   różnych elementów. Uzyskuje się w ten sposób  -elementowy ciąg, czyli wariację ze zbioru   Wariacji takich jest

 

Kombinacje, jako podzbiory, w przeciwieństwie do wariacji, czyli ciągów, nie mają ustalonej kolejności elementów. Dwie różne wariacje, różniące się tylko kolejnością elementów, dają tę samą kombinację. Liczba  -elementowych kombinacji jest więc mniejsza od liczby  -elementowych wariacji tylokrotnie, ile jest różnych porządków (przestawień, czyli permutacji) takiego ciągu. A ponieważ permutacji  -elementowych jest

 

ostatecznie:

 

Pochodzenie wzoru rekurencyjnego

edytuj

Z każdego zbioru  -elementowego można wybrać tylko jedną kombinację 0-elementową (czyli podzbiór pusty,  ), stąd liczba kombinacji pustych  

Z każdego zbioru  -elementowego   można wybrać tylko jedną kombinację  -elementową   (podzbiór niewłaściwy, równy całemu zbiorowi:  ), stąd liczba takich kombinacji  

Oba powyższe stwierdzenia dotyczą oczywiście także zbioru pustego    

Niech teraz   będzie niepustym zbiorem  -elementowym   Wyłączymy zeń jeden element,   i oznaczymy pozostały podzbiór  -elementowy przez  

 

Wśród wszystkich niepustych kombinacji k-elementowych   wyróżnić można te, które zawierają element   i pozostałe, które go nie zawierają.

  • Każdą  -elementową kombinację   zawierającą   można przedstawić jako unię pewnej  -elementowej kombinacji   i jednoelementowego zbioru   Ponieważ przy tym   zawiera się w  -elementowym   to kombinacji takich jest  
  • Każda k-elementowa kombinacja nie zawierająca   sama zawiera się w   czyli w  -elementowym zbiorze   Zatem kombinacji takich jest  

Stąd ostatecznie dla   liczba kombinacji  -elementowych równa jest sumie liczb kombinacji obu rodzajów:

 

Tożsamości algebraiczne

edytuj

Skracając w definicji czynnik   otrzymuje się:

 

co dla dodatnich wartości   rozwija się do uproszczonej postaci iteracyjnej[1]:

 

Dla   puste iloczyny stają się równe jedności, i w efekcie[1]:

 

Dla   w liczniku i mianowniku zostaje tylko pierwszy czynnik, stąd:

 

– jeden element spośród   wybrać można na   sposobów.

Inne tożsamości:

liczba kombinacji dopełniających[1]:

  •  

liczba kombinacji pustych (i dopełniających do pustych):

  •  

liczba kombinacji w zbiorze pustym:

  •  
  •  

suma współczynników dwumianu Newtona  

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Teoria liczb

edytuj

Liczba pierwsza   dzieli każdą liczbę   dla  

Dowód: W liczniku wyrażenia   występuje   zaś w mianowniku tylko liczby mniejsze, które ze względu na pierwszość liczby   nie mogą być jej dzielnikami (oprócz 1). Ponieważ liczba jest całkowita, w jej rozkładzie na czynniki pierwsze występuje  

Wniosek: W ciele   zachodzi równość:  

Trójkąt Pascala

edytuj

Wartości kolejnych symboli Newtona można zapisać w postaci trójkąta Pascala:

0                      1
1                    1   1
2                  1   2   1
3                1   3   3   1
4              1   4   6   4   1
5            1   5   10  10  5   1
6          1   6   15  20  15  6   1
7        1   7   21  35  35  21  7   1
8      1   8   28  56  70  56  28  8   1
9    1   9   36  84 126 126  84  36  9   1
10 1   10  45  120 210 252 210 120 45 10   1
   . . . . . . . . . . . . . . . . . . . . . .

Kolejnym wierszom trójkąta odpowiadają kolejne wartości   kolejnym wyrazom w każdym wierszu – kolejne wartości  

Skrajne wyrazy w każdym wierszu równe są jedności, każdy wyraz (poza skrajnymi) jest sumą dwu wyrazów stojących bezpośrednio nad nim, w poprzednim wierszu. Schemat ten odpowiada wprost wzorowi rekurencyjnemu.

Obliczanie symbolu Newtona

edytuj

Prosta, a równocześnie dość szybka metoda obliczania wartości współczynnika Newtona opiera się na uproszczonej postaci iteracyjnej:

 

oraz spostrzeżeniu o występowaniu czynników pierwszych w ciągu kolejnych liczb naturalnych:

  • z każdych kolejnych dwu liczb naturalnych jedna jest parzysta (podzielna przez 2),
  • z każdych kolejnych trzech liczb naturalnych jedna jest podzielna przez 3,
  • z każdych kolejnych czterech liczb naturalnych jedna jest podzielna przez 4 itd.

To gwarantuje, że z liczb   i   jedna jest podzielna przez 2, a więc i iloczyn   jest podzielny przez 2 – można więc obliczyć iloraz   i iloraz ten jest liczbą całkowitą. Z kolei z liczb     i   jedna jest podzielna przez 3, zatem iloczyn   dzieli się przez 3 (prócz tego, że na pewno dzieli się przez 2); zatem obliczony wcześniej iloraz   po pomnożeniu przez   można podzielić przez 3, a uzyskana wartość ilorazu   znów jest liczbą całkowitą.

Tym sposobem, mnożąc i dzieląc na przemian, można obliczyć wartość współczynnika Newtona   wykonując   mnożeń i tyleż dzieleń całkowitoliczbowych. Dzięki odpowiedniemu uporządkowaniu działań w metodzie tej nie występują ułamki – wszystkie wyniki pośrednie są całkowite, a więc nie ma ryzyka błędów zaokrąglenia.

Przykładowa procedura w Pascalu:

function WspNewtona( n, k : integer ) : integer;
var
    wynik : integer;
    i : integer;
begin
    wynik := 1;

    for i := 1 to k do
        wynik := wynik * (n - i + 1) div i;

    WspNewtona := wynik;
end;

Przykładowa metoda 64-bitowa w Javie kontrolująca przepełnienie typu Long:

long symbolNewtona(final long N, final long K)
{
    assert N >= 0;
    assert K >= 0;

    if (N < K)
        return 0L;

    if (K == 0 || K == N)
        return 1L;

    if (K == 1 || K == N - 1)
        return N;

    long wynik = 1L;
    try
    {
        final long maxK = Math.min(K, N - K);
        for (long i = 1L; i <= maxK; i++)
            wynik = Math.multiplyExact(wynik, (N - i + 1)) / i;
    }
    catch (ArithmeticException e)
    {
        return -1L;
    }

    return wynik;
}

Drugi przykład w Javie daje poprawne wyniki dla dowolnych dodatnich danych wejściowych:

BigInteger symbolNewtona(final long N, final long K)
{
    assert N >= 0;
    assert K >= 0;

    if (N < K)
        return BigInteger.valueOf(0);

    if (K == 0L || K == N)
        return BigInteger.valueOf(1);

    if (K == 1L || K == N - 1L)
        return BigInteger.valueOf(N);

    BigInteger result = BigInteger.valueOf(1);

    final long maxK = Math.min(K, N - K);
    for (long i = 1L; i <= maxK; i++)
        result = result.multiply(BigInteger.valueOf(N - i + 1L)).divide(BigInteger.valueOf(i));

    return result;
}

Ta druga metoda jest efektywna czasowo i pamięciowo, jest tylko około trzy razy wolniejsza od wersji poprzedniej. W obu metodach sprawdzane są przypadki szczególne oraz zoptymalizowano liczbę pętli dla   korzystając z faktu, że funkcja ta jest symetryczna.

Przykładowy predykat w Prologu:

silnia(0, 1) :- !.
silnia(1, 1) :- !.
silnia(N, X) :- N1 is N-1, silnia(N1, X1), X is N * X1.

npok(N, K, X) :- silnia(N, X1), silnia(K, X2), NK is N-K, silnia(NK, X3), X is X1 / (X2 * X3).

Procedura ta działa szybko i z minimalnym kosztem pamięciowym – wymaga tylko dwu pomocniczych zmiennych (a po dodatkowym usprawnieniu nie potrzebowałaby żadnych). Drobną wadą tego sposobu jest niewielki nadmiar w trakcie obliczeń: maksymalna wartość pośrednia, otrzymana przed ostatnim dzieleniem przez   jest  -krotnie większa od ostatecznego wyniku. To oznacza, że metody tej nie da się wykorzystać „do granic pojemności” typu całkowitego: maksymalna wiarygodna wartość obliczana tym sposobem zawsze będzie  -krotnie niższa od największej wartości całkowitej dostępnej w danym komputerze, kalkulatorze bądź języku programowania.

Poniżej przedstawiona jest procedura rekurencyjna, pozbawiona tej wady.

function WspNewtonaRek( n, k : integer ) : integer;
begin
    if (k = 0) or (k = n) then
        WspNewtonaRek := 1
    else
        WspNewtonaRek := WspNewtonaRek( n-1, k-1 ) + WspNewtonaRek( n-1, k );
end;

Implementacja rekurencyjna bez użycia silni w Prologu:

symbolnewtona(N, K, fail) :- K > N, !.
symbolnewtona(K, K, 1) :- !.
symbolnewtona(N, 0, 1) :- !.
symbolnewtona(N, K, X) :- N1 is N-1, K1 is K-1, symbolnewtona(N1, K1, X1), symbolnewtona(N1, K, X2), X is X1 + X2, !.

Ten sposób opiera się wprost na rekurencyjnym wzorze:

 

Procedura ta nie ma wady poprzedniej metody – oblicza końcową wartość bez żadnego nadmiaru w wynikach pośrednich. Niestety, płaci się za to ogromnym kosztem obliczeń. Funkcja przestaje wywoływać samą siebie, dopiero gdy zwraca wartość 1 – to oznacza, że obliczenie wartości   wymaga co najmniej   wywołań funkcji (bezpośrednich i pośrednich). Złożoność czasowa jest więc nie mniejsza niż wartość funkcji:   (zobacz Notacja dużego O). Równocześnie, jeśli tylko początkowa wartość   nie jest równa 0 ani   co najmniej jedna ścieżka rekursji kończy się na wywołaniu WspNewtonaRek(1, 0) albo WspNewtonaRek(1, 1). Ścieżka ta prowadzi przez   poziomów wywołań, w których parametr   był kolejno zmniejszany aż do jedności. Głębokość rekurencji, a zatem złożoność pamięciowa jest więc ściśle liniowa   i to w bardzo wrażliwym obszarze stosu.

Kolejnym krokiem pozwalającym na przyspieszenie obliczeń jest wykorzystanie programowania dynamicznego – można w tabeli przechowywać wyniki obliczeń poszczególnych kroków rekurencji, aby skrócić czas potrzebny na znalezienie danej wartości symbolu. Efektem ubocznym stosowania powyższej metody jest to, że otrzymuje się od razu wszystkie elementy trójkąta Pascala poprzedzające szukaną wartość.

Ograniczenia dla symbolu Newtona

edytuj

Zachodzą następujące nierówności (z definicji   oraz przyjmujemy   by uniknąć dzielenia przez zero):

  •  ,
  •  
  •  

Uogólnienie na wielomiany wyższych stopni

edytuj

Współczynniki dwumienne można uogólnić do współczynników wielomianowych. Definiuje się je w następujący sposób:

 

przy czym:

 

Współczynnik dwumienny określa współczynniki wyrażenia:   podczas gdy współczynniki wielomianowe określają współczynniki wielomianu:

 

w następujący sposób:

 

gdzie sumujemy po wszystkich naturalnych   spełniających podane wcześniej reguły.

Dla   uzyskujemy współczynniki dwumianowe:

 

Interpretacja kombinatoryczna współczynników wielomianowych to liczba sposobów rozmieszczenia   rozróżnialnych elementów w   rozróżnialnych pudełkach, z których każde mieści dokładnie   elementów, gdzie   jest indeksem pudełka.

Współczynniki wielomianowe mają wiele własności podobnych do własności współczynników dwumianowych, takich jak rekurencja:

 

i symetria:

 

gdzie   jest permutacją  

Uogólnienie na liczby rzeczywiste i zespolone

edytuj

Symbol Newtona uogólnia się na liczby rzeczywiste i zespolone, korzystając z funkcji specjalnej gamma. Uogólnienie to opiera się na tożsamości:

 

spełnionej dla naturalnych wartości  

Możemy także przyjąć następującą (nierównoważną) definicję:
Niech   będzie dowolną liczbą rzeczywistą lub zespoloną. Wówczas przez symbol   będziemy rozumieli wyrażenie

 

lub zapisane inaczej

 

Następujący wzór, zwany górną negacją, przydaje się do wyznaczania wartości symbolu Newtona dla ujemnych wartości z:

 

Przypisy

edytuj
  1. a b c d Wybrane wzory matematyczne, Warszawa: Centralna Komisja Egzaminacyjna, 2015, s. 2, ISBN 978-83-940902-1-0.
  2. Kenneth A. Ross, Charles R. B. Wright: Matematyka dyskretna. Wydawnictwo Naukowe PWN, 2001, s. 277. ISBN 83-01-12129-7.
  3. Newtona symbol, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-22].

Linki zewnętrzne

edytuj