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

Определение:

Композицией (или разложением) числа $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]\displaystyle{ \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}$.

Рис. 1. Композиция [math]\displaystyle{ 6=2+1+3 }[/math] соответствует двум разрезам после второго и третьего элемента. Разрезов всего [math]\displaystyle{ n-1=5 }[/math], выбираем [math]\displaystyle{ k-1=2 }[/math], поэтому [math]\displaystyle{ d_3(6)=C(5,2)=10 }[/math].

Следствие:

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

Пусть, $N_=(n,k)$ — число решений этого уравнения на неотрицательных целых числах ($x_i\in\mathbb{N}_0$). Тогда

[math]\displaystyle{ 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$ слагаемых. Следовательно, по утверждению, $N_=(n,k) = d_k(n+k) = \binom{n+k-1}{k-1}$.

Следствие:

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

Пусть, $N_\leq(n,k)$ — число решений этого неравенства на неотрицательных целых числах. Тогда

[math]\displaystyle{ 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}$.

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