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

Плоский раздел из 30 элементов, представленный стопками единичных кубов.

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

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

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

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

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

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

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

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

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

${\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}}$

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

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

Производящая функция плоских перегородок

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

$\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 Эту формулу . ) неизвестна Аналогичная формула для разбиений в более высоких измерениях (т. е. для сплошных перегородок . Асимптотика плоских разбиений была впервые вычислена Э. М. Райтом . Получается, для больших $n$, что

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

Численная оценка доходности

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

Плоские перегородки в коробе

Примерно в 1896 году Мак-Магон ввел производящую функцию плоских перегородок, которые являются подмножествами $r\times s\times t$ коробка ${\mathcal {B}}(r,s,t)=\{(i,j,k)|1\leq i\leq r,1\leq j\leq s,1\leq k\leq t\}$ в своей первой статье о плоских перегородках. Формула имеет вид $$\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}}}$$

Доказательство этой формулы можно найти в книге «Комбинаторный анализ» . Мак-Магона Мак-Магон также упоминает производящие функции плоских разбиений. Формулу производящей функции можно записать альтернативным способом: $$\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}}}$$

Умножив каждую составляющую на $\textstyle {\frac {1-q}{1-q}}$, а полагая q = 1 в приведенных выше формулах, получаем общее число $N_{1}(r,s,t)$ плоских перегородок, которые вписываются в $r\times s\times t$ коробка ${\mathcal {B}}(r,s,t)$ равен следующей формуле произведения: $$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}}.$$Плоский случай (когда t = 1) дает биномиальные коэффициенты :

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

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

${\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}}$

Специальные плоские перегородки

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

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

Действие S ₂ , S ₃ и C ₃ на плоские перегородки

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

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

${\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}}$

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

$(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).$

Симметричные плоские перегородки

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

Симметричная плоская перегородка, сумма 35

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

В 1898 году Мак-Магон сформулировал свою гипотезу о производящей функции для симметричных плоских разбиений, которые являются подмножествами ${\mathcal {B}}(r,r,t)$. Эта гипотеза называется гипотезой Мак-Магона . Производящая функция определяется выражением $$\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]$$

Макдональд отметил, что гипотеза Перси А. Мак-Магона сводится к

$\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 году Эдвард А. Бендер и Дональд Э. Кнут предположили, что простая замкнутая форма производящей функции для плоского разбиения, имеющего не более r строк и строгого убывания по строкам. Джордж Эндрюс показал что гипотеза Бендера и Кнута и гипотеза Мак-Магона эквивалентны. Гипотеза Мак-Магона была почти одновременно доказана Джорджем Эндрюсом в 1977 году. а позже Ян Г. Макдональд представил альтернативное доказательство. При установке q = 1 получается считающая функция $N_{2}(r,r,t)$ который дается

$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 обратитесь к статье Джорджа Эндрюса « Гипотеза Мак-Магона о симметричных плоских разбиениях» .

Циклически симметричные плоские разбиения

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

Циклически симметричное плоское разбиение

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

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

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

$\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 как «слабую» гипотезу Макдональда . Три года спустя Уильям Х. Миллс, Дэвид Роббинс и Говард Рамси доказали общий случай гипотезы Макдональда в своей статье « Доказательство гипотезы Макдональда» . Формула для $N_{3}(r,r,r)$ дается «слабой» гипотезой Макдональда

$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]$

Полностью симметричные плоские перегородки

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

Полностью симметричная плоская перегородка

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

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

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

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

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

$\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 году Кристоф Кутшан , Мануэль Кауэрс и Дорон Зейлбергер .

Самодополняющие плоские перегородки

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

Самодополняющая плоская перегородка

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

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

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

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

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

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

$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}}}$

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

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

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

$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 -аналоговый случай.

Циклически симметричные самодополняющие плоские разбиения

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

Циклически симметричное самодополняющее плоское разбиение

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

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

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

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

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

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

Полностью симметричные самодополняющие плоские перегородки

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

Полностью симметричное самодополняющее плоское разбиение

${\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}}$

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

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

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

См. также

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

Ссылки

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

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

• Вайсштейн, Эрик В. «Плоская перегородка» . Математический мир .
• Страница DLMF о плоских перегородках