Разбиение числа

---

Разбие́ние натурального числа́ ${\displaystyle n}$ — это такое представление числа ${\displaystyle n}$ в виде суммы положительных целых чисел ${\displaystyle \lambda _{1}+\lambda _{2}+\dots +\lambda _{m}}$, которое, в отличие от композиции, не учитывает порядок слагаемых. Слагаемые ${\displaystyle \lambda _{k}}$ в разбиении называются частями. В канонической записи разбиения слагаемые перечисляются в невозрастающем порядке.

Если ${\displaystyle \lambda _{1}\geq \lambda _{2}\dots \geq \lambda _{m}}$, то соответствующее этому набору чисел разбиение обычно обозначается как {${\displaystyle \lambda _{1},\lambda _{2},\dots \lambda _{m}}$} = ${\displaystyle \lambda }$. Число ${\displaystyle n}$ при этом называют мощностью разбиения и обозначают ${\displaystyle |\lambda |}$, а число ${\displaystyle m}$ называют длиной разбиения и обозначают ${\displaystyle l(\lambda )}$.

Число разбиений ${\displaystyle p(n)}$ натурального числа ${\displaystyle n}$ является одним из фундаментальных объектов изучения в комбинаторике.

Например, {3, 1, 1} или {3, 2} — разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует ${\displaystyle p(5)=7}$ разбиений числа 5: {1, 1, 1, 1, 1}, {2, 1, 1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}.

Некоторые значения числа разбиений ${\displaystyle p(n)}$ приведены в следующей таблице^[1]:

---