Symbol Newtona

Dla liczb naturalnych spełniających warunki 0 ≤ k ≤ n definiujemy funkcję:
$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! (n - k)!}$

Symbol $(\begin{matrix} n \\ k \end{matrix})$ nazywamy symbolem Newtona i czytamy n nad k lub n po k lub k z n.
Podstawowe własności tej funkcji to:
$(\begin{matrix} n \\ 0 \end{matrix}) = (\begin{matrix} n \\ n \end{matrix}) = 1$
$(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$
$(\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ n + k \end{matrix}) = (\begin{matrix} n + 1 \\ k + 1 \end{matrix})$ , dla k = 0, 1, ... , n-1

Wartości liczbowe symbolu Newtona $(\begin{matrix} n \\ k \end{matrix})$ możemy zapisać w formie zwanej trójkątem 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
            . . . . . . . . . . . . . . . . .

Kolejnym wierszom trójkąta odpowiadają kolejne wartości n, kolejnym wyrazom w każdym wierszu - wartości k. Zgodnie z własnościami każdy wiersz zaczyna się i kończy na liczbue 1, a każdy element wewnątrz wiersza jest sumą dwóch leżących nad nim elementów. Trókąt Pascala umożliwia szybkie znajdowanie wartości symbolu Newtona.

Wartość symbolu Newtona można obliczyć korzystając ze wzoru iteracyjnego:
$(\begin{matrix} n \\ k \end{matrix}) = \frac{n (n - 1) \cdot ... \cdot (n - k + 1)}{1 \cdot 2 \cdot ... \cdot k}$
Jest to prostsza, a zarazem szybka metoda obliczania wartości symbolu Newtona.