Разделение (теория чисел)

Диаграммы Юнга, связанные с разбиениями натуральных чисел от 1 до 8. Они расположены так, что изображения под отражением относительно главной диагонали квадрата являются сопряженными разбиениями.

Разделы n с наибольшим слагаемым k

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

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Зависимая от порядка композиция 1 + 3 является тем же разбиением, что и 3 + 1, в то время как две различные композиции 1 + 2 + 1 и 1 + 1 + 2 представляют собой одно и то же разбиение 2 + 1 + 1.

Слагаемое в разбиении также называется частью . Количество разбиений n определяется статистической суммой p ( n ). Таким образом, p (4) = 5. Обозначение λ ⊢ n означает, что λ является разбиением числа n .

Разделы могут быть графически визуализированы с помощью диаграмм Юнга или Феррерса . Они встречаются в ряде разделов математики и физики , включая изучение симметрических многочленов и симметрической группы, а также в теории представлений групп в целом.

Примеры [ править ]

Семь разделов из пяти:

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

В некоторых источниках разбиения трактуются как последовательность слагаемых, а не как выражение со знаком плюс. Например, раздел 2 + 2 + 1 вместо этого может быть записан как кортеж (2, 2, 1) или в еще более компактной форме (2 ² , 1), где верхний индекс указывает количество повторений термина.

Представления перегородок [ править ]

Существует два распространенных схематических метода представления разбиений: в виде диаграмм Феррерса, названных в честь Нормана Маклеода Феррерса , и в виде диаграмм Юнга, названных в честь британского математика Альфреда Янга . У обоих есть несколько возможных соглашений; здесь мы используем английскую нотацию , а диаграммы выровнены в верхнем левом углу.

Диаграмма Феррерса [ править ]

Разделение 6 + 4 + 3 + 1 положительного числа 14 можно представить в виде следующей диаграммы:

14 кругов выстроены в 4 ряда, каждый размером с часть перегородки. Схемы для 5 разделов числа 4 приведены ниже:

Диаграмма Юнга [ править ]

Альтернативным визуальным представлением целочисленного разбиения является его диаграмма Юнга (часто также называемая диаграммой Феррерса). Вместо того, чтобы представлять разбиение точками, как на диаграмме Феррерса, диаграмма Юнга использует прямоугольники или квадраты. Таким образом, диаграмма Юнга для разбиения 5 + 4 + 1 имеет вид

а диаграмма Феррерса для того же разбиения имеет вид

Хотя этот, казалось бы, тривиальный вариант не заслуживает отдельного упоминания, диаграммы Юнга оказались чрезвычайно полезными при изучении симметрических функций и теории представлений групп : заполнение ящиков диаграмм Юнга числами (или иногда более сложными объектами), подчиняющимися различным rules приводит к семейству объектов, называемых таблицами Юнга , и эти таблицы имеют комбинаторное и теоретико-представительное значение. ^[1] Как тип фигуры, образованной смежными квадратами, соединенными вместе, диаграммы Юнга представляют собой особый вид полимино . ^[2]

Функция разделения [ править ]

Функция разделения представляет количество возможных разделов неотрицательного целого числа . Например, поскольку целое число имеет пять разделов , , , , и . Значения этой функции для :${\ Displaystyle р (п)}$${\ displaystyle n}$${\ Displaystyle p (4) = 5}$${\ displaystyle 4}$${\ displaystyle 1 + 1 + 1 + 1}$${\ displaystyle 1 + 1 + 2}$${\ displaystyle 1 + 3}$${\ displaystyle 2 + 2}$${\ displaystyle 4}$${\ Displaystyle п = 0,1,2, \ точки}$

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (последовательность A000041 в OEIS ).

Нет замкнутая форма выражения для функции разбиения не известно, но она имеет как асимптотические разложения , которые точно аппроксимировать его и рекуррентные соотношения , с помощью которого он может быть рассчитаны точно. Он растет как экспоненциальная функция от квадратного корня из аргумента. ^[3] мультипликативный обратное его порождающей функции является функция Эйлера ; по теореме Эйлера о пятиугольных числах эта функция представляет собой переменную сумму пятиугольных числовых степеней своего аргумента.

${\ Displaystyle п (п) = п (п-1) + п (п-2) -р (п-5) -р (п-7) + \ cdots}$

Шриниваса Рамануджан первым обнаружил, что статистическая сумма имеет нетривиальные закономерности в модульной арифметике , теперь известные как сравнения Рамануджана . Например, всякий раз, когда десятичное представление чисел заканчивается цифрой 4 или 9, количество разделов будет делиться на 5. ^[4]${\ displaystyle n}$${\ displaystyle n}$

