Экспоненциальная формула

В комбинаторной математике экспоненциальная формула называемая разложением полимера ( в физике ) утверждает, что экспоненциальная производящая функция для структур на конечных множествах является экспоненциальной производящей функцией для связанных структур.Экспоненциальная формула представляет собой вариант степенного ряда частного случая формулы Фаа ди Бруно .

Алгебраическое утверждение

Это чисто алгебраическое утверждение как первое введение в комбинаторное использование формулы.

Для любого формального степенного ряда вида $f(x)=a_{1}x+{a_{2} \over 2}x^{2}+{a_{3} \over 6}x^{3}+\cdots +{a_{n} \over n!}x^{n}+\cdots \,$ у нас есть $\exp f(x)=e^{f(x)}=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n},\,$ где $b_{n}=\sum _{\pi =\left\{\,S_{1},\,\dots ,\,S_{k}\,\right\}}a_{\left|S_{1}\right|}\cdots a_{\left|S_{k}\right|},$ и индекс $\pi$ проходит через все разделы $\{S_{1},\ldots ,S_{k}\}$ из набора $\{1,\ldots ,n\}$ . (Когда $k=0,$ произведение пусто и по определению равно $1$ .)

Формула в других выражениях

Формулу можно записать в следующем виде: $b_{n}=B_{n}(a_{1},a_{2},\dots ,a_{n}),$ и таким образом $\exp \left(\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},$ где $B_{n}(a_{1},\ldots ,a_{n})$ это $n$ полный полином Белла .

В качестве альтернативы экспоненциальную формулу также можно записать с использованием индекса цикла следующим симметричной группы образом: $\exp \left(\sum _{n=1}^{\infty }a_{n}{x^{n} \over n}\right)=\sum _{n=0}^{\infty }Z_{n}(a_{1},\dots ,a_{n})x^{n},$ где $Z_{n}$ обозначает полином индекса цикла для симметричной группы $S_{n}$ , определяемый как: $Z_{n}(x_{1},\cdots ,x_{n})={\frac {1}{n!}}\sum _{\sigma \in S_{n}}x_{1}^{\sigma _{1}}\cdots x_{n}^{\sigma _{n}}$ и $\sigma _{j}$ обозначает количество циклов $\sigma$ размера $j\in \{1,\cdots ,n\}$ . Это следствие общего отношения между $Z_{n}$ и полиномы Белла : $Z_{n}(x_{1},\dots ,x_{n})={1 \over n!}B_{n}(0!\,x_{1},1!\,x_{2},\dots ,(n-1)!\,x_{n}).$

Комбинаторная интерпретация

В комбинаторных приложениях числа $a_{n}$ подсчитать количество какой-то «связной» структуры на $n$ -множество точек и числа $b_{n}$ подсчитайте количество (возможно, несвязных) структур. Числа $b_{n}/n!$ подсчитать количество классов изоморфизма структур на $n$ точки, причем каждая структура имеет вес, обратный ее группе автоморфизмов , и числа $a_{n}/n!$ Аналогично подсчитывают классы изоморфизма связных структур.

Примеры

$b_{3}=B_{3}(a_{1},a_{2},a_{3})=a_{3}+3a_{2}a_{1}+a_{1}^{3},$ потому что есть один раздел набора $\{1,2,3\}$ который имеет один блок размером $3$ , есть три раздела $\{1,2,3\}$ который разделил его на блок размером $2$ и блок размером $1$ , и есть один раздел $\{1,2,3\}$ который разбивает его на три блока размером $1$ . Это также следует из $Z_{3}(a_{1},a_{2},a_{3})={1 \over 6}(2a_{3}+3a_{1}a_{2}+a_{1}^{3})={1 \over 6}B_{3}(a_{1},a_{2},2a_{3})$ , поскольку можно написать группу $S_{3}$ как $S_{3}=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}$ , используя циклическую запись для перестановок .
Если $b_{n}=2^{n(n-1)/2}$ количество графов , вершины которых являются заданными $n$ -множество точек, тогда $a_{n}$ количество связных графов , вершины которых являются заданными $n$ - набор точек.
Существует множество вариаций предыдущего примера, в которых граф обладает определенными свойствами: например, если $b_{n}$ считает графы без циклов, то $a_{n}$ считает деревья (связные графы без циклов).
Если $b_{n}$ считает ориентированные графы , чьи ребра (а не вершины) являются заданными $n$ набор точек, затем $a_{n}$ подсчитывает связные ориентированные графы с этим набором ребер.
В квантовой теории поля и статистической механике статистические суммы $Z$ или, в более общем смысле , корреляционные функции задаются формальной суммой по диаграммам Фейнмана . Показательная формула показывает, что $\ln(Z)$ может быть записана как сумма по связным диаграммам Фейнмана в терминах связанных корреляционных функций .