Циклическое просеивание

В комбинаторной математике циклическое просеивание — это явление, с помощью которого при оценке производящей функции для конечного набора корней из единицы подсчитываются классы симметрии объектов, на которые действует циклическая группа .

Определение

Пусть C — циклическая группа, порожденная элементом c порядка n . Предположим, действует на множестве X. C Пусть X ( q ) — многочлен с целыми коэффициентами. тройка ( X , C , X ( q Тогда говорят, что )) демонстрирует явление циклического просеивания ( CSP ), если для всех целых d значение X ( e ^{2 π ид / п} ) — количество элементов, фиксированных c ^д . В частности, ( 1) — это мощность множества X , и по этой причине X ( q ) рассматривается как производящая функция для X. X

Примеры

коэффициент q -биномиальный

$\left[{n \atop k}\right]_{q}$

– многочлен от q, определяемый формулой

$\left[{n \atop k}\right]_{q}={\frac {\prod _{i=1}^{n}(1+q+q^{2}+\cdots +q^{i-1})}{\left(\prod _{i=1}^{k}(1+q+q^{2}+\cdots +q^{i-1})\right)\cdot \left(\prod _{i=1}^{n-k}(1+q+q^{2}+\cdots +q^{i-1})\right)}}.$

Легко видеть, что его значение при q = 1 представляет собой обычный биномиальный коэффициент ${\binom {n}{k}}$, поэтому это производящая функция для подмножеств {1, 2, ..., n } размера k . Эти подмножества несут естественное действие циклической группы C порядка n , которая действует путем добавления 1 к каждому элементу набора по модулю n . Например, когда n = 4 и k = 2, групповые орбиты имеют вид

$\{1,3\}\to \{2,4\}\to \{1,3\}$ (размера 2)

и

$\{1,2\}\to \{2,3\}\to \{3,4\}\to \{1,4\}\to \{1,2\}$ (размера 4).

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

В примере n = 4 и k = 2 q -биномиальный коэффициент равен

$\left[{4 \atop 2}\right]_{q}=1+q+2q^{2}+q^{3}+q^{4};$

оценка этого полинома при q = 1 дает 6 (поскольку все шесть подмножеств фиксируются единичным элементом группы); вычисление его при q = −1 дает 2 (подмножества {1, 3} и {2, 4} фиксируются двумя применениями генератора групп); и вычисление его при q = ± i дает 0 (одним или тремя применениями генератора группы не фиксируются никакие подмножества).

Список явлений циклического просеивания

В статье Райнера-Стэнтона-Уайта приведен следующий пример:

Пусть α — композиция n , и пусть W ( α ) — множество всех слов длины n с α _i буквами, равными i . Спуском называется слова w любой индекс j такой, что $w_{j}>w_{j+1}$. Определить основной индекс $\operatorname {maj} (w)$ о словах как о сумме всех спусков.

---

тройка $(X_{n},C_{n-1},{\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q})$ демонстрируют явление циклического просеивания, при котором $X_{n}$ — множество непересекающихся (1,2)-конфигураций [ n − 1].

---

Пусть λ — прямоугольное разбиение размера n , и пусть X — множество стандартных таблиц Юнга формы λ . Пусть C = Z / nZ действует на X посредством раскрутки. Затем $(X,C,{\frac {[n]!_{q}}{\prod _{(i,j)\in \lambda }[h_{ij}]_{q}}})$ демонстрируют явление циклического просеивания. Обратите внимание, что полином является q -аналогом формулы длины крюка .

Кроме того, пусть λ — прямоугольное разбиение размера n , и пусть X — множество полустандартных таблиц Юнга формы λ . Пусть C = Z / kZ действует на X посредством k -продвижения. Затем $(X,C,q^{-\kappa (\lambda )}s_{\lambda }(1,q,q^{2},\dotsc ,q^{k-1}))$ демонстрируют явление циклического просеивания. Здесь, $\kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}$ и s _λ — полином Шура .

---

Возрастающая таблица — это полустандартная таблица Юнга, в которой и строки, и столбцы строго возрастают, а набор записей имеет вид $1,2,\dotsc ,\ell$ для некоторых $\ell$.Позволять $Inc_{k}(2\times n)$ обозначаем набор возрастающей таблицы с двумя строками длины n и максимальной записью $2n-k$. Затем $(\operatorname {Inc} _{k}(2\times n),C_{2n-k},q^{n+{\binom {k}{2}}}{\frac {\left[{n-1 \atop k}\right]_{q}\left[{2n-k \atop n-k-1}\right]_{q}}{[n-k]_{q}}})$ демонстрируют явление циклического просеивания, при котором $C_{2n-k}$ действовать через K -продвижение.

---

Позволять $S_{\lambda ,j}$ — множество перестановок типа цикла λ и ровно j превышений. Позволять $a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-\operatorname {exc} (\sigma )}$, и пусть $C_{n}$ действовать дальше $S_{\lambda ,j}$ путем конъюгации.

Затем $(S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))$ демонстрируют явление циклического просеивания.

Примечания и ссылки

• Саган, Брюс (2011). «Феномен циклического просеивания: обзор» . В Чепмен, Робин (ред.). Обзоры по комбинаторике 2011 . Серия лекций Лондонского математического общества. Том. 392. Издательство Кембриджского университета. стр. 183–233. ISBN  978-1-139-50368-6 .