Сплошная перегородка - Solid partition

В математике массивные перегородки являются естественным обобщением перегородки и плоские перегородки определяется Перси Александр МакМахон.^[1] Сплошная перегородка ${\displaystyle n}$ представляет собой трехмерный массив, ${\displaystyle n_{i,j,k}}$, неотрицательных целых чисел (индексы ${\displaystyle i,\ j,\ k\geq 1}$) такие, что

${\displaystyle \sum _{i,j,k}n_{i,j,k}=n}$

и

${\displaystyle n_{i+1,j,k}\leq n_{i,j,k}\quad ,\quad n_{i,j+1,k}\leq n_{i,j,k}\quad {\text{and}}\quad n_{i,j,k+1}\leq n_{i,j,k}\quad ,\quad \forall \ i,\ j{\text{ and }}k\ .}$

Позволять ${\displaystyle p_{3}(n)}$ обозначим количество твердых перегородок ${\displaystyle n}$. Поскольку определение твердых перегородок включает трехмерные массивы чисел, их также называют трехмерные перегородки в обозначениях, где плоские перегородки - это двухмерные перегородки, а перегородки - одномерные перегородки. Твердые перегородки и их многомерные обобщения обсуждаются в книге Эндрюс.^[2]

Схемы Феррерса для монолитных перегородок

Другое представление массивных перегородок - в виде Феррерс диаграммы. Диаграмма Феррерса твердого разбиения ${\displaystyle n}$ это собрание ${\displaystyle n}$ точки или узлы, ${\displaystyle \lambda =(\mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n})}$, с ${\displaystyle \mathbf {y} _{i}\in \mathbb {Z} _{\geq 0}^{4}}$ удовлетворяющие условию:^[3]

Состояние FD: Если узел ${\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3},a_{4})\in \lambda }$, то и все узлы ${\displaystyle \mathbf {y} =(y_{1},y_{2},y_{3},y_{4})}$ с ${\displaystyle 0\leq y_{i}\leq a_{i}}$ для всех ${\displaystyle i=1,2,3,4}$.

Например, диаграмма Феррерса

${\displaystyle \left({\begin{smallmatrix}0\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}0\\0\\1\\0\end{smallmatrix}}{\begin{smallmatrix}0\\1\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\1\\0\\0\end{smallmatrix}}\right)\ ,}$

где каждый столбец является узлом, представляет собой сплошной раздел ${\displaystyle 5}$. Существует естественное действие группы перестановок ${\displaystyle S_{4}}$ на диаграмме Феррерса - это соответствует перестановке четырех координат всех узлов. Это обобщает операцию, обозначаемую сопряжением, на обычных разбиениях.

Эквивалентность двух представлений

По диаграмме Феррерса твердое разбиение (как в основном определении) строится следующим образом.

Позволять ${\displaystyle n_{i,j,k}}$ - количество узлов на диаграмме Феррерса с координатами вида ${\displaystyle (i-1,j-1,k-1,*)}$ куда ${\displaystyle *}$ обозначает произвольное значение. Коллекция ${\displaystyle n_{i,j,k}}$ образуют прочную перегородку. Можно проверить, что условие FD означает выполнение условий для твердого разбиения.

Учитывая набор ${\displaystyle n_{i,j,k}}$ образующих сплошное разбиение, можно получить соответствующую диаграмму Феррерса следующим образом.

Начните с диаграммы Феррерса без узлов. Для каждого ненулевого ${\displaystyle n_{i,j,k}}$, Добавить ${\displaystyle n_{i,j,k}}$ узлы ${\displaystyle (i-1,j-1,k-1,y_{4})}$ за ${\displaystyle 0\leq y_{4}<n_{i,j,k}}$ диаграмме Феррерса. По построению легко видеть, что условие FD выполнено.

Например, диаграмма Феррерса с ${\displaystyle 5}$ приведенные выше узлы соответствуют сплошному разделу с

