Математика
Введение в целочисленные разделы
Лестница в небо
Типичная лестница состоит из тринадцати-шестнадцатиступеней. Для целей этого введения давайте рассмотрим скромную лестницу, состоящую всего из 5 ступенек. Мы хотим определить, сколько существует различных способов подняться по лестнице. Давай выясним:
- Обычный или распространенный способ - подниматься по одной (1) ступеньке за раз, пока мы не доберемся до вершины, давайте представим эту стратегию как 1 + 1 + 1 + 1 + 1.
- Другой способ — сначала подняться по двум ступенькам за раз, а затем подняться по оставшимся трем ступенькам одну за другой. Давайте сохраним это как 2 + 1 + 1 + 1.
- Еще один способ — перепрыгнуть две ступеньки за раз, затем еще две за раз, затем последнюю ступеньку, то есть 2 + 2 + 1.
- Четвертая стратегия состоит в том, чтобы за один раз подняться на три ступеньки, а затем на оставшиеся две ступеньки одну за другой, то есть 3 + 1 + 1.
- Еще одна стратегия: подняться по трем ступеням за раз, затем за один раз подняться и по оставшимся двум ступеням, то есть 3 + 2.
- Шестая стратегия: подняться на четыре ступеньки за раз, затем подняться на одну ступеньку. То есть 4+1.
- Если вы чувствуете себя олимпийским чемпионом, вы можете совершить всего один гигантский прыжок, преодолев все 5 ступенек одновременно! Браво. Стратегия семь = 5.
Итак, это все возможные способы подъема по рассматриваемой лестнице? Не совсем так, еще один вариант, не указанный выше: сначала подняться по одной лестнице, а затем подняться по оставшимся четырем лестницам за один раз (1 + 4). Но это всего лишь вариант 6 наоборот. Они содержат одинаковый набор чисел, 1 и 4.
Если порядок расположения чисел не имеет значения, то по 5-ступенчатой лестнице можно подняться всего 7 способами. Мы говорим, что количество разделов из 5 равно 7. Каждая стратегия подъема представляет собой раздел количества ступеней.
Формальное определение, основные понятия
Раздел положительного целого числа n – это последовательность положительных целых чисел, сумма которых составляет n. Из введения, разделы 5 равны 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1, 3 + 1 + 1, 3 + 2, 4 + 1 и 5. Всего семь.
Каждое слагаемое в разделе называется частью (как и следовало ожидать), а порядок расположения частей не имеет значения, 2 + 2 + 1 — это тот же раздел, что и 1 + 2 + 2, и 2 + 1 + 2. Когда порядок имеет значение, последовательность называется композицией.
p(n) используется для обозначения статистической суммы, которая дает количество неограниченных разделений числа n, например p(5) = 7. Когда мы накладываем какие-то ограничения на части, мы получаем ограниченные разделы. Обычные ограничения включают ограничение количества частей только нечетным числом, ограничение отдельных частей, ограничение количества частей, ограничение размеров частей и т. д.
Пример. Пусть p(n, k) обозначает количество разбиений числа n ровно на k частей, тогда p(5, 2) = 2 (считая только 4 + 1 и 3 + 2).
Очевидно, что для всех n p(n, n) = p(n, 1) = 1, не так ли?
Значения p(n) для n = от 0 до 9 показаны в таблице ниже.
Обратите внимание, что p(0) имеет значение 1, мы вернемся к этому позже.
Упражнение. Определите значения p(10), p(10, 5), p(10, 6).
Нахождение формулы для p(n)
Поиск значения p(n) путем перечисления всех разделов n и их подсчета может оказаться непростой задачей даже при умеренных значениях n. Было бы неплохо иметь алгебраическую формулу.
К сожалению, не существует известной естественной формулы для p(n). Под естественным мы подразумеваем формулу, которая является прямой, комбинаторной (дискретной) и точной одновременно. Тем не менее, существуют некоторые косвенные методы и сложные формулы для вычисления p(n). Мы рассмотрим некоторые из них.
Производящая функция Эйлера
Мы начнем с простого, но очень умного открытия Леонада Эйлера, легендарного швейцарского математика, который сделал большую часть новаторской работы в этой области.
Эйлер заметил, что когда мы умножаем набор бесконечных полиномов вида: (1 + x + x² + x³ + x⁴ + …)(1 + x² + x⁴ + x⁶ + …)(1 + x³ + x⁶ + x⁹ + …)…, коэффициент при xⁿ в результирующем произведении дает номер раздела n, то есть p(n). Мы дадим ручное объяснение, почему это так:
Пусть G(x) = (1 + x + x² + x³ + x⁴ + …) (1 + x² + x⁴ + x⁶ + …)(1 + x³ + x⁶ + x⁹ + …)…(1 + xⁿ + x² ⁿ + x³ⁿ + …)…
При расширении G(x) принимает следующий вид:
1 + c₁x + c₂x² + c₃x³ + c₄x⁴ + …+ cₙxⁿ + …
Общий термин cₙxⁿ в расширении возникает в результате умножения членов, сумма показателей которых равна n, а затем сложения произведений. Например, чтобы получить c₃x³, возможны следующие конфигурации:
Конфигурация 1: умножьте x (то есть x¹) из первой скобки на x² из второй скобки. Сумма показателей равна 1 + 2 = 3.
Конфигурация 2: возьмите x³ из первой скобки (и умножьте на 1 из всех остальных скобок).
Конфигурация 3: возьмите x³ из третьей скобки (и умножьте на 1 из всех остальных скобок).
Затем сложите x³, чтобы получить 3x³. Итак, c₃=3, что является значением p(3).
Как правило, коэффициент cₙ приxⁿ в разложении G(x) дает значение p(n), поскольку каждая конфигурация (как определено выше) фактически представляет собой уникальный раздел n(поскольку показатели в сумме составляют n и по-разному). И когда мы сложим xⁿ's, получим cₙxⁿ , очевидно, что cₙ — это количество разделов n. КЭД.
G(x) называется генерирующей функцией для p(n). Каждый из составляющих его многочленов представляет собой бесконечную геометрическую прогрессию общей формы
1 + xᵏ + x²ᵏ + x³ᵏ + x⁴ᵏ+… (первый член = 1, обыкновенное отношение = xᵏ).
Используя формулу суммы бесконечной геометрической прогрессии и сокращенные обозначения суммы и произведения, мы можем написать:
Там у вас есть функция распределения, неявно определенная производящей функцией. Если бы был способ выжать это и сделать предметом формулы.
Теперь давайте применим этот метод, чтобы найти p(4). Мы хотим найти коэффициент при x⁴ в разложении G(x). К счастью, нам не нужно перемножать весь бесконечный набор многочленов; поскольку члены с показателями выше 4 не влияют на коэффициент x⁴, мы можем обрезать их в каждой скобке.
Нам просто нужно умножить следующее:
(1 + x + x² + x³ + x⁴ )(1 + x² + x⁴ )(1 + x³)(1 + x⁴)
Вручную надо поработать, а с помощью онлайн-программы умножения полиномов получаем:
1 + x + 2x² + 3x³ + 5x⁴ + 5x⁵ + 6x⁶ + 7x⁷ + 7x⁸ + 6x⁹ + 5x¹⁰ + 5x¹¹ + 3x¹² + 2x¹³ + x¹⁴ + x¹⁵
Отсюда мы получаем, что p(4) = 5. Обратите внимание, что результат также дает значения p(3), p(2), p(1) и p(0). Посмотрите теперь, почему p(0) = 1?
Коэффициенты x с показателями выше n=4 не обязательно представляют p(n) из-за сделанного нами усечения, но обычно расширение дает правильные значения p(n) также для всех целых чисел меньше n. Поговорите о том, чтобы попросить дерево и получить лес (или хотя бы его часть).
Итак, мы преобразовали задачу подсчета разбиений в задачу умножения многочленов, которая поддается алгоритмизации. Благодаря идее производящей функции.
Рекуррентная формула
Теорема Эйлера о пятиугольных числах. Эйлер обнаружил следующее тождество:
Показатели x в правой части (1, 2, 5, 7, 12, …) — это числа вида k(3k − 1)/2 (где k = 0, 1, −1, 2, −2 , 3, −3, 4…), называемые обобщенными пятиугольными числами, поэтому это тождество известно как теорема о пятиугольных числах. Используя обозначения пи и сигма, тождество можно кратко сформулировать как:
Мы можем объединить эту теорему с производящей функцией для p(n), изложенной ранее, чтобы получить рекурсивную формулу для p(n) следующим образом:
Числа в скобках снова представляют собой пятиугольные числа в форме k(3k − 1)/2 со знаком перед каждым term — это знак -1, возведенный в степень |k| + 1, где |k| абсолютное значение k. При этом вы можете продолжать формулу повторения столько, сколько необходимо.
Обратите внимание, как снова проявляется ситуация с деревом и лесом, на этот раз наоборот: чтобы получить дерево, отдайте лес (или хотя бы его часть).
Например, чтобы вычислить p(9), нам нужно знать p(8), p(7) и т. д. Если эти значения еще не вычислены заранее, мы можем просто начать с p(0) = 1 и работать вверх.
p(9) = p(8) + p(7) - p(4) - p(2) + p(-3) + p(-6) - …
p(n) = 0 для отрицательных значений n.
Итак, у нас осталось p(9) = p(8) + p(7) - p(4) - p(2).
Прямые формулы
В 1918 году Г. Х. Харди и С. Рамануджан вывели следующую приблизительную формулу для p(n):
Это асимптотическая формула, приближение становится все ближе и ближе к реальному значению p(n) по мере того, как n становится все больше и больше, сама формула является приближением (первым членом) следующего асимптотического ряда:
Где Aₖ(n) — некоторая сложная функция от n.
Другой математик, Ганс Радемахер, в 1937 году улучшил формулу и получил:
На самом деле эта формула так же хороша, как и точная: при округлении до ближайшего целого числа она дает точное значение p(n).
Рамануджан, Харди, Радемахер. Как они придумали такие огромные формулы? По сути, пытаясь выжать p(n) из производящей функции. Это немалый подвиг, он включает в себя некоторые глубокие и оригинальные аналитические методы.
Визуализация разделов
Разделы могут быть визуально представлены диаграммами Юнга, которые состоят из рядов ячеек, причем количество ячеек в ряду соответствует размеру части.
Например, раздел 7 + 4 + 2 + 1 имеет следующую диаграмму Юнга:
Диаграмма читается по строкам, если мы повернем ее по диагонали или просто прочитаем по столбцам, мы получим сопряжение разбиения, поэтому сопряжение раздел выше (7 + 4 + 2 + 1) будет 4 + 3 + 2 + 2 + 1 + 1 + 1. Обратите внимание, что количество частей в сопряженном разделе равно размеру наибольшей части в исходном разделе, это наблюдение в целом верно.
Когда раздел совпадает со своим сопряженным, этот раздел называется самосопряженным. Упражнение. Убедитесь, что 5 + 4 + 2 + 2 + 1 является самосопряженным.
Диаграммы Юнга полезны для легкого (визуального) вывода или доказательства теорем о разбиениях. Следующая теорема, например, основана на наблюдении, что количество частей в сопряженном разделе равно размеру наибольшей части в исходном разделе.
Теорема: количество разделов n на k частей равно количеству разделов n с k в качестве наибольшей части.
Сравнения Рамануджана
Наблюдая за большой таблицей значений p(n), Рамануджан сделал несколько замечательных наблюдений о свойствах делимости статистической суммы:
(я). p(n)оставляетостаток 0 при делении на 5 всякий раз, когда n является числом, например 4, 9, 14, 19 и т. д. Другими словами, p(n) кратно 5, когда n имеет форму 5k + 4. Например, p(9) = 30, кратное 5.
(ii). p(n) кратно 7, если n — число в форме 7k + 5. Пример: p( 26) = 2436, кратное 7.
(iii). p(n) – кратное 11, если n – число в формате 11k + 6. Пример: p( 17) = 297, кратное 11.
Эти наблюдения можно записать на языке сравнений (модулярной арифметики) следующим образом:
(я). p(5k + 4) ≡ 0 (mod 5)
(ii). p(7k + 5) ≡ 0 (mod 7)
(iii). p(11k + 6) ≡ 0 (mod 11)
Обратите внимание, что делители являются простыми числами. Следуя шаблону, заманчиво думать, что следующее сравнение должно быть чем-то вроде
p(13k + c) ≡ 0 (mod 13), но такого совпадения нет.
Исследования конгруэнтности разделов продолжаются до сих пор.
Занятия и задачи
- Предполагая, что порядок имеет значение, то есть 2 + 3 — это не то же самое, что 3 + 2, определите общее количество способов подняться по 5-ступенчатой лестнице во введении.
- Найдите сопряжение следующего разбиения 20; 8 + 7 + 3 + 2.
- Каковы самосопряженные разбиения числа 5? Сколько их?
- (i) Напишите программу на вашем любимом языке, чтобы найти p(n), используя метод полиномиального разложения.
(ii) Напишите программу на вашем любимом языке, чтобы найти p (n) с помощью рекуррентной формулы.
(iii) Сравните время выполнения двух программ для следующих значений n: 10, 20, 30, 50, 100. , 200, 300, 400, 500, 600, 700, 800, 900, 1000. - Напишите программу на своем любимом языке, чтобы найти сопряжение раздела.