Ограниченные разделы [ править ]

И в комбинаторике, и в теории чисел часто изучаются семейства разбиений с различными ограничениями. ^{[5] В} этом разделе рассматривается несколько таких ограничений.

Сопряженные и самосопряженные разделы [ править ]

Если перевернуть диаграмму разбиения 6 + 4 + 3 + 1 по его главной диагонали, мы получим еще одно разбиение 14:

Превращая строки в столбцы, мы получаем разбиение 4 + 3 + 3 + 2 + 1 + 1 числа 14. Такие разбиения называются сопряженными друг другу. ^[6] В случае числа 4 разбиения 4 и 1 + 1 + 1 + 1 являются сопряженными парами, а разбиения 3 + 1 и 2 + 1 + 1 сопряжены друг другу. Особый интерес представляет разбиение 2 + 2, которое само является сопряженным. Такое разбиение называется самосопряженным . ^[7]

Требование : Количество самосопряженных перегородок является таким же , как число разделов с различными нечетными частями.

Доказательство (схема) : ключевое наблюдение состоит в том, что каждую нечетную часть можно « сложить » посередине, чтобы сформировать самосопряженную диаграмму:

Затем можно получить биекцию между набором разделов с различными нечетными частями и набором самосопряженных разделов, как показано в следующем примере:

Нечетные части и отдельные части [ редактировать ]

Среди 22 разбиений числа 8 есть 6, которые содержат только нечетные части :

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

В качестве альтернативы мы могли бы подсчитать разделы, в которых ни одно число не встречается более одного раза. Такой раздел называется разделом с отдельными частями . Если мы посчитаем разбиения 8 с отдельными частями, мы также получим 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

Это общее свойство. Для каждого положительного числа количество разделов с нечетными частями равно количеству разделов с отдельными частями, обозначенным q ( n ). ^{[8] [9]} Этот результат был доказан Леонардом Эйлером в 1748 году ^[10] и позже был обобщен в виде теоремы Глейшера .

Для каждого типа ограниченного раздела существует соответствующая функция для количества разделов, удовлетворяющих данному ограничению. Важный пример - q ( n ). Первые несколько значений q ( n ) (начиная с q (0) = 1):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (последовательность A000009 в OEIS ).

Производящая функция для д ( п ) (перегородками на отдельные части) дается ^[11]

${\ displaystyle \ sum _ {n = 0} ^ {\ infty} q (n) x ^ {n} = \ prod _ {k = 1} ^ {\ infty} (1 + x ^ {k}) = \ prod _ {k = 1} ^ {\ infty} {\ frac {1} {1-x ^ {2k-1}}}.}.$

Теорема о пятиугольном числе дает рекуррент для q : ^[12]

q ( k ) = a _k + q ( k - 1) + q ( k - 2) - q ( k - 5) - q ( k - 7) + q ( k - 12) + q ( k - 15) - q ( k - 22) - ...

где a _k равно (−1) ^m, если k = 3 m ² - m для некоторого целого числа m, и равно 0 в противном случае.

Ограниченный размер детали или количество деталей [ править ]

Используя сопряжения, количество p _k ( n ) разбиений n ровно на k частей равно количеству разбиений n, в которых наибольшая часть имеет размер k . Функция p _k ( n ) удовлетворяет рекуррентности

p _k ( n ) = p _k ( n - k ) + p _{k −1} ( n - 1)

с начальными значениями p ₀ (0) = 1 и p _k ( n ) = 0, если n ≤ 0 или k ≤ 0 и n и k не равны нулю. ^[13]

Восстанавливают функцию p ( n ) следующим образом:

${\displaystyle p(n)=\sum _{k=0}^{n}p_{k}(n).}$

Одна из возможных производящих функций для таких разбиений при фиксированном k и переменном n :

${\displaystyle \sum _{n\geq 0}p_{k}(n)x^{n}=x^{k}\cdot \prod _{i=1}^{k}{\frac {1}{1-x^{i}}}.}$

В более общем смысле, если T - это набор положительных целых чисел, то количество разбиений n , все части которых принадлежат T , имеет производящую функцию

${\displaystyle \prod _{t\in T}(1-x^{t})^{-1}.}$

Это можно использовать для решения проблем с внесением сдачи (где набор T указывает доступные монеты). В качестве двух частных случаев можно сказать, что количество разбиений n, в которых все части равны 1 или 2 (или, что то же самое, количество разбиений n на 1 или 2 части) равно

