Symbol Newtona

Dla liczb naturalnych spełniających warunki $0 \le k \le n$ definiujemy funkcję:
$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$
Symbol $\binom{n}{k}$ nazywamy symbolem Newtona i czytamy n nad k lub n po k lub też k z n.

Wzór iteracyjny: ${n \choose k} = \frac{1 \cdot 2 \cdot ... \cdot n}{ 1 \cdot2 \cdot \ldots \cdot k \cdot (1 \cdot 2 \cdot \ldots \cdot (n-k))} = \frac{n(n-1) \cdot \ldots \cdot (n-k+1)}{1 \cdot 2 \cdot \ldots \cdot k}$


Wzór rekurencyjny: ${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}$.

---

Zastosujmy wzór iteracyjny i rekurencyjny na przykładzie dla $n=4$ i $k=2$.

Wzór iteracyjny:
${4\choose 2} = \frac{4!}{2!(4-2)!} = \frac{4 \cdot 3}{1 \cdot 2} = 6$.

Wzór rekurencyjny:
Dla lepszej przejrzystości przyjmijmy $\binom{n}{k} = f(n,k)$. Wówczas
$f(4, 2) = f(3, 1) + f(3, 2) = $ $f(2, 0) + f(2, 1) + f(2, 1) + f(2, 2) = $ $f(2, 0) + f(1, 0) + f(1, 1) + f(1, 0) + (1, 1) + F(2, 2) = $ $1 + 1 + 1 + 1 + 1 + 1 = 6$.

Wzór iteracyjny jest szybką metodą obliczania wartości symbolu Newtona, choć niekiedy dla dużych wartości liczby $n$ liczba mnożeń, które należy wykonać jest nadal spora. W przypadku wzoru rekurencyjnego dużą niedogodnością jest powielanie obliczeń.

$$\binom{n}{0} = \binom{n}{n} = 1$$ $$\binom{n}{k} = \binom{n}{n - k}$$ $$\binom{n}{k} + \binom{n}{n + k} = \binom{n + 1 }{k + 1}$$
Interesującą własnością symbolu Newtona jest to, że jego wartości zapisać można 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   35  56  56  35  28  8   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 liczbą $1$, a każda liczba wewnątrz wiersza jest sumą dwóch liczb znajdujących się bezpośrednio nad nią.

Za pomocą symbolu Newtona możemy wyznaczyć liczbę k-elementowych podzbiorów w zbiorze n-elementowym (kombinacje).

Przykład
Na ile sposobów możemy ze zbioru $\{A, B, C, D\}$ wybrać dwie litery?

Jeśli przyjmiemy, że kolejność liter w tak zadanym pytaniu nie jest istotna, to mamy 6 sposobów wyboru dwóch liter (dwuliterowych podzbiorów). Oto one: $\{A,B\}, \{A,C\}, \{A,D\}, \{B,C\}, \{B,D\}, \{C,D\}$. W tym przykładzie liczba sposobów była na tyle mała, że wypisaliśmy wszystkie możliwe sposoby i je policzyliśmy. Ale nie ma potrzeby wypisywania wszystkich sposobów, aby poznać ich liczbę. Można skorzystać z symbolu Newtona i obliczyć liczbę takich sposobów, bez uciekania się wypisywania ich wszystkich.
Zastosujmy symbol Newtona na naszym przykładzie.
Wybieramy $2$-elementowe podzbiory ze zbioru $4$-elementowego: ${4\choose 2} = \frac{4!}{2!(4-2)!} = \frac{1\cdot2\cdot3\cdot4}{2\cdot2}=2\cdot3 = 6$.