Плоская перегородка

В математике и особенно в комбинаторике плоское разбиение — это двумерный массив неотрицательных целых чисел (с положительными целыми индексами i и j ), который не возрастает по обоим индексам. Это означает, что${\displaystyle \пи _{я,j}}$

${\displaystyle \pi _{i,j} \geq \pi _{i,j+1}}$и для всех i и j .${\displaystyle \pi _{i,j} \geq \pi _{i+1,j}}$

Более того, только конечное число из может быть ненулевым. Плоские разбиения являются обобщением разбиений целого числа .${\displaystyle \пи _{я,j}}$

Плоское разбиение может быть представлено визуально путем размещения стопки единичных кубов над точкой ( i , j ) на плоскости, что дает трехмерное тело, как показано на рисунке. Изображение имеет форму матрицы${\displaystyle \пи _{я,j}}$

${\displaystyle {\begin{matrix}4&4&3&2&1\\4&3&1&1\\3&2&1\\1\end{matrix}}}$

Плоские разбиения также часто описываются позициями единичных кубов. С этой точки зрения плоское разбиение можно определить как конечное подмножество положительных целых точек решетки ( i , j , k ) в , такое, что если ( r , s , t ) лежит в и если удовлетворяет , , и , то ( i , j , k ) также лежит в .${\displaystyle {\mathcal {P}}}$${\displaystyle \mathbb {N} ^{3}}$${\displaystyle {\mathcal {P}}}$${\displaystyle (i,j,k)}$${\displaystyle 1\leq i\leq r}$${\displaystyle 1\leq j\leq s}$${\displaystyle 1\leq k\leq t}$${\displaystyle {\mathcal {P}}}$

Сумма плоского разбиения равна

${\ displaystyle n = \ sum _ {i, j} \ pi _ {i, j}.}$

Сумма описывает количество кубов, из которых состоит плоское разбиение. Большой интерес к плоским разбиениям связан с перечислением плоских разбиений в различных классах. Количество плоских разбиений с суммой n обозначается как PL( n ). Например, существует шесть плоских разбиений с суммой 3

${\displaystyle {\begin{matrix}3\end{matrix}}\qquad {\begin{matrix}2&1\end{matrix}}\qquad {\begin{matrix}1&1&1\end{matrix}}\qquad {\begin{matrix}2\\1\end{matrix}}\qquad {\begin{matrix}1&1\\1\end{matrix}}\qquad {\begin{matrix}1\\1\\1\end{matrix}}}$

поэтому ПЛ(3) = 6.

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

Производящая функция для PL( n ) равна ^[1]

${\displaystyle \sum _{n=0}^{\infty }\operatorname {PL} (n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{(1-x^{k})^{k}}}=1+x+3x^{2}+6x^{3}+13x^{4}+24x^{5}+\cdots \qquad }$(последовательность A000219 в OEIS ).

Иногда ее называют функцией Мак-Магона , поскольку она была открыта Перси А. Мак-Магоном .

Эту формулу можно рассматривать как двумерный аналог формулы произведения Эйлера для числа целочисленных разбиений n . Аналогичная формула неизвестна для разбиений в более высоких размерностях (т.е. для сплошных разбиений ). ^[2] Асимптотика для плоских разбиений была впервые вычислена Э. М. Райтом . ^[3] Для больших получается , что ^[a]${\displaystyle n}$

${\displaystyle \operatorname {PL} (n)\sim {\frac {\zeta (3)^{7/36}}{\sqrt {12\pi }}}\ \left({\frac {n}{2}}\right)^{-25/36}\ \exp \left(3\ \zeta (3)^{1/3}\left({\frac {n}{2}}\right)^{2/3}+\zeta '(-1)\right).}$

Оценка численно дает

${\displaystyle \ln \operatorname {PL} (n)\sim 2.00945n^{2/3}-0.69444\ln n-1.4631.}$

Около 1896 года Мак-Магон в своей первой статье о плоских разбиениях установил производящую функцию плоских разбиений, которые являются подмножествами ящика . ^[5] Формула имеет вид${\displaystyle r\times s\times t}$${\displaystyle {\mathcal {B}}(r,s,t)=\{(i,j,k)|1\leq i\leq r,1\leq j\leq s,1\leq k\leq t\}}$$${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {1-q^{i+j+t-1}}{1-q^{i+j-1}}}}$$

Доказательство этой формулы можно найти в книге «Комбинаторный анализ», написанной Макмахоном. ^[6] Макмахон также упоминает производящие функции плоских разбиений. ^[7] Формулу для производящей функции можно записать альтернативным способом, который задается как$${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}\prod _{k=1}^{t}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}}$$

