~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ 91D5DAF921B5254A79C53D4AED66FB9D__1711107540 ✰
Заголовок документа оригинал.:
✰ Integer partition - Wikipedia ✰
Заголовок документа перевод.:
✰ Целочисленный раздел — Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Ferrers_diagram ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/91/9d/91d5daf921b5254a79c53d4aed66fb9d.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/91/9d/91d5daf921b5254a79c53d4aed66fb9d__translat.html ✰
Дата и время сохранения документа:
✰ 12.06.2024 03:26:02 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 22 March 2024, at 14:39 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Arc.Ask3.ru: далее начало оригинального документа

Целочисленный раздел — Википедия Jump to content

Целочисленный раздел

Из Википедии, бесплатной энциклопедии
(Перенаправлено из диаграммы Феррера )
Диаграммы Юнга соответствуют разбиениям натуральных чисел от 1 до 8. Они устроены так, что изображения при отражении относительно главной диагонали квадрата являются сопряженными разбиениями.
Разделы n с наибольшей частью k

В теории чисел и комбинаторике разбиение в неотрицательного целого числа n , также называемое целочисленным разбиением , представляет собой способ записи n виде суммы положительных целых чисел . Две суммы, отличающиеся только порядком слагаемых, считаются одним и тем же разбиением. (Если порядок имеет значение, сумма становится композицией .) Например, число 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 ) . Итак, р (4) = 5 . Обозначение λ n означает, что λ является разбиением n .

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

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

Семь разделов из 5

  • 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 2 , 1) где верхний индекс указывает количество повторений детали.

Это обозначение кратности для раздела можно альтернативно записать как , где m 1 — количество единиц, m 2 — количество двоек и т. д. (Компоненты с m i = 0 можно опустить.) Например, в этих обозначениях разбиения из 5 записываются , и .

Схематические изображения перегородок [ править ]

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

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

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

******
****
***
*

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

**** ***
*
**
**
**
*
*
*
*
*
*
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1

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

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

в то время как диаграмма Феррера для того же раздела имеет вид

*****
****
*

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

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

Использование метода Эйлера для нахождения p (40): линейка со знаками плюс и минус (серый прямоугольник) перемещается вниз, соответствующие части добавляются или вычитаются. Положения знаков задаются разностью чередующихся натуральных (синих) и нечетных (оранжевых) чисел. В файле SVG наведите указатель мыши на изображение, чтобы переместить линейку.

Функция разделения подсчитывает части неотрицательного целого числа . Например, потому что целое число имеет пять разделов , , , , и . Значения этой функции для являются:

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] следующее:

как

В 1937 году Ганс Радемахер нашел способ представить статистическую сумму. сходящимся рядом

где

и есть сумма Дедекинда .

Мультипликативная обратная производящая функция — это функция Эйлера ; по теореме Эйлера о пятиугольных числах эта функция представляет собой знакопеременную сумму степеней пятиугольных чисел своего аргумента.

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

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

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

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

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

******
****
***
*
****
***
***
**
*
*
6 + 4 + 3 + 1 = 4 + 3 + 3 + 2 + 1 + 1

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

Утверждение : количество самосопряженных разделов равно количеству разделов с различными нечетными частями.

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

*****   ↔   ***
*
*

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

ООООООООО
*******
ИксИксИкс

ООООО
О****
О*ИксИкс
О*Икс
О*
9 + 7 + 3 = 5 + 5 + 4 + 3 + 2
Расст. странный самосопряженный

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

Среди 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 ).

Производящая функция для q ( n ) определяется выражением [11]

Теорема о пятиугольных числах дает возврат для 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) м если к = 3 м 2 m для некоторого целого числа m и равно 0 в противном случае.

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

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

п k ( п ) знак равно п k ( п - k ) + п k -1 ( п - 1)

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

Функцию p ( n ) можно восстановить с помощью

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

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

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

а количество разбиений n , в которых все части равны 1, 2 или 3 (или, что то же самое, количество разбиений n не более чем на три части), является ближайшим к ( n + 3) целым числом. 2 / 12. [14]

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

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

получено, наблюдая, что подсчитывает разбиения n ровно на M частей размером не более N , и вычитание 1 из каждой части такого разбиения дает разбиение n - M не более чем на M частей. [15]

Биномиальный коэффициент Гаусса определяется как:

Биномиальный коэффициент Гаусса связан с производящей функцией p ( N , M ; n ) равенством

