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

2026-10-24T13:32:36Z

← Предыдущая		Версия 13:32, 24 октября 2026
Строка 11:		Строка 11:
	* 3+1		* 3+1
	* 4		* 4

			[[Файл:p24-01-compositions-vs-partitions.svg\|frame\|none\|800px\|alt=Восемь композиций числа 4 и пять разбиений; три композиции 1+1+2, 1+2+1, 2+1+1 дают одно разбиение 2+1+1\|Рис. 1. У числа 4 восемь композиций и пять разбиений. Композиции <math>1+1+2</math>, <math>1+2+1</math> и <math>2+1+1</math> — три порядка одной суммы, поэтому как разбиение они дают одно <math>2+1+1</math>.]]

	{{Замечание		{{Замечание

СВ в 09:57, 11 октября 2026

2026-10-11T09:57:16Z

← Предыдущая		Версия 09:57, 11 октября 2026
Строка 93:		Строка 93:

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

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

СВ: Новая страница: «{{Определение |definition= Набор $(\lambda_1, \lambda_2, ..., \lambda_k)$, $\lambda_i\in\mathbb{N}$, называется разбиением ч...»

2026-10-09T19:48:57Z

Новая страница: «{{Определение |definition= Набор $(\lambda_1, \lambda_2, ..., \lambda_k)$, $\lambda_i\in\mathbb{N}$, называется разбиением ч...»

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

{{Определение
|definition=
Набор $(\lambda_1, \lambda_2, ..., \lambda_k)$, $\lambda_i\in\mathbb{N}$, называется разбиением числа $n\in \mathbb{N}$, если
$n = \lambda_1 + \lambda_2 + \cdots + \lambda_k$, $\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_k >0$
}}

Существует $5$ различных разбиений числа $n=4$:
* 1+1+1+1
* 2+1+1
* 2+2
* 3+1
* 4

{{Замечание
|content=Можно использовать и другое определение разбиения натурального числа:
}}
{{Определение
|definition=
Разбиением числа $n\in \mathbb{N}$ называется представление $n$ в виде неупорядоченной суммы натуральных чисел.
}}

Действительно, можно считать, что разбиение $\{\lambda_1, \lambda_2, ..., \lambda_k\}$ {{---}} такой произвольный неупорядоченный набор, что
$n = \lambda_1 + \lambda_2 + \cdots + \lambda_k$.
Тогда, расставив элементы $\lambda_i$ в другом порядке, мы получим то же самое разбиение. Чтобы получить возможность определять,
имеем ли мы дело с двумя различными разбиениями, или с одним и тем же набором, но с элементами, следующими в другом порядке,
удобно договориться расставлять элементы $\lambda_i$ по убыванию.
В таком случае, любому разбиению будет однозначно соответствовать упорядоченная последовательность, удовлетворяющая определению разбиения натурального числа.

Обозначим $p_k(n)$ {{---}} число разбиений $n$ на $k$ частей.

Пусть $k, n\in\mathbb{N}$, $k>1$ и $n>k$. Тогда
<math>
p_k(n) = p_{k-1}(n-1)+p_k(n-k).
</math>

Пусть
$S_k(n) = \{(\lambda_1, \lambda_2, ..., \lambda_k) | n = \lambda_1 + \lambda_2 + \cdots + \lambda_k, \lambda_1\geq \lambda_2\geq \cdots \geq \lambda_k >0, \lambda_i\in\mathbb{N}, i=\overline{1,k} \}$,
$A = \{(\lambda_1, \lambda_2, ..., \lambda_k) | (\lambda_1, \lambda_2, ..., \lambda_k)\in S_k(n), \lambda_k=1\}$,
$B = \{(\lambda_1, \lambda_2, ..., \lambda_k) | (\lambda_1, \lambda_2, ..., \lambda_k)\in S_k(n), \lambda_k\geq 2\}$.

Тогда $S_k(n) = A\cup B$ и $A\cap B = \varnothing$; $|S_k(n)| = |A|+|B|$.

$|A| = |\{(\lambda_1, \lambda_2, ..., \lambda_{k-1}) | \lambda_1 + \lambda_2 + \cdots + \lambda_{k-1} = n-1, \lambda_1\geq \lambda_2\geq \cdots \geq \lambda_{k-1} >0,
\lambda_i\in\mathbb{N}\}| = |S_{k-1}(n-1)| = p_{k-1}(n-1)$.

$|B| = |\{(\lambda_1, \lambda_2, ..., \lambda_{k}) | \lambda_1 + \lambda_2 + \cdots + \lambda_{k} = n, \lambda_1\geq \lambda_2\geq \cdots \geq \lambda_{k} >1, \lambda_i\in\mathbb{N}\}| = $

Сделаем замену $\mu_i = \lambda_i-1$, $i=overline{1,k}$.
$=|\{(\mu_1, \mu_2, ..., \mu_{k}) | \mu_1 + \mu_2 + \cdots + \mu_{k} = n-k, \mu_1\geq \mu_2\geq \cdots \geq \mu_{k} >0, \mu_i\in\mathbb{N}\}| = |S_{k}(n-k)| = p_{k}(n-k)$.

$|S_k(n)| = p_k(n) = p_{k-1}(n-1)+p_k(n-k)$.

{{Замечание
|content=Несмотря на схожесть определений, вычисление величины $p_k(n)$ оказывается гораздо более сложной задачей, чем вычисление $d_k(n)$.
Если для числа композиций мы имеем явную формулу, то для числа разбиений мы получили только рекуррентное выражение $p_k(n) = p_{k-1}(n-1)+p_k(n-k)$,
которое, тем не менее, позволяет нам вычислить $p_k(n)$ для любых натуральных $n$ и $k$, пользуясь начальными условиями:
$\forall n\in\mathbb{N}$ $p_n(n) = 1$, $p_1(n)=1$; если $k>n$, то $p_k(n) = 0$.
}}

Заполним таблицу первых значений $p_k(n)$, пользуясь начальными значениями и формулой $p_k(n) = p_{k-1}(n-1)+p_k(n-k)$.

<math>
\begin{array}{c|cccccccc}
n \backslash k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots\\
\hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\
2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots\\
3 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & \cdots\\
4 & 1 & 2 & 1 & 1 & 0 & 0 & 0 & \cdots\\
5 & 1 & 2 & 2 & 1 & 1 & 0 & 0 & \cdots\\
6 & 1 & 3 & 3 & 2 & 1 & 1 & 0 & \cdots\\
7 & 1 & 3 & 4 & 3 & 2 & 1 & 1 & \cdots\\
\vdots & \vdots & \vdots & \vdots &
\vdots & \vdots & \vdots & \vdots &
\ddots\\
\end{array}
</math> 
<math>p_2(3) = p_1 (2) + p_2(1) = p_1(2) = 1,</math> 
<math>p_2(4) = p_1 (3) + p_2(2) = 1+1 = 2,</math> 
<math>p_3(4) = p_2 (3) + p_3(1) = p_2(3) = 1,</math> 
<math>p_2(5) = p_1 (4) + p_2(3) = 1 + 1 = 2,</math> 
<math>p_3(5) = p_2 (4) + p_3(2) = p_2(4) = 2,</math> 
<math>p_4(5) = p_3 (4) + p_4(1) = p_3(4) = 1,</math> 
<math>p_2(6) = p_1 (5) + p_2(4) = 1+2 = 3,</math> 
<math>p_3(6) = p_2 (5) + p_3(3) = 2+1 = 3,</math> 
<math>p_4(6) = p_3 (5) + p_4(2) = 2,</math> 
<math>p_5(6) = p_4 (5) + p_5(1) = 1,</math> 
<math>p_2(7) = p_1 (6) + p_2(5) = 1 + 2 = 3,</math> 
<math>p_3(7) = p_2 (6) + p_3(4) = 3+1 =4,</math> 
<math>p_4(7) = p_3 (6) + p_4(3) = 3,</math> 
<math>p_5(7) = p_4 (6) + p_5(2) = 2,</math> 
<math>p_6(7) = p_5 (6) + p_6(1)= 1.</math>

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

Разбиения натурального числа - История изменений

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

СВ в 09:57, 11 октября 2026

СВ: Новая страница: «{{Определение |definition= Набор $(\lambda_1, \lambda_2, ..., \lambda_k)$, $\lambda_i\in\mathbb{N}$, называется разбиением ч...»