Треугольник Паскаля: различия между версиями
СВ (обсуждение | вклад) |
СВ (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Тогда $|\binom{S}{k}| = |A| + |B|$. Учитывая, что $|\binom{S}{k}| = \binom{n}{k}$, $|A| = \binom{n-1}{k-1}$ и $|B| = \binom{n-1}{k}$, | Тогда $|\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}.$. | получаем искомое равенство $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$. | ||
[[Файл:p15-01-partition-proof.svg|frame|none|900px|alt=Все сочетания из четырёх элементов по два разбиты на содержащие четвёртый элемент и не содержащие его, по три в каждом классе|Рис. 1. Все <math>k</math>-элементные сочетания из <math>S</math> делятся на два класса: содержащие <math>s_n</math> и не содержащие <math>s_n</math>. Для <math>S=\{1,2,3,4\}</math> и <math>k=2</math> это даёт <math>C_4^2 = C_3^1 + C_3^2 = 3 + 3 = 6</math>.]] | |||
Положим следующие естественные начальные условия для числа сочетаний из $n$ по $k$: | Положим следующие естественные начальные условия для числа сочетаний из $n$ по $k$: | ||
| Строка 17: | Строка 19: | ||
* $\binom{n}{0} = 1$ для любых $n\in\mathbb{N}$; | * $\binom{n}{0} = 1$ для любых $n\in\mathbb{N}$; | ||
* $\binom{n}{k} = 0$ для любых $k > n$. | * $\binom{n}{k} = 0$ для любых $k > n$. | ||
[[Файл:p15-02-pascal-boundaries.svg|frame|none|900px|alt=Фрагмент таблицы сочетаний: единицы в первом столбце и на диагонали, нули при k больше n; справа разобран крайний случай C(4,4) = 1 + 0|Рис. 2. Начальные условия: первый столбец и диагональ заполнены единицами, клетки при <math>k>n</math> — нулями. Нуль на диагонали обнуляет второе слагаемое: <math>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}.$, можно построить следующую таблицу, которую называют треугольником Паскаля: | Тогда, пользуясь рекуррентным соотношением $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$, можно построить следующую таблицу, которую называют треугольником Паскаля: | ||
| Строка 38: | Строка 43: | ||
Здесь каждый элемент $\binom{n}{k}$, кроме первого столбца и ниже диагонали, является суммой элемента слева сверху, который соответствует $\binom{n-1}{k-1}$, и верхнего {{---}} $\binom{n-1}{k}$. | Здесь каждый элемент $\binom{n}{k}$, кроме первого столбца и ниже диагонали, является суммой элемента слева сверху, который соответствует $\binom{n-1}{k-1}$, и верхнего {{---}} $\binom{n-1}{k}$. | ||
[[Файл:p15-03-pascal-recurrence.svg|frame|none|900px|alt=Треугольник Паскаля, в котором число 10 в строке n = 5 получается сложением 6 и 4 из строки n = 4|Рис. 3. Каждое внутреннее число треугольника — сумма двух чисел над ним: <math>C_5^3 = C_4^2 + C_4^3 = 6 + 4 = 10</math>.]] | |||
Конспект: [[Дискретная математика]] | Конспект: [[Дискретная математика]] | ||
Текущая версия на 16:13, 24 октября 2026
Пусть $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}$.
Конспект: Дискретная математика