Умножение каждого компонента на и установка q  = 1 в приведенных выше формулах дает, что общее число плоских разбиений, которые помещаются в ящик, равно следующей формуле произведения: ^[8] Плоский случай (когда t = 1) дает биномиальные коэффициенты :${\displaystyle \textstyle {\frac {1-q}{1-q}}}$${\displaystyle N_{1}(r,s,t)}$${\displaystyle r\times s\times t}$${\displaystyle {\mathcal {B}}(r,s,t)}$$${\displaystyle N_{1}(r,s,t)=\prod _{(i,j,k)\in {\mathcal {B}}(r,s,t)}{\frac {i+j+k-1}{i+j+k-2}}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {i+j+t-1}{i+j-1}}.}$$

${\displaystyle {\mathcal {B}}(r,s,1)={\binom {r+s}{r}}.}$

Общее решение:

${\displaystyle {\begin{aligned}{\mathcal {B}}(r,s,t)&=\prod _{k=1}^{t}{\frac {(r+s+k-1)!(k-1)!}{(r+k-1)!(s+k-1)!}}\\&=\prod _{k=1}^{t}{\frac {{\binom {r+s+k-1}{r+k-1}}{\binom {r+s+k-1}{s+k-1}}}{{\binom {r+s+k-1}{r}}{\binom {s+k-1}{s}}}}\end{aligned}}}$

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

Специальные плоские разбиения включают симметричные, циклические и самодополнительные плоские разбиения, а также комбинации этих свойств.

В последующих разделах рассматривается перечисление специальных подклассов плоских разбиений внутри ящика. В этих статьях используются обозначения для числа таких плоских разбиений, где r , s и t — размеры рассматриваемого ящика, а i — индекс рассматриваемого случая.${\displaystyle N_{i}(r,s,t)}$

${\displaystyle {\mathcal {S}}_{2}}$— группа перестановок, действующих на первые две координаты точки. Эта группа содержит тождество, которое переводит ( i , j , k ) в себя, и транспозицию ( i , j , k ) → ( j , i , k ). Количество элементов в орбите обозначается как . обозначает множество орбит элементов под действием . Высота элемента ( i , j , k ) определяется как Высота увеличивается на единицу для каждого шага от заднего правого угла. Например, угловая позиция (1, 1, 1) имеет высоту 1 и ht (2, 1, 1) = 2. Высота орбиты определяется как высота любого элемента в орбите. Эта запись высоты отличается от записи Яна Г. Макдональда . ^[10]${\displaystyle \eta }$${\displaystyle |\eta |}$${\displaystyle {\mathcal {B}}/{\mathcal {S}}_{2}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {S}}_{2}}$$${\displaystyle ht(i,j,k)=i+j+k-2.}$$

Существует естественное действие группы перестановок на диаграмме Феррерса плоского разбиения — это соответствует одновременной перестановке трех координат всех узлов. Это обобщает операцию сопряжения для целочисленных разбиений . Действие может генерировать новые плоские разбиения, начиная с заданного плоского разбиения. Ниже показаны шесть плоских разбиений 4, которые генерируются действием . Только обмен первыми двумя координатами проявляется в представлении, приведенном ниже.${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {S}}_{3}}$

${\displaystyle {\begin{smallmatrix}3&1\end{smallmatrix}}\quad {\begin{smallmatrix}3\\1\end{smallmatrix}}\quad {\begin{smallmatrix}2&1&1\end{smallmatrix}}\quad {\begin{smallmatrix}2\\1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1&1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1\\1\\1\end{smallmatrix}}}$

