|
'''Symbol Newtona, współczynnik dwumianowy (dwumienny) Newtona''' – [[funkcja]] dwóch argumentów [[liczby całkowite|całkowitych]] nieujemnych, zdefiniowana jako:
: <math>{n \choose k} = \frac{n!}{k!(n-k)!}</math> dla <math>0 \leqslant k \leqslant n,</math>
gdzie <math>a!</math> oznacza [[silnia|silnię]] liczby całkowitej nieujemnej <math>a.</math>
Symbol <math>n \choose k</math> odczytuje się ''n nad k'', ''n po k'' lub ''k z n''.
Symbol Newtona można równoważnie wyrazić wzorem [[Rekurencja|rekurencyjnym]]:
: <math>{n \choose k} = \begin{cases}
1 & \mbox{dla } k=0 \mbox{ lub } k=n \\
{n-1 \choose k-1} + {n-1 \choose k} & \mbox{dla } 0 < k < n
\end{cases}</math>
Symbol Newtona pojawia się we [[dwumian Newtona|wzorze dwumiennym Newtona]] jako współczynnik w <math>k</math>-tym wyrazie rozwinięcia <math>n</math>-tej potęgi sumy dwu składników – stąd jego druga nazwa '''współczynnik dwumienny Newtona'''.
== Własności symbolu Newtona ==
=== Związki kombinatoryczne ===
Symbol [[Isaac Newton|Newtona]] równy jest liczbie wszystkich <math>k</math>-elementowych [[kombinacja bez powtórzeń|kombinacji]] bez powtórzeń ze [[zbiór|zbioru]] <math>n</math>-elementowego (<math>k</math>-elementowych podzbiorów zbioru <math>n</math>-elementowego). Liczba ta jest też oznaczana jako <math>C^k_n;</math> w literaturze angielskiej spotyka się oznaczenie <math>{}^nC_k,</math> w amerykańskiej <math>{}_nC_k</math> (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:
: <math>{7 \choose 2} = C^2_7 = ^7C_2 = _7C_2 = 21.</math>
=== Pochodzenie wzoru iteracyjnego ===
Każdą kombinację <math>k</math>-elementową ze zbioru <math>n</math>-elementowego <math>A</math> można utworzyć wybierając kolejno <math>k</math> różnych elementów. Uzyskuje się w ten sposób <math>k</math>-elementowy [[ciąg (matematyka)|ciąg]], czyli [[Wariacja bez powtórzeń|wariację]] ze zbioru <math>A.</math> Wariacji takich jest
: <math>V_n^k=\frac{n!}{(n-k)!}.</math>
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 <math>k</math>-elementowych kombinacji jest więc mniejsza od liczby <math>k</math>-elementowych wariacji tylokrotnie, ile jest różnych porządków (przestawień, czyli [[permutacja|permutacji]]) takiego ciągu. A ponieważ permutacji <math>k</math>-elementowych jest
: <math>P_k = k!,</math>
ostatecznie:
: <math>C_n^k = \frac{V_n^k}{P_k} = \frac{n!}{(n-k)!} \cdot \frac{1}{k!} = \frac{n!}{k!(n-k)!}.</math>
=== Pochodzenie wzoru rekurencyjnego ===
Z każdego zbioru <math>n</math>-elementowego można wybrać tylko jedną [[kombinacja bez powtórzeń|kombinację]] 0-elementową (czyli [[podzbiór]] [[zbiór pusty|pusty]], <math>\varnothing</math>), stąd liczba kombinacji pustych <math>C_n^0=1.</math>
Z każdego zbioru <math>n</math>-elementowego <math>A</math> można wybrać tylko jedną kombinację <math>n</math>-elementową <math>B</math> (podzbiór niewłaściwy, równy całemu zbiorowi: <math>B=A</math>), stąd liczba takich kombinacji <math>C_n^n=1.</math>
Oba powyższe stwierdzenia dotyczą oczywiście także zbioru pustego <math>A=\varnothing</math> <math>(n=0).</math>
Niech teraz <math>A</math> będzie niepustym zbiorem <math>n</math>-elementowym (n>0). Wyłączymy zeń jeden element, <math>a</math> i oznaczymy pozostały podzbiór (n-1)-elementowy przez <math>A'{:}</math>
: <math>A'=A\setminus\{a\}</math>
Wśród wszystkich niepustych kombinacji k-elementowych <math>(k>0)</math> wyróżnić można te, które zawierają element <math>a,</math> i pozostałe, które go nie zawierają.
* Każdą <math>k</math>-elementową kombinację <math>K</math> zawierającą <math>a</math> można przedstawić jako [[suma zbiorów|unię]] pewnej <math>(k-1)</math>-elementowej kombinacji <math>K'</math> i jednoelementowego zbioru <math>\{a\}.</math> Ponieważ przy tym <math>K'</math> zawiera się w <math>(n-1)</math>-elementowym <math>A',</math> to kombinacji takich jest <math>C_{n-1}^{k-1}.</math>
* Każda k-elementowa kombinacja nie zawierająca <math>a</math> sama zawiera się w <math>A\setminus\{a\},</math> czyli w <math>(n-1)</math>-elementowym zbiorze <math>A'.</math> Zatem kombinacji takich jest <math>C_{n-1}^k.</math>
Stąd ostatecznie dla <math>0<k<n</math> liczba kombinacji <math>k</math>-elementowych równa jest sumie liczb kombinacji obu rodzajów:
: <math>C_n^k = C_{n-1}^{k-1} + C_{n-1}^k</math>
=== Tożsamości algebraiczne ===
Skracając w definicji czynnik <math>(n-k)!</math> otrzymuje się:
: <math>{n \choose k} = \frac{\prod_{i=1}^k n-i+1}{\prod_{i=1}^k i} = \prod_{i=1}^k \frac{n-i+1}{i},</math>
co dla dodatnich wartości <math>k</math> rozwija się do uproszczonej postaci iteracyjnej:
: <math>{n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdot\ldots\cdot k}.</math>
Dla <math>k=0</math> puste iloczyny stają się równe jedności, i w efekcie:
: <math>{n \choose 0} = 1.</math>
Dla <math>k=1</math> w liczniku i mianowniku zostaje tylko pierwszy czynnik, stąd:
: <math>{n \choose 1} = \frac n 1 = n</math>
– jeden element spośród <math>n</math> wybrać można na <math>n</math> sposobów.
'''Inne tożsamości:'''
liczba kombinacji dopełniających:
* <math>{n \choose k} = {n \choose n-k},</math>
liczba kombinacji pustych (i dopełniających do pustych):
* <math>{n \choose 0} = {n \choose n} = 1,</math>
liczba kombinacji w zbiorze pustym:
* <math>{0 \choose 0} = 1</math>
* <math>{n \choose k+1} = {n \choose k} \cdot \frac{n-k}{k+1},</math>
suma współczynników [[dwumian Newtona|dwumianu Newtona]] <math>(1+1)^n{:}</math>
* <math>\sum_{k=0}^n {n \choose k} = 2^n,</math>
* <math>\sum_{k=0}^n {n \choose k}^2 = {2n \choose n},</math>
* <math>\sum_{k=0}^n (-1)^k \cdot {n \choose k} = 0,</math>
* <math>\sum_{k=1}^n k{n \choose k} = n2^{n-1},</math>
* <math>\sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n},</math>
* <math>{r \choose k} = \frac{r}{k} {r-1 \choose k-1}, k \neq 0,</math>
* <math>(r-k){r \choose k} = r{r-1 \choose k},</math>
* <math>{n \choose k}{n-k \choose p-k} = {n \choose p}{p \choose k}.</math>
=== Teoria liczb ===
Liczba pierwsza <math>p</math> dzieli każdą liczbę <math>p \choose k</math> dla <math>k=1,2,\dots,p-1.</math>
'''Dowód''': W liczniku wyrażenia <math>\frac{p(p-1)\cdots(p-k+1)}{1\cdot 2\cdot \ldots \cdot k}</math> występuje <math>p,</math> zaś w mianowniku tylko liczby mniejsze, które ze względu na pierwszość liczby <math>p</math> nie mogą być jej [[dzielnik]]ami (oprócz 1). Ponieważ liczba jest całkowita, w jej rozkładzie na [[Czynnik pierwszy|czynniki pierwsze]] występuje <math>p.</math>
'''Wniosek''': W [[Arytmetyka modularna|ciele <math>\mathbb{Z}_p</math>]] zachodzi równość: <math>(a+b)^p=a^p+b^p.</math>
== Trójkąt Pascala ==
Wartości kolejnych symboli Newtona można zapisać w postaci [[Trójkąt Pascala|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
. . . . . . . . . . . . . . . . . . .
Kolejnym wierszom trójkąta odpowiadają kolejne wartości <math>n,</math> kolejnym wyrazom w każdym wierszu – kolejne wartości <math>k.</math>
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 ==
Prosta, a równocześnie dość szybka metoda obliczania wartości współczynnika Newtona opiera się na uproszczonej postaci iteracyjnej:
: <math>{n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdot \ldots \cdot k}</math>
oraz spostrzeżeniu o występowaniu [[Czynnik pierwszy|czynników pierwszych]] w ciągu kolejnych [[liczby naturalne|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 <math>n</math> i <math>(n-1)</math> jedna jest podzielna przez 2, a więc i iloczyn <math>n(n-1)</math> jest podzielny przez 2 – można więc obliczyć iloraz <math>\frac{n(n-1)}2,</math> i iloraz ten jest liczbą całkowitą. Z kolei z liczb <math>n,</math> <math>(n-1)</math> i <math>(n-2)</math> jedna jest podzielna przez 3, zatem iloczyn <math>n(n-1)(n-2)</math> dzieli się przez 3 (prócz tego, że na pewno dzieli się przez 2); zatem obliczony wcześniej iloraz <math>\frac{n(n-1)}2</math> po pomnożeniu przez <math>(n-2)</math> można podzielić przez 3, a uzyskana wartość ilorazu <math>\frac{n(n-1)(n-2)}{2\cdot 3}</math> znów jest [[Liczby całkowite|liczbą całkowitą]].
Tym sposobem, mnożąc i dzieląc na przemian, można obliczyć wartość współczynnika Newtona <math>C_n^k</math> wykonując <math>k</math> 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 [[Pascal (język programowania)|Pascalu]]:
<source lang=pascal>
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;
</source>
Przykładowy predykat w [[Prolog (język programowania)|Prologu]]:
<source lang=prolog>
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).
</source>
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 <math>k,</math> jest <math>k</math>-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 <math>k</math>-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 [[Rekurencja|rekurencyjna]], pozbawiona tej wady.
<source lang=pascal>
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;
</source>
Implementacja rekurencyjna bez użycia silni w [[Prolog (język programowania)|Prologu]]:
<source lang=prolog>
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, !.
</source>
Ten sposób opiera się wprost na rekurencyjnym wzorze:
: <math>{n \choose k}=\begin{cases}
1 & \mbox{gdy } k=0 \mbox{ lub } k=n \\
{n-1 \choose k-1} + {n-1 \choose k} & \mbox{gdy } 0 < k < n
\end{cases}</math>
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 <math>C_n^k</math> wymaga co najmniej <math>C_n^k</math> wywołań funkcji (bezpośrednich i pośrednich). Złożoność czasowa jest więc nie mniejsza niż wartość funkcji: <math>\Omega(C_n^k)</math> (zobacz [[Asymptotyczne tempo wzrostu|Notacja dużego O]]). Równocześnie, jeśli tylko początkowa wartość <math>k</math> nie jest równa 0 ani <math>n,</math> co najmniej jedna ścieżka [[Rekurencja|rekursji]] kończy się na wywołaniu <code>WspNewtonaRek(1, 0)</code> albo <code>WspNewtonaRek(1, 1)</code>. Ścieżka ta prowadzi przez <math>n</math> poziomów wywołań, w których parametr <math>n</math> był kolejno zmniejszany aż do jedności. Głębokość rekurencji, a zatem złożoność pamięciowa jest więc ściśle liniowa <math>\Theta(n),</math> i to w bardzo wrażliwym obszarze [[stos (informatyka)|stosu]].
Kolejnym krokiem pozwalającym na przyspieszenie obliczeń jest wykorzystanie [[programowanie dynamiczne|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 ==
Zachodzą następujące nierówności:
* <math>\mathrm{C}(n, k) \leqslant \frac{n^k}{k!},</math>
* <math>\mathrm{C}(n, k) \leqslant \left(\frac{n\cdot e}{k}\right)^k,</math>
* <math>\mathrm{C}(n, k) \geqslant \left(\frac{n}{k}\right)^k.</math>
== Uogólnienie na wielomiany wyższych stopni ==
Współczynniki dwumienne można uogólnić do '''współczynników wielomianowych'''. Definiuje się je w następujący sposób:
: <math>{n\choose k_1,k_2,\dots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!},</math>
przy czym:
: <math>\sum_{i=1}^rk_i=n.</math>
Współczynnik dwumienny określa współczynniki wyrażenia: <math>(x+y)^n,</math> podczas gdy współczynniki wielomianowe określają współczynniki wielomianu:
: <math>(x_1+x_2+\dots+x_r)^n.</math>
w następujący sposób:
: <math>(x_1 + x_2 + \cdots + x_r)^n
= \sum_{k_1,k_2,\dots,k_r} {n \choose k_1, k_2, \dots, k_r}
x_1^{k_1} x_2^{k_2} \cdots x_m^{k_r},</math>
gdzie sumujemy po wszystkich naturalnych <math>k</math> spełniających podane wcześniej reguły.
Dla <math>k=2</math> uzyskujemy współczynniki dwumianowe:
: <math>{n\choose k_1,k_2}={n\choose k_1, n-k_1}={n\choose k_1}= {n\choose k_2}.</math>
Interpretacja kombinatoryczna współczynników wielomianowych to liczba sposobów rozmieszczenia <math>n</math> rozróżnialnych elementów w <math>r</math> rozróżnialnych pudełkach, z których każde mieści dokładnie <math>k_i</math> elementów, gdzie <math>i</math> jest indeksem pudełka.
Współczynniki wielomianowe mają wiele własności podobnych do własności współczynników dwumianowych, takich jak rekurencja:
: <math>{n\choose k_1,k_2,\dots,k_r} = {n-1\choose k_1-1,k_2,\dots,k_r}+{n-1\choose k_1,k_2-1,\dots,k_r}+\ldots+{n-1\choose k_1,k_2,\dots,k_r-1}</math>
i symetria:
: <math>{n\choose k_1,k_2,\dots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\dots,k_{\sigma_r}},</math>
gdzie <math>(\sigma_i)</math> jest permutacją <math>(1,2,\dots,r).</math>
== Uogólnienie na liczby rzeczywiste i zespolone ==
Symbol Newtona uogólnia się na [[liczby rzeczywiste]] i [[liczby zespolone|zespolone]], korzystając z [[funkcje specjalne|funkcji specjalnej]] [[Funkcja Γ|gamma]]. Uogólnienie to opiera się na tożsamości:
: <math>\Gamma(n+1)=n!</math>
spełnionej dla [[liczby naturalne|naturalnych]] wartości <math>n</math>.
Możemy także przyjąć następującą (nierównoważną) definicję:<br />
Niech <math>z</math> będzie dowolną liczbą rzeczywistą lub zespoloną. Wówczas przez symbol <math>z\choose n</math> będziemy rozumieli wyrażenie
: <math>{z\choose n} = \prod_{k=1}^n\frac{z-n+k}{k} = \frac{z(z-1)(z-2)\cdots (z-n+1)}{n!}</math>
lub zapisane inaczej
: <math>{z\choose n} = \prod_{k=1}^n\frac{z-k+1}{k} = \frac{z(z-1)(z-2)\cdots (z-n+1)}{n!}.</math>
Następujący wzór, zwany ''górną negacją'', przydaje się do wyznaczania wartości symbolu Newtona dla ujemnych wartości z:
: <math>\binom{z}{n} = (-1)^n\binom{n-z-1}{n}.</math>
== Zobacz też ==
* [[kombinatoryka]]
* [[liczby Stirlinga]]
* [[permutacja]]
* [[wariacja bez powtórzeń]]
* [[wariacja z powtórzeniami]]
== Linki zewnętrzne ==
* [http://mathworld.wolfram.com/BinomialCoefficient.html Symbol Newtona] {{lang|en}} w encyklopedii [[MathWorld]]
[[Kategoria:Kombinatoryka]]
| 