Композиция натурального числа - История изменений

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

2026-10-24T13:31:24Z

← Предыдущая		Версия 13:31, 24 октября 2026
Строка 39:		Строка 39:

	Таким образом, $d_k(n) = \binom{n-1}{k-1}$.		Таким образом, $d_k(n) = \binom{n-1}{k-1}$.

			[[Файл:p23-01-composition-cuts.svg\|frame\|none\|800px\|alt=Шесть единиц, разделённые двумя разрезами на части 2, 1 и 3; формула C(5,2)=10\|Рис. 1. Композиция <math>6=2+1+3</math> соответствует двум разрезам после второго и третьего элемента. Разрезов всего <math>n-1=5</math>, выбираем <math>k-1=2</math>, поэтому <math>d_3(6)=C(5,2)=10</math>.]]

	{{Следствие		{{Следствие
	\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.		\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.

СВ в 10:34, 11 октября 2026

2026-10-11T10:34:05Z

← Предыдущая		Версия 10:34, 11 октября 2026
Строка 39:		Строка 39:

	Таким образом, $d_k(n) = \binom{n-1}{k-1}$.		Таким образом, $d_k(n) = \binom{n-1}{k-1}$.
	~~/{{якорь\|Число решений уравнения в неотрицательных целых числах}}/~~
	{{Следствие		{{Следствие
	\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.		\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.
Строка 58:		Строка 57:
	Следовательно, по утверждению, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.		Следовательно, по утверждению, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.

	~~/{{якорь\|Число решений неравенства в неотрицательных целых числах}}/~~
	{{Следствие		{{Следствие
	\|statement=Рассмотрим неравенство $x_1+x_2+\cdots + x_k \leq n$ (**), где $n$ {{---}} заданное число из $\mathbb{N}_0$.		\|statement=Рассмотрим неравенство $x_1+x_2+\cdots + x_k \leq n$ (**), где $n$ {{---}} заданное число из $\mathbb{N}_0$.

СВ в 10:28, 11 октября 2026

2026-10-11T10:28:17Z

← Предыдущая		Версия 10:28, 11 октября 2026
Строка 39:		Строка 39:

	Таким образом, $d_k(n) = \binom{n-1}{k-1}$.		Таким образом, $d_k(n) = \binom{n-1}{k-1}$.
			/{{якорь\|Число решений уравнения в неотрицательных целых числах}}/
	{{Следствие		{{Следствие
	\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.		\|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.
	Пусть, $N_=(n,k)$ {{---}} число решений этого уравнения на неотрицательных целых числах ($x_i\in\mathbb{N}_0$).		Пусть, $N_=(n,k)$ {{---}} число решений этого уравнения на неотрицательных целых числах ($x_i\in\mathbb{N}_0$).
	Тогда		Тогда
	<math> ~~\label{equation:x_1+...x_k=n}~~		<math>
	N_=(n,k) = \binom{n+k-1}{k-1}.		N_=(n,k) = \binom{n+k-1}{k-1}.
	</math>		</math>
Строка 56:		Строка 56:

	То есть, мы построили взаимно-однозначное соответствие между множеством решений уравнения и множеством композиций $n+k$ на $k$ слагаемых.		То есть, мы построили взаимно-однозначное соответствие между множеством решений уравнения и множеством композиций $n+k$ на $k$ слагаемых.
	Следовательно, по утверждению ~~\ref{claim:decomposition}~~, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.		Следовательно, по утверждению, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.

			/{{якорь\|Число решений неравенства в неотрицательных целых числах}}/
	{{Следствие		{{Следствие
	\|statement=Рассмотрим неравенство $x_1+x_2+\cdots + x_k \leq n$ (**), где $n$ {{---}} заданное число из $\mathbb{N}_0$.		\|statement=Рассмотрим неравенство $x_1+x_2+\cdots + x_k \leq n$ (**), где $n$ {{---}} заданное число из $\mathbb{N}_0$.
	Пусть, $N_\leq(n,k)$ {{---}} число решений этого неравенства на неотрицательных целых числах.		Пусть, $N_\leq(n,k)$ {{---}} число решений этого неравенства на неотрицательных целых числах.
	Тогда		Тогда
	<math> ~~\label{equation:x_1+...x_k<=n}~~		<math>
	N_\leq(n,k) = \binom{n+k}{k}.		N_\leq(n,k) = \binom{n+k}{k}.
	</math>		</math>

СВ: Новая страница: «{{Определение |definition= Композицией (или разложением) числа $n\in \mathbb{N}$ называется представл...»

2026-10-09T19:45:47Z

Новая страница: «{{Определение |definition= Композицией (или разложением) числа $n\in \mathbb{N}$ называется представл...»

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

{{Определение
|definition=
Композицией (или разложением) числа $n\in \mathbb{N}$ называется представление $n$ в виде упорядоченной суммы натуральных чисел
$(a_1, a_2, ..., a_k): n = a_1+a_2+...+a_k, a_i\in\mathbb{N}, k\in\mathbb{N}$.
Слагаемые, входящие в композицию, называют частями.
}}

Существует всего $8$ различных композиций числа $n=4$:
* 1+1+1+1
* 1+1+2
* 1+2+1
* 2+1+1
* 1+3
* 3+1
* 2+2
* 4

Обозначим $d_k(n)$ {{---}} число композиций $n$ длины $k$ (композиций состоящих из $k$ частей).

Число $d_k(n)$ композиций числа $n$ длины $k$ равно числу сочетаний из $n-1$ по $k-1$:
<math> \label{equation:decomposition}
d_k(n) = \binom{n-1}{k-1}.
</math>

Пусть $(a_1, a_2, ..., a_k)$ {{---}} произвольная композиция $n$ длины $k$: $n = a_1+a_2+...+a_k$.

Тогда $1\leq a_1 < a_1+a_2 < a_1+a_2+a_3 < ... < a_1+a_2+...+a_{k-1}\leq n-1$.
Обозначим $b_i = a_1+a_2+...+a_i$,\quad $1\leq i\leq k-1$.
Тогда $\{b_1,...,b_{k-1}\}\subset \{1,...,n-1\}$, причем никакие два $b_i$ и $b_j$ не совпадают.
Значит, $\{b_1,...,b_{k-1}\}$ {{---}} некоторая выборка $k-1$ элемента из $n-1$.
При этом различным композициям $n$ длины $k$ будут соответствовать разные выборки из $n-1$ по $k-1$. Следовательно, $d_k(n) \leq \binom{n-1}{k-1}$.

Пусть теперь $\{b_1,...,b_{k-1}\}$ произвольная выборка мощности $k-1$ из $n-1$. Пусть, для определенности, $b_1<b_2<...<b_{k-1}$.
Тогда, $b_1+(b_2-b_1) + (b_3-b_2)% + (b_4-b_3) + \cdots + (b_{k-1} - b_{k-2}) + (n-b_{k-1}) = n$.

Обозначим $a_1 = b_1$, $a_k = n-b_{k-1}$ и $a_i = b_i - b_{i-1}$, $i=\overline{2, k-1}$.
Тогда, $n = a_1+a_2+\cdots+a_k$ {{---}} композиция числа $n$ длины $k$.
Причем разным выборкам будут соответствовать различные композиции и, следовательно, $d_k(n) \geq \binom{n-1}{k-1}$.

Таким образом, $d_k(n) = \binom{n-1}{k-1}$.

{{Следствие
|statement=Рассмотрим уравнение $x_1+x_2+\cdots + x_k = n$ (*), где $n$ {{---}} заданное число из $\mathbb{N}_0$.
Пусть, $N_=(n,k)$ {{---}} число решений этого уравнения на неотрицательных целых числах ($x_i\in\mathbb{N}_0$).
Тогда
<math> \label{equation:x_1+...x_k=n}
N_=(n,k) = \binom{n+k-1}{k-1}.
</math>
}}

Пусть $n = c_1+c_2+\cdots+c_k$, $c_i\in\mathbb{N}_0$.
Тогда $n+k = (c_1+1)+ (c_2+1)+\cdots + (c_k+1)$, $c_i\in\mathbb{N}$.
Таким образом, любому решению уравнения (*) соответствует композиция $n+k$ длины $k$. И, наоборот, для любой композиции
$n+k = a_1+a_2+...+a_k,\quad a_i\in\mathbb{N}$
набор $\{(a_1-1), (a_2-1),...,(a_k-1) \}$ является решением уравнения (*).

То есть, мы построили взаимно-однозначное соответствие между множеством решений уравнения и множеством композиций $n+k$ на $k$ слагаемых.
Следовательно, по утверждению \ref{claim:decomposition}, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.

{{Следствие
|statement=Рассмотрим неравенство $x_1+x_2+\cdots + x_k \leq n$ (**), где $n$ {{---}} заданное число из $\mathbb{N}_0$.
Пусть, $N_\leq(n,k)$ {{---}} число решений этого неравенства на неотрицательных целых числах.
Тогда
<math> \label{equation:x_1+...x_k<=n}
N_\leq(n,k) = \binom{n+k}{k}.
</math>
}}

Пусть $c_1+c_2+\cdots + c_k\leq n$, $c_i\in\mathbb{N}_0$.
Тогда обозначим $c_{k+1} = n-c_1+c_2+\cdots + c_k$.
$\{c_1, c_2,...,c_k, c_{k+1}\}$ {{---}} решение уравнения $x_1+x_2+\cdots + x_k + x_{k+1} = n$.

Обратно, для любого решения $c_1, c_2,..., c_k ,c_{k+1}$ уравнения $x_1+x_2+\cdots + x_k + x_{k+1} = n$ верно, что $c_1+c_2+\cdots + c_k\leq n$.

Таким образом, множеству решений неравенства (**) взаимооднозначно соответствует множество решений уравнения $x_1+x_2+\cdots + x_k + x_{k+1} = n$.

Тогда по следствию $N_\leq(n,k) = N_=(n,k+1) = \binom{n+k}{k}$.

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