${\displaystyle {\mathcal {C}}_{3}}$называется группой циклических перестановок и состоит из

${\displaystyle (i,j,k)\rightarrow (i,j,k),\quad (i,j,k)\rightarrow (j,k,i),\quad {\text{and }}\quad (i,j,k)\rightarrow (k,i,j).}$

Плоское разбиение называется симметричным, если π _{i , j} = π _j,i для всех i , j . Другими словами, плоское разбиение симметрично, если тогда и только тогда, когда . Плоские разбиения этого типа симметричны относительно плоскости x = y . Ниже приведен пример симметричного плоского разбиения и его визуализация.${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle (j,i,k)\in {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}4&3&3&2&1\\3&3&2&1&\\3&2&2&1&\\2&1&1&&\\1&&&&\end{matrix}}}$

В 1898 году Мак-Магон сформулировал свою гипотезу о производящей функции для симметричных плоских разбиений, которые являются подмножествами . ^[11] Эта гипотеза называется гипотезой Мак-Магона . Производящая функция задается формулой${\displaystyle {\mathcal {B}}(r,r,t)}$$${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{i=1}^{r}\left[{\frac {1-q^{t+2i-1}}{1-q^{2i-1}}}\prod _{j=i+1}^{r}{\frac {1-q^{2(i+j+t-1)}}{1-q^{2(i+j-1)}}}\right]}$$

Макдональд ^[10] указал, что гипотеза Перси А. Макмахона сводится к

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}}$

В 1972 году Эдвард А. Бендер и Дональд Э. Кнут выдвинули гипотезу ^[12] о простой замкнутой форме для производящей функции для плоского разбиения, которое имеет не более r строк и строго убывает вдоль строк. Джордж Эндрюс показал ^[13] , что гипотеза Бендера и Кнута и гипотеза Макмахона эквивалентны. Гипотеза Макмахона была доказана почти одновременно Джорджем Эндрюсом в 1977 году ^[14] , а позже Ян Г. Макдональд представил альтернативное доказательство. ^[15] При установке q  = 1 получается подсчитывающая функция , которая задается как${\displaystyle N_{2}(r,r,t)}$

${\displaystyle N_{2}(r,r,t)=\prod _{i=1}^{r}{\frac {2i+t-1}{2i-1}}\prod _{1\leq i<j\leq r}{\frac {i+j+t-1}{i+j-1}}}$

Доказательство случая q  = 1 см. в статье Джорджа Эндрюса « Гипотеза Мак-Магона о симметричных разбиениях плоскости» . ^[16]

π называется циклически симметричным, если i -я строка сопряжена с i -м столбцом для всех i . i -я строка рассматривается как обычное разбиение. Сопряженным разбиением является разбиение, диаграмма которого является транспонированной диаграммой разбиения . ^[10] Другими словами, плоское разбиение циклически симметрично, если всякий раз, когда то ( k , i , j ) и ( j , k , i ) также принадлежат . Ниже приведен пример циклически симметричного плоского разбиения и его визуализация.${\displaystyle \pi }$${\displaystyle \pi }$${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}6&5&5&4&3&3\\6&4&3&3&1&\\6&4&3&1&1&\\4&2&2&1&&\\3&1&1&&&\\1&1&1&&&\end{matrix}}}$

Гипотеза Макдональда дает формулу для вычисления числа циклически симметричных плоских разбиений для заданного целого числа r . Эта гипотеза называется гипотезой Макдональда . Производящая функция для циклически симметричных плоских разбиений, которые являются подмножествами , задается как${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}}$

Это уравнение можно записать и по-другому

${\displaystyle \prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}=\prod _{i=1}^{r}\left[{\frac {1-q^{3i-1}}{1-q^{3i-2}}}\prod _{j=i}^{r}{\frac {1-q^{3(r+i+j-1)}}{1-q^{3(2i+j-1)}}}\right]}$

В 1979 году Эндрюс доказал гипотезу Макдональда для случая q  = 1 как «слабую» гипотезу Макдональда . ^[17] Три года спустя Уильям Х. Миллс, Дэвид Роббинс и Говард Рамси доказали общий случай гипотезы Макдональда в своей статье « Доказательство гипотезы Макдональда» . ^[18] Формула для дается «слабой» гипотезой Макдональда${\displaystyle N_{3}(r,r,r)}$

