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

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

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

и

$n_{i+1,j,k}\leq n_{i,j,k},\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}$ для всех $i,j{\text{ and }}k.$

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

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

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

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

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

$\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)\ ,$

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

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

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

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

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

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

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

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

со всеми остальными $n_{i,j,k}$ исчезает.

Генерирующая функция

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

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

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

Точный подсчет с помощью компьютеров

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

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

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

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

Предполагается, что существует константа $c$ такой, что

$$\lim _{n\rightarrow \infty }{\frac {\log p_{3}(n)}{n^{3/4}}}=c.$$

Внешние ссылки

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