Полином порядка - Order polynomial

Смотрите также: Порядок полинома

В порядковый полином это многочлен изучал математику, в частности алгебраическая теория графов и алгебраическая комбинаторика. Полином порядка подсчитывает количество сохраняющих порядок отображений из посеть к цепь длины ${\displaystyle n}$. Эти сохраняющие порядок отображения были впервые введены Ричард П. Стэнли при изучении упорядоченных конструкций и перегородок в докторантуре. студент на Гарвардский университет в 1971 г. под руководством Джан-Карло Рота.

Определение

Позволять ${\displaystyle P}$ быть конечный посеть с ${\displaystyle p}$ обозначенные элементы ${\displaystyle x,y\in P}$, и разреши ${\displaystyle [n]=\{1<2<\ldots <n\}}$ быть цепь ${\displaystyle n}$ элементы. Карта ${\displaystyle \phi :P\to [n]}$ сохраняет порядок, если ${\displaystyle x\leq y}$ подразумевает ${\displaystyle \phi (x)\leq \phi (y)}$. Количество таких отображений полиномиально растет с увеличением ${\displaystyle n}$, а функция, подсчитывающая их количество, - это порядковый полином ${\displaystyle \Omega (n)=\Omega (P,n)}$.

Точно так же мы можем определить порядковый полином, который подсчитывает количество строго сохраняющие порядок карты ${\displaystyle \phi :P\to [n]}$, смысл ${\displaystyle x<y}$ подразумевает ${\displaystyle \phi (x)<\phi (y)}$. Количество таких карт равно полином строгого порядка ${\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}$.^[1]

Обе ${\displaystyle \Omega (n)}$ и ${\displaystyle \Omega ^{\circ }\!(n)}$ иметь степень ${\displaystyle p}$. Карты, сохраняющие порядок, обобщают линейные расширения из ${\displaystyle P}$, сохраняющие порядок биекции ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$. Фактически, старший коэффициент ${\displaystyle \Omega (n)}$ и ${\displaystyle \Omega ^{\circ }\!(n)}$ количество линейных расширений, деленное на ${\displaystyle p!}$.

Примеры

Сдача ${\displaystyle P}$ быть цепь из ${\displaystyle p}$ элементы, у нас есть

${\displaystyle \Omega (n)={\binom {n+k-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)}$ и ${\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}$

Существует только одно линейное расширение (тождественное отображение), и оба многочлена имеют главный член ${\displaystyle {\tfrac {1}{p!}}n^{p}}$.

Сдача ${\displaystyle P}$ быть антицепь из ${\displaystyle p}$ несравнимые элементы, у нас есть ${\displaystyle \Omega (n)=\Omega ^{\circ }(n)=n^{p}}$. Поскольку любая биекция ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$ (строго) сохраняющий порядок, есть ${\displaystyle p!}$ линейные расширения, и оба полинома сводятся к главному члену ${\displaystyle {\tfrac {p!}{p!}}n^{p}=n^{p}}$.

Теорема взаимности

Существует связь между картами, строго сохраняющими порядок, и картами, сохраняющими порядок:^[2]

${\displaystyle \Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).}$

В случае, если ${\displaystyle P}$ цепь, это восстанавливает отрицательная биномиальная идентичность. Есть аналогичные результаты для хроматический полином и Многочлен Эрхарта (см. ниже), все частные случаи общей Теорема взаимности.^[3]

Связи с другими счетными многочленами

Хроматический полином

В хроматический полином ${\displaystyle P(G,n)}$считает количество правильных раскраски конечного график ${\displaystyle G}$ с ${\displaystyle n}$ доступные цвета. Для ациклическая ориентация ${\displaystyle \sigma }$ краев ${\displaystyle G}$, на вершинах существует естественный частичный порядок "ниже по потоку" ${\displaystyle V(G)}$ подразумевается основными отношениями ${\displaystyle u>v}$ в любое время ${\displaystyle u\rightarrow v}$ направленный край ${\displaystyle \sigma }$. (Таким образом Диаграмма Хассе чугуна является подграфом ориентированного графа ${\displaystyle \sigma }$.) Мы говорим ${\displaystyle \phi :V(G)\rightarrow [n]}$ совместим с ${\displaystyle \sigma }$ если ${\displaystyle \phi }$ сохраняет порядок. Тогда у нас есть