${\displaystyle \left\lfloor {\frac {n}{2}}+1\right\rfloor ,}$

и число перегородок п , в которых все части являются 1, 2 или 3 (или, что то же самое, число разбиений п на не более трех частей) является ближайшим целым числом к ( п + 3) ² /12 ^{[14 ]}

Асимптотика [ править ]

Асимптотическая скорость роста для р ( п ) задаются

${\displaystyle \log p(n)\sim C{\sqrt {n}}{\text{ as }}n\rightarrow \infty }$

где . ^[15] Более точная асимптотическая формула${\displaystyle C=\pi {\sqrt {\frac {2}{3}}}.}$

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$ в качестве ${\displaystyle n\rightarrow \infty }$

был впервые получен Г. Х. Харди и Рамануджаном в 1918 г. и независимо И. В. Успенским в 1920 г. Полное асимптотическое разложение было дано в 1937 г. Гансом Радемахером .

Если является множество натуральных чисел, пусть р ( п ) обозначает число разбиений п на элементы А . Если A имеет положительную естественную плотность α, то

${\displaystyle \log p_{A}(n)\sim C{\sqrt {\alpha n}}}$

и наоборот, если это асимптотическое свойство выполняется для p _A ( n ), то A имеет естественную плотность α. ^[16] Этот результат был сформулирован с наброском доказательства Эрдёшем в 1942 году. ^{[17] [18]}

Если A - конечное множество, этот анализ неприменим (плотность конечного множества равна нулю). Если A имеет k элементов, наибольший общий делитель которых равен 1, то ^[19]

${\displaystyle p_{A}(n)=\left(\prod _{a\in A}a^{-1}\right)\cdot {\frac {n^{k-1}}{(k-1)!}}+O(n^{k-2}).}$

Разделы в прямоугольнике и биномиальные коэффициенты по Гауссу [ править ]

Также можно одновременно ограничить количество и размер деталей. Пусть р ( N , M ; п ) обозначает число разбиений п с не более чем М частей, каждая из размера не более N . Эквивалентно, это разбиения, диаграмма Юнга которых помещается внутри прямоугольника M × N. Есть рекуррентное отношение

${\displaystyle p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)}$

полученный путем наблюдения, которое подсчитывает разбиения n на ровно M частей размером не более N , и вычитание 1 из каждой части такого разбиения дает разбиение n - M на не более M частей. ^[20]${\displaystyle p(N,M;n)-p(N,M-1;n)}$

Гауссовский биномиальный коэффициент определяется следующим образом:

${\displaystyle {k+\ell \choose \ell }_{q}={k+\ell \choose k}_{q}={\frac {\prod _{j=1}^{k+\ell }(1-q^{j})}{\prod _{j=1}^{k}(1-q^{j})\prod _{j=1}^{\ell }(1-q^{j})}}.}$

Гауссовский биномиальный коэффициент связан с порождающей функцией от р ( Н , М , п ) равенство

${\displaystyle \sum _{n=0}^{MN}p(N,M;n)q^{n}={M+N \choose M}_{q}.}$

Ранг и площадь Дарфи [ править ]

Оценка перегородки является наибольшим числом к таким образом, что перегородка содержит , по меньшей мере , K части размера по крайней мере , к . Например, разбиение 4 + 3 + 3 + 2 + 1 + 1 имеет ранг 3, потому что оно содержит 3 части ≥ 3, но не содержит 4 частей ≥ 4. В диаграмме Феррерса или диаграмме Юнга разбиения ранга r , квадрат r × r элементов в верхнем левом углу известен как квадрат Дёрфи :

Квадрат Дёрфи находит применение в комбинаторике при доказательстве различных тождеств разбиения. ^[21] Это также имеет некоторое практическое значение в виде индекса Хирша .

Другой статистический показатель также иногда называют рангом разбиения (или рангом Дайсона), а именно разницей для разбиения k частей с наибольшей частью . Эта статистика (которая не связана со статистикой, описанной выше) появляется в исследовании сравнений Рамануджана .${\displaystyle \lambda _{k}-k}$${\displaystyle \lambda _{k}}$

Решетка Юнга [ править ]

Существует естественный частичный порядок на разбиениях, задаваемый включением диаграмм Юнга. Этот частично упорядоченный набор известен как решетка Юнга . Решетки были первоначально определены в контексте теории представлений , где он используется для описания неприводимых представлений о симметрических группах S _п для все п , вместе с их свойствами ветвления, в нулевой характеристике. Он также получил значительные исследования из-за своих чисто комбинаторных свойств; в частности, это мотивирующий пример дифференциального положения .

