Калькулятор Функции Разбиения

Добро пожаловать в Калькулятор функции разбиения — полнофункциональный инструмент для исследования одного из самых захватывающих объектов комбинаторики. Введите любое неотрицательное целое число \(n\), и этот инструмент вычислит \(p(n)\) — количество способов представить \(n\) в виде суммы положительных целых чисел, где порядок не имеет значения — вместе с количеством разбиений на различные части \(q(n)\), количеством разбиений на нечетные части \(o(n)\), асимптотической оценкой Харди-Рамануджана, всеми подходящими сравнениями Рамануджана и (для небольших \(n\)) отрисует каждое отдельное разбиение в виде анимированной диаграммы Юнга.

Что такое функция разбиения p(n)?

Функция разбиения \(p(n)\) подсчитывает количество способов записать \(n\) как сумму положительных целых чисел без учета порядка. Две суммы, отличающиеся только порядком слагаемых, считаются одним и тем же разбиением. Например, разбиениями числа 4 являются:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Это дает нам \(p(4) = 5\). По соглашению \(p(0) = 1\), что соответствует "пустому разбиению". Еще несколько значений: \(p(1) = 1,\ p(5) = 7,\ p(10) = 42,\ p(50) = 204{,}226,\ p(100) = 190{,}569{,}292.\)

Производящая функция

Леонард Эйлер обнаружил, что производящая функция для \(p(n)\) имеет удивительно компактную форму произведения:

Каждый множитель \(1/(1 - x^k) = 1 + x^k + x^{2k} + \ldots\) вносит выбор того, сколько раз часть \(k\) появляется в разбиении. Перемножение этих факторов генерирует каждое разбиение ровно один раз.

Диаграммы Юнга (Феррерса)

Диаграмма Юнга (также называемая диаграммой Феррерса) представляет разбиение визуально в виде выровненного по левому краю массива квадратов. Каждая строка соответствует одной части, и строки перечисляются от наибольшей к наименьшей. Например, разбиение \(4 + 2 + 1\) числа 7 превращается в:

Диаграммы Юнга позволяют "видеть" тождества разбиений. Отражение диаграммы относительно главной диагонали превращает строки в столбцы, что соответствует сопряженному разбиению. Этот калькулятор отрисовывает диаграмму Юнга для каждого разбиения \(n\), если \(n \le 15\).

Теорема Эйлера о разбиениях

Один из самых элегантных результатов Эйлера гласит:

Например, разбиениями числа 7 на различные части являются \(\{7\}, \{6+1\}, \{5+2\}, \{4+3\}, \{4+2+1\}\) — их пять. Разбиениями числа 7 на нечетные части являются \(\{7\}, \{5+1+1\}, \{3+3+1\}, \{3+1+1+1+1\}, \{1+1+1+1+1+1+1\}\) — их тоже пять. Сводная панель калькулятора показывает как \(q(n)\), так и \(o(n)\), чтобы вы могли проверить это тождество для выбранного \(n\).

Асимптотика Харди-Рамануджана

В 1918 году Г. Х. Харди и Сриниваса Рамануджан доказали первую формулу, которая отражала истинную скорость роста \(p(n)\) для больших \(n\):

Этот результат появился благодаря круговому методу Харди-Рамануджана, который интегрирует производящую функцию вокруг особых точек на единичной окружности. Ганс Радемахер в 1937 году усовершенствовал ее до точного сходящегося ряда — одной из самых знаменитых формул в аналитической теории чисел.

Сравнения Рамануджана для разбиений

Изучая таблицу значений разбиений, Рамануджан заметил три удивительных паттерна делимости:

К примеру, \(p(4)=5,\ p(9)=30,\ p(14)=135,\ p(19)=490,\ p(24)=1575\) все делятся на 5. Калькулятор автоматически подает сигнал, если выбранное вами \(n\) попадает в один из этих классов.

Как пользоваться этим калькулятором

1. Введите неотрицательное целое число до 500 в поле ввода или нажмите на один из известных быстрых примеров (0, 4, 10, 42, 100, 200).
2. Нажмите "Рассчитать разбиения". Инструмент вычислит \(p(n)\), \(q(n)\), \(o(n)\) и оценку Харди-Рамануджана.
3. Ознакомьтесь с главной панелью, показывающей \(p(n)\) крупным шрифтом, затем просмотрите таблицу для разбиений на различные и нечетные части, асимптотическую оценку и процентную погрешность.
4. Изучите диаграммы Юнга — если \(n \le 15\), каждое разбиение отображается в виде анимированной диаграммы Юнга в адаптивной сетке.
5. Изучите график роста — он отображает \(p(k)\), \(q(k)\) и кривую Харди-Рамануджана для \(k = 0, 1, \ldots, n\). Переключайтесь между линейной и логарифмической шкалой, чтобы увидеть асимптотическую форму.
6. Просмотрите таблицу роста — построчный вид \(p(k), q(k), o(k)\) для малых \(k\). Используйте ее, чтобы найти первое вхождение каждого сравнения Рамануджана.

