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

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

Набор $(\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

Замечание

Можно использовать и другое определение разбиения натурального числа:

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

Разбиением числа $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]\displaystyle{ 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)$.

Замечание

Несмотря на схожесть определений, вычисление величины $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]\displaystyle{ \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]\displaystyle{ p_2(3) = p_1 (2) + p_2(1) = p_1(2) = 1, }[/math]
[math]\displaystyle{ p_2(4) = p_1 (3) + p_2(2) = 1+1 = 2, }[/math]
[math]\displaystyle{ p_3(4) = p_2 (3) + p_3(1) = p_2(3) = 1, }[/math]
[math]\displaystyle{ p_2(5) = p_1 (4) + p_2(3) = 1 + 1 = 2, }[/math]
[math]\displaystyle{ p_3(5) = p_2 (4) + p_3(2) = p_2(4) = 2, }[/math]
[math]\displaystyle{ p_4(5) = p_3 (4) + p_4(1) = p_3(4) = 1, }[/math]
[math]\displaystyle{ p_2(6) = p_1 (5) + p_2(4) = 1+2 = 3, }[/math]
[math]\displaystyle{ p_3(6) = p_2 (5) + p_3(3) = 2+1 = 3, }[/math]
[math]\displaystyle{ p_4(6) = p_3 (5) + p_4(2) = 2, }[/math]
[math]\displaystyle{ p_5(6) = p_4 (5) + p_5(1) = 1, }[/math]
[math]\displaystyle{ p_2(7) = p_1 (6) + p_2(5) = 1 + 2 = 3, }[/math]
[math]\displaystyle{ p_3(7) = p_2 (6) + p_3(4) = 3+1 =4, }[/math]
[math]\displaystyle{ p_4(7) = p_3 (6) + p_4(3) = 3, }[/math]
[math]\displaystyle{ p_5(7) = p_4 (6) + p_5(2) = 2, }[/math]
[math]\displaystyle{ p_6(7) = p_5 (6) + p_6(1)= 1. }[/math]

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