Symbol Newtona - Polski Serwis Naukowy

Symbol Newtona ${n \choose k}$ (nazywany też współczynnikiem dwumianowym, czytany n nad k, n po k lub k z n) jest to funkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako: ${n \choose k} = \frac{n!}{k!(n-k)!}$

gdzie wykrzyknik oznacza silnię.

Wartość symbolu Newtona można wyrazić wzorem rekurencyjnym: ${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}$

Jest on równoważny definicji podanej wyżej, można więc uważać go za alternatywną definicję symbolu Newtona.

Dzielnik – w matematyce dla danej liczby całkowitej liczba całkowita, która dzieli ją bez reszty. W matematyce elementarnej dzielnikiem nazywa się dowolną liczbę, przez którą się dzieli.
Rekurencja albo rekursja (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie. Wbrew próbom rozróżnienia terminów [potrzebne źródło] rekursja i rekurencja w rzeczywistości słowa te mają identyczne znaczenie[potrzebne źródło].

Symbol Newtona pojawia się również we wzorze dwumiennym Newtona jako współczynnik w k-tym wyrazie rozwinięcia n-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 Newtona równy jest liczbie wszystkich kombinacji k-elementowych ze zbioru n-elementowego (k-elementowych podzbiorów zbioru n-elementowego). Liczba ta jest też oznaczana jako $C^k_n$ ; w literaturze angielskiej spotyka się oznaczenie ${}^nC_k\,$ , w amerykańskiej ${}_nC_k\,$ (od wyrażenia "n choose k" - "n brane po k").

Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.
Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

Zatem poniższe symbole są równoważnymi oznaczeniami liczby dwuelementowych kombinacji ze zbioru siedmioelementowego: ${7 \choose 2} = C^2_7 = {}^7C_2 = {}_7C_2 = 21$

Pochodzenie wzoru iteracyjnego

Każdą kombinację k-elementową ze zbioru n-elementowego $A\,$ można utworzyć wybierając kolejno k różnych elementów. Uzyskuje się w ten sposób k-elementowy ciąg, czyli wariację ze zbioru $A\,$ . Wariacji takich jest $V_n^k=\frac{n!}{(n-k)!}$ .

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 k-elementowych kombinacji jest więc mniejsza od liczby k-elementowych wariacji tylokrotnie, ile jest różnych porządków (przestawień, czyli permutacji) takiego ciągu. A ponieważ permutacji k-elementowych jest

Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka stosu można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.
Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.

$P_k = k!\,$ ,

ostatecznie: $C_n^k = \frac{V_n^k}{P_k} = \frac{n!}{(n-k)!} \cdot {1 \over k!} = \frac{n!}{k!(n-k)!}$ .

Pochodzenie wzoru rekurencyjnego

Z każdego zbioru n-elementowego można wybrać tylko jedną kombinację 0-elementową (czyli podzbiór pusty, $\varnothing$ ), stąd liczba kombinacji pustych $C_n^0=1$ .

Z każdego zbioru n-elementowego $A\,$ można wybrać tylko jedną kombinację n-elementową $B\,$ (podzbiór niewłaściwy, równy całemu zbiorowi: $B=A\,$ ), stąd liczba takich kombinacji $C_n^n=1$ .

Oba powyższe stwierdzenia dotyczą oczywiście także zbioru pustego $A=\varnothing$ (n=0).

Silnią liczby naturalnej n (w notacji matematycznej: n!, co czytamy „n silnia”) nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie n! wprowadził w 1808 roku Christian Kramp.
Wariacją z powtórzeniami k-wyrazową zbioru n-elementowego A nazywa się każdy k-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu).

Niech teraz $A\,$ będzie niepustym zbiorem n-elementowym (n>0). Wyłączymy zeń jeden element, $a\,$ i oznaczymy pozostały podzbiór (n-1)-elementowy przez $A'\,$ : $A'=A\setminus\{a\}$

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

Każdą k-elementową kombinację $K\,$ zawierającą $a\,$ można przedstawić jako unię pewnej (k-1)-elementowej kombinacji $K'\,$ i jednoelementowego zbioru $\{a\}\,$ . Ponieważ przy tym $K'\,$ zawiera się w (n-1)-elementowym $A'\,$ , to kombinacji takich jest $C_{n-1}^{k-1}$ .

Każda k-elementowa kombinacja nie zawierająca $a\,$ sama zawiera się w $A\setminus\{a\}$ , czyli w (n-1)-elementowym zbiorze $A'\,$ . Zatem kombinacji takich jest $C_{n-1}^k$ .

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

Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb.
Liczby zespolone – liczby będące elementami rozszerzenia ciała liczb rzeczywistych o jednostkę urojoną i, tj. pierwiastek wielomianu x + 1 (innymi słowy, jednostka urojona spełnia równanie i = − 1). Każda liczba zespolona z może być zapisana w postaci z = a + bi, gdzie a,b są pewnymi liczbami rzeczywistymi, nazywanymi odpowiednio częścią rzeczywistą oraz częścią urojoną liczby z.

$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$

Tożsamości algebraiczne

Skracając w definicji czynnik $(n-k)!\,$ otrzymuje się: ${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}$

co dla dodatnich wartości k rozwija się do uproszczonej postaci iteracyjnej: ${n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdots k}$

Dla k=0 puste iloczyny stają się równe jedności, i w efekcie: ${n \choose 0} = 1.$

Inne tożsamości:

liczba kombinacji dopełniających:

${n \choose k} = {n \choose n-k}$

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

Kombinacja bez powtórzeń to każdy podzbiór zbioru skończonego. Kombinacją k-elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0≤k≤n). Używa się też terminu "kombinacja z n elementów po k elementów" lub wręcz "kombinacja z n po k".
Sir Isaac Newton (ur. 4 stycznia 1643 w Woolsthorpe-by-Colsterworth, zm. 31 marca 1727 w Kensington) – angielski fizyk, matematyk, astronom, filozof, historyk, badacz Biblii i alchemik.

${n \choose 0} = {n \choose n} = 1$

liczba kombinacji w zbiorze pustym:

${0 \choose 0} = 1$

${n \choose k+1} = {n \choose k} \cdot \frac{n-k}{k+1}$

suma wpółczynników dwumianu Newtona $(1+1)^{n}\,$ :

$\sum _{k=0} ^{n} {n \choose k} = 2^n$

$\sum_{k=0}^{n} {n \choose k}^2 = {2n \choose n}$

$\sum_{k=0}^n (-1)^k \cdot {n \choose k} = 0$

$\sum _{k=1} ^{n} k{n \choose k} = n2^{n-1}$

$\sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n}$

${r \choose k} = \frac{r}{k} {r-1 \choose k-1}, k \neq 0$

$(r-k){r \choose k} = r{r-1 \choose k}$

Teoria liczb

Liczba pierwsza $p$ dzieli każdą liczbę ${p \choose k}$ dla $k=1,2,\ldots,p-1$ .

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

Wniosek: W ciele $\mathbb{Z}_p$ zachodzi równość: $(a+b)^p=a^p+b^p$ .

Pascal – dawniej jeden z najpopularniejszych języków programowania, uniwersalny, wysokiego poziomu, ogólnego zastosowania, oparty na języku Algol. Został opracowany przez Niklausa Wirtha w 1970 roku. Nazwa języka pochodzi od nazwiska francuskiego fizyka, matematyka i filozofa Blaise Pascala.[potrzebne źródło]
Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)