Разбиения натурального числа
Существует $5$ различных разбиений числа $n=4$:
- 1+1+1+1
- 2+1+1
- 2+2
- 3+1
- 4
Действительно, можно считать, что разбиение $\{\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) = 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]
Конспект: Дискретная математика