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

Аналог теоремы Полиа о перечислении для помеченного случая

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

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

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

${\displaystyle 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 .

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

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

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

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

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

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

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

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

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

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

или

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

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

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

Ссылки

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