Теорема о помеченном перечислении

В комбинаторной математике теорема о помеченном перечислении является аналогом теоремы о перечислении Пойа для помеченного случая, когда у нас есть набор помеченных объектов, заданных экспоненциальной производящей функцией (EGF) g ( z ), которые распределяются по n слотам и группа перестановок G , которая переставляет слоты, создавая таким образом классы эквивалентности конфигураций. Существует специальная операция перемаркировки, которая перемаркирует объекты в слотах, присваивая метки от 1 до k , где k — общее количество узлов, т.е. сумма количества узлов отдельных объектов. ЭФР $f_{n}(z)$ числа различных конфигураций в рамках этого процесса перемаркировки определяется выражением

$f_{n}(z)={\frac {g(z)^{n}}{|G|}}.$

В частности, если G — симметрическая группа порядка n (следовательно, | G | = n !), функции $f_{n}(z)$ могут быть дополнительно объединены в одну производящую функцию :

$F(z,t)=\sum _{n=0}^{\infty }f_{n}(z)t^{n}=\sum _{n=0}^{\infty }{\frac {g(z)^{n}}{n!}}t^{n}=e^{g(z)t}$

который является экспоненциальным относительно переменной z и обычным относительно переменной t .

Процесс перемаркировки

Набор циклов, которые переименовываются для формирования перестановки. (Есть три слота и $G=S_{3}$.)

Мы предполагаем, что объект $\omega$ размера $|\omega |$ в лице $z^{|\omega |}/|\omega |!$ содержит $|\omega |=m$ помеченные внутренние узлы с метками от 1 до m . Действие G на слоты значительно упрощается по сравнению со случаем без меток, поскольку метки различают объекты в слотах, а орбиты под G имеют одинаковый размер. $|G|$. (ЭФР g ( z ) не может включать в себя объекты нулевого размера. Это связано с тем, что они не выделяются метками и поэтому наличие двух и более таких объектов создает орбиты, размер которых меньше $|G|$.) Как уже говорилось, узлы объектов перемаркируются при их распределении по слотам. Скажи предмет размером $r_{1}$ в первый слот входит объект размером $r_{2}$ во второй слот и так далее, а общий размер конфигурации равен k , так что

$r_{1}+r_{2}+\cdots +r_{n}=k.$

Процесс перемаркировки работает следующим образом: выберите один из

${k \choose r_{1},r_{2},\ldots ,r_{n}}$

разбиение набора из k меток на подмножества размером $r_{1},r_{2},\ldots r_{n}.$Теперь переименуйте внутренние узлы каждого объекта, используя метки из соответствующего подмножества, сохраняя порядок меток. Например, если первый объект содержит четыре узла, помеченных от 1 до 4, и набор меток, выбранный для этого объекта, равен {2, 5, 6, 10}, то узел 1 получает метку 2, узел 2, метку 5, узел 3. , метка 6 и узел 4, метка 10. Таким образом, метки на объектах создают уникальную маркировку с использованием меток из подмножества $[k]$ выбран для объекта.

Доказательство теоремы

Из конструкции перемаркировки следует, что существуют

${\frac {1}{|G|}}\sum _{r_{1}+r_{2}+\cdots +r_{n}=k}{k \choose r_{1},r_{2},\ldots ,r_{n}}\;r_{1}![z^{r_{1}}]g(z)\;r_{2}![z^{r_{2}}]g(z)\;\cdots \;r_{n}![z^{r_{n}}]g(z)$

или

${\frac {k!}{|G|}}\sum _{r_{1}+r_{2}+\cdots +r_{n}=k}[z^{r_{1}}]g(z)[z^{r_{2}}]g(z)\cdots [z^{r_{n}}]g(z)\;=\;{\frac {k!}{|G|}}[z^{k}]g(z)^{n}$

различные конфигурации общего размера k . Формула возвращает целое число, поскольку $[z^{k}]g(z)^{n}$ равно нулю при k < n (помните, что g не включает объекты нулевого размера) и когда $k\geq n$ у нас есть $n!|k!$ и порядок $|G|$ группы G делит порядок $S_{n}$, что $n!$, по теореме Лагранжа . Вывод состоит в том, что EGF меченых конфигураций определяется выражением

$f_{n}(z)=\sum _{k\geq 0}\left({\frac {k!}{|G|}}[z^{k}]g(z)^{n}\right){\frac {z^{k}}{k!}}={\frac {1}{|G|}}\sum _{k\geq 0}z^{k}[z^{k}]g(z)^{n}={\frac {g(z)^{n}}{|G|}}.$

Эту формулу можно также получить путем перебора последовательностей, т. е. случая, когда слоты не переставляются, и используя приведенный выше аргумент без $1/|G|$-фактор, чтобы показать, что их производящая функция при перемаркировке определяется выражением $g(z)^{n}$. Наконец, обратите внимание, что каждая последовательность принадлежит орбите размера $|G|$, следовательно, производящая функция орбит имеет вид $g(z)^{n}/|G|.$

Ссылки

• Франсуа Бержерон, Жильбер Лабель, Пьер Леру, Теория видов и комбинаторика древовидных структур , LaCIM, Монреаль (1994). Английская версия: Комбинаторные виды и древовидные структуры , Издательство Кембриджского университета (1998).