Треугольник Паскаля
Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда [math]\displaystyle{ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. }[/math]
Пусть множество $S$ имеет вид: $S = \{s_1, s_2, ..., s_n\}$. Определим множества $A$ и $B$ следующим образом: $A = \left\{ \{s_{i_1}, s_{i_2}, ..., s_{i_{k-1}}, s_n\} | \{s_{i_1}, s_{i_1}, ..., s_{i_{k-1}}\}\in \binom{S\setminus\{s_n\}}{k-1} \right\}$, $B = \binom{S\setminus\{s_n\}}{k}$.
Очевидно, $A\cap B = \varnothing$. Кроме того, можно видеть, что $\binom{S}{k} = A\cup B$, поскольку все $k$-элементные сочетания из $S$, содержащие $s_n$, находятся в $A$, а все такие $k$-элементные сочетания, которые не содержат $s_n$, лежат в $B$. Тогда $|\binom{S}{k}| = |A| + |B|$. Учитывая, что $|\binom{S}{k}| = \binom{n}{k}$, $|A| = \binom{n-1}{k-1}$ и $|B| = \binom{n-1}{k}$, получаем искомое равенство $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$.
Положим следующие естественные начальные условия для числа сочетаний из $n$ по $k$:
- $\binom{0}{0} = 1$;
- $\binom{n}{0} = 1$ для любых $n\in\mathbb{N}$;
- $\binom{n}{k} = 0$ для любых $k > n$.
Тогда, пользуясь рекуррентным соотношением $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$, можно построить следующую таблицу, которую называют треугольником Паскаля:
[math]\displaystyle{ \begin{array}{|c|ccccccccc|} \hline n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ... \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\ 2 & 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & ... \\ 3 & 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & ... \\ 4 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & ... \\ 5 & 1 & 5 & 10 & 10 & 5 & 1 & 0 & 0 & ... \\ 6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & ... \\ 7 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & ... \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \hline \end{array} }[/math]
Здесь каждый элемент $\binom{n}{k}$, кроме первого столбца и ниже диагонали, является суммой элемента слева сверху, который соответствует $\binom{n-1}{k-1}$, и верхнего — $\binom{n-1}{k}$.