${\displaystyle N_{3}(r,r,r)=\prod _{i=1}^{r}\left[{\frac {3i-1}{3i-2}}\prod _{j=i}^{r}{\frac {i+j+r-1}{2i+j-1}}\right]}$

Полностью симметричное плоское разбиение — это плоское разбиение, которое симметрично и циклически симметрично. Это означает, что диаграмма симметрична во всех трех диагональных плоскостях, или, другими словами, что если то все шесть перестановок ( i , j , k ) также находятся в . Ниже приведен пример матрицы для полностью симметричного плоского разбиения. На рисунке показана визуализация матрицы.${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}5&4&4&3&1\\4&3&3&1&\\4&3&2&1&\\3&1&1&&\\1&&&&\end{matrix}}}$

Макдональд нашел общее число полностью симметричных плоских разбиений, которые являются подмножествами . Формула имеет вид${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle N_{4}(r,r,r)=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1+ht(\eta )}{ht(\eta )}}}$

В 1995 году Джон Р. Стембридж впервые доказал формулу для ^[19] , а позднее в 2005 году ее доказали Джордж Эндрюс, Питер Пол и Карстен Шнайдер. ^[20] Около 1983 года Эндрюс и Роббинс независимо друг от друга сформулировали явную формулу произведения для производящей функции подсчета орбит для полностью симметричных плоских разбиений. ^{[21] [22]} Эта формула уже упоминалась в статье Джорджа Э. Эндрюса Полностью симметричные плоские разбиения , опубликованной в 1980 году. ^[23] Гипотеза называется гипотезой q -TSPP и задается следующим образом:${\displaystyle N_{4}(r,r,r)}$

Пусть будет симметричной группой. Функция подсчета орбит для полностью симметричных плоских разбиений, которые помещаются внутри, задается формулой${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1-q^{1+ht(\eta )}}{1-q^{ht(\eta )}}}=\prod _{1\leq i\leq j\leq k\leq r}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}.}$

Эта гипотеза была доказана в 2011 году Кристофом Кутшаном , Мануэлем Кауэрсом и Дороном Зейлбергером . ^[24]

Если для всех , , то плоское разбиение называется самодополнительным. Необходимо, чтобы произведение было четным. Ниже приведен пример самодополнительного симметричного плоского разбиения и его визуализация.${\displaystyle \pi _{i,j}+\pi _{r-i+1,s-j+1}=t}$${\displaystyle 1\leq i\leq r}$${\displaystyle 1\leq j\leq s}$${\displaystyle r\cdot s\cdot t}$

${\displaystyle {\begin{matrix}4&4&3&2&1\\4&2&2&2&\\3&2&1&&\end{matrix}}}$

Ричард П. Стэнли ^[25] предположил формулы для общего числа самодополнительных плоских разбиений . По словам Стэнли, Роббинс также сформулировал формулы для общего числа самодополнительных плоских разбиений в другой, но эквивалентной форме. Общее число самодополнительных плоских разбиений, которые являются подмножествами, определяется как${\displaystyle N_{5}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle N_{5}(2r,2s,2t)=N_{1}(r,s,t)^{2}}$

${\displaystyle N_{5}(2r+1,2s,2t)=N_{1}(r,s,t)N_{1}(r+1,s,t)}$

${\displaystyle N_{5}(2r+1,2s+1,2t)=N_{1}(r+1,s,t)N_{1}(r,s+1,t)}$

Необходимо, чтобы произведение r, s и t было четным. Доказательство можно найти в статье Symmetries of Plane Partitions , написанной Стэнли. ^{[26] [25]} Доказательство работает с функциями Шура . Доказательство Стэнли обычного перечисления самодополнительных плоских разбиений дает q -аналог путем замены на . ^[27] Это особый случай формулы Стэнли для крюкового содержания. ^[28] Производящая функция для самодополнительных плоских разбиений задается как${\displaystyle s_{s^{r}}(x)}$${\displaystyle x_{i}=q^{i}}$${\displaystyle i=1,\ldots ,n}$