и Дёрфи Ранг площадь

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

****
***
***
**
*
*

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

(или рангом Дайсона) иногда называют и другую статистику Рангом разбиения , а именно разность для разбиения из k частей с наибольшей частью . Эта статистика (не имеющая отношения к описанной выше) появляется при изучении сравнений Рамануджана .

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

На разбиениях существует естественный частичный порядок , задаваемый включением диаграмм Юнга. Этот частично упорядоченный набор известен как решетка Юнга . Решетка была первоначально определена в контексте теории представлений , где она используется для описания представлений симметрических групп Sn n для всех неприводимых вместе с их свойствами ветвления в нулевой характеристике. Его чисто комбинаторные свойства также подверглись серьезному изучению; в частности, это мотивирующий пример дифференциального ЧУУ .

Случайные разделы [ править ]

Существует глубокая теория случайных разбиений, выбранных в соответствии с равномерным распределением вероятностей на симметричной группе посредством соответствия Робинсона-Шенстеда . В 1977 году Логан и Шепп, а также Вершик и Керов показали, что диаграмма Юнга типичного большого разбиения становится асимптотически близкой к графику некоторой аналитической функции, минимизирующей некоторый функционал. В 1988 году Байк, Дейфт и Йоханссон расширили эти результаты, чтобы определить распределение самой длинной возрастающей подпоследовательности случайной перестановки с точки зрения распределения Трейси – Уидома . [17] Окуньков связал эти результаты с комбинаторикой римановых поверхностей и теорией представлений. [18] [19]

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

Примечания [ править ]

  1. ^ Эндрюс 1976 , с. 199.
  2. ^ Жосуа-Верже, Матье (2010), «Биекции между заполнениями диаграмм Юнга, избегающими шаблонов», Журнал комбинаторной теории , серия A, 117 (8): 1218–1230, arXiv : 0801.4928 , doi : 10.1016/j.jcta. 2010.03.006 , МР   2677686 , S2CID   15392503 .
  3. ^ Эндрюс 1976 , с. 69.
  4. ^ Харди и Райт 2008 , с. 380.
  5. ^ Олдер, Генри Л. (1969). «Тождества разбиений – от Эйлера до современности» . Американский математический ежемесячник . 76 (7): 733–746. дои : 10.2307/2317861 . JSTOR   2317861 .
  6. ^ Харди и Райт 2008 , с. 362.
  7. ^ Харди и Райт 2008 , с. 368.
  8. ^ Харди и Райт 2008 , с. 365.
  9. ^ Обозначения следуют Abramowitz & Stegun 1964 , p. 825
  10. ^ Эндрюс, Джордж Э. (1971). Теория чисел . Филадельфия: Компания WB Saunders. стр. 149–50.
  11. ^ Абрамовиц и Стегун 1964 , с. 825, 24.2.2 экв. Я (Б)
  12. ^ Абрамовиц и Стегун 1964 , с. 826, 24.2.2 экв. II(А)
  13. ^ Ричард Стэнли, Перечислительная комбинаторика , том 1, второе издание. Издательство Кембриджского университета, 2012. Глава 1, раздел 1.7.
  14. ^ Харди, GH (1920). Некоторые известные проблемы теории чисел . Кларендон Пресс.
  15. ^ Эндрюс 1976 , стр. 33–34.
  16. ^ см., например, Stanley 1999 , с. 58
  17. ^ Ромик, Дэн (2015). Удивительная математика длиннейших возрастающих подпоследовательностей . Учебники Института математической статистики. Нью-Йорк: Издательство Кембриджского университета. ISBN  978-1-107-42882-9 .
  18. ^ Окуньков, Андрей (2000). «Случайные матрицы и случайные перестановки» . Уведомления о международных математических исследованиях . 2000 (20): 1043. doi : 10.1155/S1073792800000532 . S2CID   14308256 .
  19. ^ Окуньков, А. (1 апреля 2001 г.). «Бесконечный клин и случайные разбиения» . Селекта Математика . 7 (1): 57–81. arXiv : math/9907127 . дои : 10.1007/PL00001398 . ISSN   1420-9020 . S2CID   119176413 .

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

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

Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: 91D5DAF921B5254A79C53D4AED66FB9D__1711107540
URL1:https://en.wikipedia.org/wiki/Ferrers_diagram
Заголовок, (Title) документа по адресу, URL1:
Integer partition - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)