${\displaystyle n_{1,1,1}=n_{2,1,1}=n_{1,2,1}=n_{1,1,2}=n_{2,2,1}=1}$

со всеми другими ${\displaystyle n_{i,j,k}}$ исчезновение.

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

Позволять ${\displaystyle p_{3}(0)\equiv 1}$. Определите производящую функцию твердых перегородок, ${\displaystyle P_{3}(q)}$, к

${\displaystyle P_{3}(q):=\sum _{n=0}^{\infty }p_{3}(n)\ q^{n}=1+q+4\ q^{2}+10\ q^{3}+26\ q^{4}+59\ q^{5}+140\ q^{6}+\cdots }$

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

Точный подсчет с использованием компьютеров

Ввиду отсутствия явно известной производящей функции подсчет количества твердых разбиений для больших целых чисел проводился численно. Есть два алгоритма, которые используются для перечисления твердых разделов и их многомерных обобщений. Работа Аткина. и другие. использовал алгоритм Брэтли и Маккея.^[4] В 1970 году Кнут предложил другой алгоритм для перечисления топологических последовательностей, который он использовал для вычисления количества твердых разбиений всех целых чисел. ${\displaystyle n\leq 28}$.^[5] Мустонен и Раджеш расширили перечисление для всех целых чисел ${\displaystyle n\leq 50}$.^[6] В 2010 году С. Балакришнан предложил параллельную версию алгоритма Кнута, который был использован для расширения перечисления на все целые числа. ${\displaystyle n\leq 72}$.^[7] Один находит

${\displaystyle p_{3}(72)=3464274974065172792\ ,}$

это 19-значное число, иллюстрирующее сложность проведения таких точных подсчетов.

Асимптотическое поведение

Известно, что из работы Bhatia et al. который^[8]

${\displaystyle \lim _{n\rightarrow \infty }n^{-3/4}\ln p_{3}(n)\rightarrow {\text{a constant}}.}$

Значение этой константы было оценено Мустоненом и Раджешем с использованием моделирования Монте-Карло как ${\displaystyle 1.79\pm 0.01}$.^[6]

Рекомендации

1. Мак-Магон П. А. Комбинаторный анализ. Cambridge Univ. Press, Лондон и Нью-Йорк, Vol. 1, 1915 и т. 2, 1916 г .; см. т. 2. С. 332.
2. Г. Эндрюс, Теория перегородок, Издательство Кембриджского университета, 1998.
3. А. О. Л. Аткин, П. Братли, И. Г. Макдональд, Дж. К. С. Маккей, Некоторые вычисления дляm-мерные перегородки, Учеб. Camb. Фил. Soc., 63 (1967), 1097–1100.
4. П. Брэтли и Дж. К. С. Маккей, "Алгоритм 313: Генератор многомерного разбиения", Comm. ACM, 10 (Выпуск 10, 1967), стр. 666.
5. Д. Э. Кнут, "Заметка о твердых перегородках", Матем. Comp., 24 (1970), 955–961.
6. Вилле Мустонен и Р. Раджеш, "Численная оценка асимптотического поведения твердотельных разбиений целого числа", J. Phys. A: Математика. Gen. 36 (2003), нет. 24, 6651.cond-mat / 0303607
7. Шривацан Балакришнан, Суреш Говиндараджан и Навин С. Прабхакар, «Об асимптотике многомерных разбиений», J.Phys. A: Математика. Gen. 45 (2012) 055001 arXiv: 1105.6231.
8. Д. П. Бхатия, М. А. Прасад и Д. Арора, "Асимптотические результаты для числа многомерных разбиений целых и направленных компактных решетчатых животных", J. Phys. A: Математика. Gen. 30 (1997) 2281

внешняя ссылка

• OEIS последовательность A000293 (твердотельные (т.е. трехмерные) перегородки)
• Проект твердых перегородок ИИТ Мадраса
• Запись Mathworld для твердых разделов