${\displaystyle s_{\gamma ^{\alpha }}(q,q^{2},\ldots ,q^{n})=q^{\gamma \alpha (\alpha +1)/2}\prod _{i=1}^{\alpha }\prod _{j=0}^{\gamma -1}{\frac {1-q^{i+n-\alpha +j}}{1-q^{i+j}}}}$

Подставляя эту формулу в

${\displaystyle s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})^{2}\ {\text{ for }}{\mathcal {B}}(2r,2s,2t)}$

${\displaystyle s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})s_{(s+1)^{r}}(x_{1},x_{2},\ldots ,x_{t+r}){\text{ for }}{\mathcal {B}}(2r,2s+1,2t)}$

${\displaystyle s_{s^{r+1}}(x_{1},x_{2},\ldots ,x_{t+r+1})s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r+1}){\text{ for }}{\mathcal {B}}(2r+1,2s,2t+1)}$

обеспечивает желаемый q -аналоговый случай.

Плоское разбиение называется циклически симметричным самодополнительным, если оно циклически симметрично и самодополнительно. На рисунке представлено циклически симметричное самодополнительное плоское разбиение, а соответствующая матрица приведена ниже.${\displaystyle \pi }$

${\displaystyle {\begin{matrix}4&4&4&1\\3&3&2&1\\3&2&1&1\\3&&&\end{matrix}}}$

В частной беседе со Стэнли Роббинс высказал предположение, что общее число циклически симметричных самодополнительных плоских разбиений определяется как . ^{[22] [25]} Общее число циклически симметричных самодополнительных плоских разбиений определяется как${\displaystyle N_{6}(2r,2r,2r)}$

${\displaystyle N_{6}(2r,2r,2r)=D_{r}^{2}}$

${\displaystyle D_{r}}$это число матриц с чередующимися знаками . Формула для имеет вид${\displaystyle r\times r}$ ${\displaystyle D_{r}}$

${\displaystyle D_{r}=\prod _{j=0}^{r-1}{\frac {(3j+1)!}{(r+j)!}}}$

Грег Куперберг доказал формулу в 1994 году. ^[9]${\displaystyle N_{6}(r,r,r)}$

Полностью симметричное самодополнительное плоское разбиение — это плоское разбиение, которое является одновременно полностью симметричным и самодополнительным. Например, матрица ниже является таким плоским разбиением; оно визуализировано на прилагаемом рисунке.

${\displaystyle {\begin{matrix}6&6&6&5&5&3\\6&5&5&3&3&1\\6&5&5&3&3&1\\5&3&3&1&1&\\5&3&3&1&1&\\3&1&1&&&\end{matrix}}}$

Формула была предложена Уильямом Х. Миллсом, Роббинсом и Говардом Рамси в их работе «Самодополняющие полностью симметричные плоские разбиения» . ^[29] Общее число полностью симметричных самодополнительных плоских разбиений определяется по формуле${\displaystyle N_{7}(r,r,r)}$

${\displaystyle N_{7}(2r,2r,2r)=D_{r}}$

Эндрюс доказывает эту формулу в 1994 году в своей статье « Плоские разбиения V: гипотеза TSSCPP» . ^[30]

• Гауссовские биномиальные коэффициенты
• Воксель

• Г. Эндрюс , Теория разделов , Cambridge University Press, Кембридж, 1998, ISBN 0-521-63766-X 
• Бендер, Эдвард А.; Кнут, Дональд Э. (1972), «Перечисление плоских разбиений», Журнал комбинаторной теории, Серия A , 13 : 40–54 , doi :10.1016/0097-3165(72)90007-6, ISSN  1096-0899, MR  0299574
• IG Macdonald , Симметричные функции и многочлены Холла , Oxford University Press, Оксфорд, 1999, ISBN 0-19-850450-0 
• П. А. Макмахон , Комбинаторный анализ , 2 тома, Cambridge University Press, 1915–1916.

• Вайсштейн, Эрик В. "Плоское разбиение". MathWorld .
• Страница DLMF о плоских разбиениях