${\displaystyle P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),}$

куда ${\displaystyle \sigma }$ пробегает все ациклические ориентации ГРАММ, рассматриваются как структуры poset.^[4]

Порядковый многогранник и многочлен Эрхарта

Основная статья: Многогранник порядка

В порядковый многогранник ассоциирует многогранник с частичным заказом. Для посета ${\displaystyle P}$ с ${\displaystyle p}$ элементы, многогранник порядка ${\displaystyle O(P)}$ - множество сохраняющих порядок отображений ${\displaystyle f:P\to [0,1]}$, куда ${\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}$ - упорядоченный единичный интервал, непрерывный цепной ч.^[5][6] Более геометрически мы можем перечислить элементы ${\displaystyle P=\{x_{1},\ldots ,x_{p}\}}$, и определить любое отображение ${\displaystyle f:P\to \mathbb {R} }$ с точкой ${\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}$; то многогранник порядка - это множество точек ${\displaystyle (t_{1},\ldots ,t_{p})\in [0,1]^{p}}$ с ${\displaystyle t_{i}\leq t_{j}}$ если ${\displaystyle x_{i}\leq x_{j}}$.^[7]

В Многочлен Эрхарта считает количество целочисленная решетка точки внутри дилатации многогранник. В частности, рассмотрим решетку ${\displaystyle L=\mathbb {Z} ^{n}}$ и ${\displaystyle d}$-мерный многогранник ${\displaystyle K\subset \mathbb {R} ^{d}}$ с вершинами в ${\displaystyle L}$; затем мы определяем

${\displaystyle L(K,n)=\#(nK\cap L),}$

количество точек решетки в ${\displaystyle nK}$, расширение ${\displaystyle K}$ положительным целым скаляром ${\displaystyle n}$. Ehrhart показал, что это рациональный многочлен степени ${\displaystyle d}$ в переменной ${\displaystyle n}$, при условии ${\displaystyle K}$ имеет вершины в решетке.^[8]

Фактически, многочлен Эрхарта многогранника порядка равен многочлену порядка исходного чугуна (со смещенным аргументом):^[7][9]

${\displaystyle L(O(P),n)\ =\ \Omega (P,n{+}1).}$

Это непосредственное следствие определений, учитывая вложение ${\displaystyle (n{+}1)}$-сеть посет ${\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }$.

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

1. Стэнли, Ричард П. (1972). Заказные конструкции и перегородки. Провиденс, Род-Айленд: Американское математическое общество.
2. Стэнли, Ричард П. (1970). «Хроматический многочлен для упорядоченных множеств». Proc. Вторая конференция Чапел-Хилл по комбинаторной математике и ее приложениям.: 421–427.
3. Стэнли, Ричард П., 1944- (2012). «4.5.14 Теорема взаимности для линейных однородных диофантовых уравнений». Перечислительная комбинаторика. Том 1 (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  9781139206549. OCLC  777400915.
4. Стэнли, Ричард П. (1973). «Ациклические ориентации графов». Дискретная математика. 5 (2): 171–178. Дои:10.1016 / 0012-365X (73) 90108-8.
5. Карзанов, Александр; Хачиян, Леонид (1991). «О порядке проведения цепей Маркова». Заказ. 8: 7–15. Дои:10.1007 / BF00385809.
6. Брайтвелл, Грэм; Винклер, Питер (1991). «Подсчет линейных расширений». Заказ. 8 (3): 225–242. Дои:10.1007 / BF00383444.
7. Стэнли, Ричард П. (1986). "Два посета многогранника". Дискретные вычисления. Geom. 1: 9–23. Дои:10.1007 / BF02187680.
8. Бек, Матиас; Робинс, Синай (2015). Вычисление непрерывного дискретного. Нью-Йорк: Спрингер. С. 64–72. ISBN  978-1-4939-2968-9.
9. Линиал, Натан (1984). «Теоретико-информационная оценка хороша для слияния». SIAM J. Comput. 13 (4): 795–801. Дои:10.1137/0213049.
   Кан, Джефф; Ким, Чон Хан (1995). «Энтропия и сортировка». Журнал компьютерных и системных наук. 51: 390–399. Дои:10.1145/129712.129731. ISBN  0897915119.