Треугольник Паскаля - История изменений

СВ в 13:13, 24 октября 2026

2026-10-24T13:13:02Z

← Предыдущая		Версия 13:13, 24 октября 2026
Строка 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>.]]

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

СВ в 19:23, 9 октября 2026

2026-10-09T19:23:15Z

← Предыдущая		Версия 19:23, 9 октября 2026
Строка 38:		Строка 38:

	Здесь каждый элемент $\binom{n}{k}$, кроме первого столбца и ниже диагонали, является суммой элемента слева сверху, который соответствует $\binom{n-1}{k-1}$, и верхнего {{---}} $\binom{n-1}{k}$.		Здесь каждый элемент $\binom{n}{k}$, кроме первого столбца и ниже диагонали, является суммой элемента слева сверху, который соответствует $\binom{n-1}{k-1}$, и верхнего {{---}} $\binom{n-1}{k}$.

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

СВ: Новая страница: «Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$ Пусть множество $S$...»

2026-10-09T19:22:54Z

Новая страница: «Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда <math> \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. </math> Пусть множество $S$...»

Новая страница

Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда
<math>
\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>
\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}$.

Треугольник Паскаля - История изменений

СВ в 13:13, 24 октября 2026

СВ в 19:23, 9 октября 2026

СВ: Новая страница: «Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. Пусть множество $S$...»

СВ: Новая страница: «Пусть $k,n\in\mathbb{N}$ и $2\leq k\leq n$. Тогда $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$ Пусть множество $S$...»