См. Также [ править ]

Викискладе есть медиафайлы, связанные с целочисленными разделами .

Заметки [ править ]

Ссылки [ править ]

• Абрамовиц, Милтон ; Стегун, Ирен (1964). Справочник по математическим функциям с формулами, графиками и математическими таблицами . Министерство торговли США, Национальное бюро стандартов. ISBN 0-486-61272-4.
• Эндрюс, Джордж Э. (1976). Теория перегородок . Издательство Кембриджского университета. ISBN 0-521-63766-X.
• Эндрюс, Джордж Э .; Эрикссон, Киммо (2004). Целочисленные разделы . Издательство Кембриджского университета. ISBN 0-521-60090-1.
• Апостол, Том М. (1990) [1976]. Модулярные функции и ряды Дирихле в теории чисел . Тексты для выпускников по математике . 41 (2-е изд.). Нью-Йорк и др .: Springer-Verlag . ISBN 0-387-97127-0. Zbl  0697.10023 . (См. Современное педагогическое введение к формуле Радемахера в главе 5) .
• Бона, Миклош (2002). Прогулка по комбинаторике: введение в теорию перечисления и графов . Мировое научное издательство. ISBN 981-02-4900-4. (элементарное введение в тему целочисленных разбиений, включая обсуждение графов Феррерса)
• Харди, GH ; Райт, EM (2008) [1938]. Введение в теорию чисел . Отредактировано Д. Р. Хитом-Брауном и Дж . Х. Сильверманом . Предисловие Эндрю Уайлса . (6-е изд.). Оксфорд: Издательство Оксфордского университета . ISBN 978-0-19-921986-5. Руководство по ремонту  2445243 . Zbl  1159.11001 .
• Лемер, Д.Х. (1939). «Об остатке и сходимости ряда для статистической суммы» . Пер. Амер. Математика. Soc . 46 : 362–373. DOI : 10.1090 / S0002-9947-1939-0000410-9 . Руководство по ремонту  0000410 . Zbl  0022.20401 .Предоставляет основную формулу (без производных), остаток и старую форму для A _k ( n ).)
• Гупта, Хансрадж; Gwyther, CE; Миллер, JCP (1962). Королевское математическое общество. Таблицы . Том 4, Таблицы перегородок. (Имеет текст, почти полную библиографию, но они (и Абрамовиц) пропустили формулу Сельберга для A _k ( n ), которая есть у Уайтмана.)
• Макдональд, Ян Г. (1979). Симметричные функции и многочлены Холла . Оксфордские математические монографии. Издательство Оксфордского университета . ISBN 0-19-853530-9. Zbl  0487.20007 . (См. Раздел I.1)
• Натансон, МБ (2000). Элементарные методы теории чисел . Тексты для выпускников по математике. 195 . Springer-Verlag . ISBN 0-387-98912-9. Zbl  0953.11002 .
• Радемахер, Ганс (1974). Собрание статей Ганса Радемахера . v II . MIT Press. С. 100–07, 108–22, 460–75.
• Сотуа, Маркус Ду. (2003). Музыка премий . Нью-Йорк: Многолетник-ХарперКоллинз.
• Стэнли, Ричард П. (1999). Перечислительная комбинаторика . Тома 1 и 2. Издательство Кембриджского университета. ISBN 0-521-56069-1.
• Whiteman, AL (1956). Сумма, связанная с рядом статистической суммы . Тихоокеанский математический журнал . 6 . С. 159–176. Zbl  0071.04004 . (Предоставляет формулу Сельберга. Более старая форма - это конечное разложение Фурье Сельберга.)

Внешние ссылки [ править ]

• "Разделение" , Энциклопедия математики , EMS Press , 2001 [1994]
• Калькулятор разбиения и состава
• Вайсштейн, Эрик В. «Перегородка» . MathWorld .
• Уилф, Герберт С. Лекции по целочисленным разделам (PDF) , заархивировано (PDF) из оригинала на 2021-02-24 , извлечено 2021-02-28
• Подсчет с помощью разделов со ссылочными таблицами на Он-лайн энциклопедию целочисленных последовательностей
• Запись целочисленных разделов в базе данных FindStat
• Модуль Integer :: Partition Perl из CPAN
• Быстрые алгоритмы генерации целочисленных разделов
• Создание всех разделов: сравнение двух кодировок
• Грайм, Джеймс (28 апреля 2016 г.). «Перегородки - Numberphile» (видео) . Брэди Харан . Дата обращения 5 мая 2016 .