Треугольник Паскаля

Пусть $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}.$.

Рис. 1. Все [math]\displaystyle{ k }[/math]-элементные сочетания из [math]\displaystyle{ S }[/math] делятся на два класса: содержащие [math]\displaystyle{ s_n }[/math] и не содержащие [math]\displaystyle{ s_n }[/math]. Для [math]\displaystyle{ S=\{1,2,3,4\} }[/math] и [math]\displaystyle{ k=2 }[/math] это даёт [math]\displaystyle{ C_4^2 = C_3^1 + C_3^2 = 3 + 3 = 6 }[/math].

Положим следующие естественные начальные условия для числа сочетаний из $n$ по $k$:

• $\binom{0}{0} = 1$;
• $\binom{n}{0} = 1$ для любых $n\in\mathbb{N}$;
• $\binom{n}{k} = 0$ для любых $k > n$.

Рис. 2. Начальные условия: первый столбец и диагональ заполнены единицами, клетки при [math]\displaystyle{ k\gt n }[/math] — нулями. Нуль на диагонали обнуляет второе слагаемое: [math]\displaystyle{ C_4^4 = C_3^3 + C_3^4 = 1 + 0 = 1 }[/math].

Тогда, пользуясь рекуррентным соотношением $\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}$.

Рис. 3. Каждое внутреннее число треугольника — сумма двух чисел над ним: [math]\displaystyle{ C_5^3 = C_4^2 + C_4^3 = 6 + 4 = 10 }[/math].

Конспект: Дискретная математика