Пример работы: Разбиения числа 5

Давайте разберем \(n = 5\). Все разбиения:

• \(5\)
• \(4 + 1\)
• \(3 + 2\)
• \(3 + 1 + 1\)
• \(2 + 2 + 1\)
• \(2 + 1 + 1 + 1\)
• \(1 + 1 + 1 + 1 + 1\)

Таким образом, \(p(5) = 7\). Разбиения на различные части: \(\{5\}, \{4+1\}, \{3+2\}\) — их три, так что \(q(5) = 3\). Разбиения на нечетные части: \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\) — тоже три, так что \(o(5) = 3\). Теорема Эйлера подтверждается. Наконец, \(n = 5 \equiv 0 \pmod 5\) не имеет вид \(5k+4\), поэтому сравнение для 5 не применяется; однако \(p(4) = 5\) удовлетворяет условию \(p(5k+4) \equiv 0 \pmod 5\).

Классические значения p(n)

История

• 1750-е: Леонард Эйлер изучает разбиения и открывает тождество производящей функции и теорему "различные = нечетные".
• 1915: Майор Перси Мак-Магон публикует таблицу \(p(n)\) для \(n\) до 200 — вычисленную вручную.
• 1918: Харди и Рамануджан доказывают асимптотическую формулу с помощью кругового метода.
• 1919: Рамануджан публикует знаменитые сравнения \(p(5k+4),\ p(7k+5),\ p(11k+6)\).
• 1937: Ганс Радемахер превращает формулу Харди-Рамануджана в точный сходящийся ряд.
• 2011: Кен Оно и Ян Брюнье доказывают, что \(p(n)\) может быть выражена как конечная алгебраическая сумма для любого положительного целого числа.

Применение

• Комбинаторика и теория представлений — разбиения индексируют неприводимые представления симметрической группы \(S_n\).
• Статистическая механика — количество разбиений встречается в расчетах энтропии идеальных квантовых газов и в функциях разбиения теории струн.
• Модулярные формы — производящая функция для \(p(n)\) тесно связана с эта-функцией Дедекинда.
• Информатика — тесты перечисления суммы подмножеств и целочисленного программирования часто используют количество разбиений.

Часто задаваемые вопросы

Что такое функция разбиения p(n)?

\(p(n)\) подсчитывает количество способов выразить \(n\) как сумму положительных целых чисел, где порядок не имеет значения. \(p(4) = 5\), потому что 4 можно записать как \(4\), \(3+1\), \(2+2\), \(2+1+1\) или \(1+1+1+1\). По соглашению \(p(0) = 1\).

Что такое диаграмма Юнга или Феррерса?

Диаграмма Юнга — это визуальное представление разбиения: каждая часть становится строкой из выровненных по левому краю квадратов, при этом части перечисляются от большей к меньшей сверху вниз. Для \(4+2+1\) рисуется строка из 4, строка из 2 и строка из 1 квадрата. Этот калькулятор отрисовывает диаграмму Юнга для каждого разбиения при \(n \le 15\).

О чем говорит теорема Эйлера о разбиениях?

Для каждого положительного целого числа \(n\) количество разбиений \(n\) на различные части равно количеству разбиений \(n\) на нечетные части. Для \(n = 5\): различные части дают \(\{5\}, \{4+1\}, \{3+2\}\); нечетные части дают \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\). Оба значения равны 3.

Что такое асимптотическая формула Харди-Рамануджана?

Она гласит, что \(p(n) \sim \frac{1}{4n\sqrt{3}} \exp\!\left(\pi \sqrt{2n/3}\right)\) при \(n \to \infty\). Это была первая формула, описывающая точную скорость роста \(p(n)\), открытая в 1918 году Г. Х. Харди и Сринивасой Рамануджаном.

Что такое сравнения Рамануджана для разбиений?

Три примечательных паттерна делимости: \(p(5k+4) \equiv 0 \pmod 5\), \(p(7k+5) \equiv 0 \pmod 7\) и \(p(11k+6) \equiv 0 \pmod{11}\). Например, \(p(4)=5, p(9)=30, p(14)=135\) все делятся на 5.

Как быстро растет p(n)?

p(n) растет субэкспоненциально, но быстрее любого многочлена, примерно как \(\exp(\pi \sqrt{2n/3})\). Для сравнения: \(p(10)=42\), \(p(50)=204{,}226\), \(p(100)=190{,}569{,}292\), а \(p(200) \approx 4 \times 10^{12}\). Используйте переключатель логарифмической шкалы на графике, чтобы визуализировать эту кривую роста.

Дополнительные ресурсы

• Функция разбиения - Wikipedia
• Сравнения Рамануджана - Wikipedia