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

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

• 1 Утверждение
• 2 Примеры
• 3 Приложения
• 4 Ссылки

Для любого формального степенного ряда вида

$f\; (x)\; =\; a\; 1\; x\; +\; a\; 2\; 2\; x\; 2\; +\; a\; 3\; 6\; x\; 3\; +\; \cdots \; +\; ann!\; xn\; +\; \cdots \; \{\backslash \; displaystyle\; f\; (x)\; =\; a\_\; \{1\}\; x\; +\; \{a\_\; \{2\}\; \backslash \; over\; 2\}\; x\; ^\; \{2\}\; +\; \{a\_\; \{3\}\; \backslash \; over\; 6\}\; x\; ^\; \{3\}\; +\; \backslash \; cdots\; +\; \{\; a\_\; \{n\}\; \backslash \; over\; n!\}\; x\; ^\; \{n\}\; +\; \backslash \; cdots\; \backslash ,\}$

имеем

$exp\; \; f\; (x)\; =\; ef\; (x)\; =\; \sum \; n\; =\; 0\; \infty \; bnn!\; хn,\; \{\backslash \; Displaystyle\; \backslash \; ехр\; е\; (х)\; =\; е\; ^\; \{е\; (х)\}\; =\; \backslash \; сумма\; \_\; \{п\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{b\_\; \{n\}\; \backslash \; над\; п!\}\; х\; ^\; \{п\},\; \backslash ,\}$

где

$bn\; =\; \sum \; \pi \; =\; \{S\; 1,\dots ,\; S\; k\}\; a\; |\; S\; 1\; |\; \cdots \; a\; |\; S\; k\; |,\; \{\backslash \; displaystyle\; b\_\; \{n\}\; =\; \backslash \; sum\; \_\; \{\backslash \; pi\; =\; \backslash \; left\; \backslash \; \{\backslash ,\; S\_\; \{1\},\; \backslash ,\; \backslash \; dots,\; \backslash ,\; S\_\; \{k\}\; \backslash ,\; \backslash \; right\; \backslash \}\}\; a\; \_\; \{\backslash \; left\; |\; S\_\; \{1\}\; \backslash \; right\; |\}\; \backslash \; cdots\; a\; \_\; \{\backslash \; left\; |\; S\_\; \{k\}\; \backslash \; right\; |\},\}$

и индекс π пробегает список всех разделов {S 1,..., S k } набора {1,..., n}. (Когда k = 0, произведение пусто и по определению равно 1.)

Формулу можно записать в следующем виде:

$bn\; =\; B\; n\; (a\; 1,\; a\; 2,\dots ,\; an),\; \{\backslash \; displaystyle\; b\_\; \{n\}\; =\; B\_\; \{n\}\; (a\_\; \{1\},\; a\_\; \{2\},\; \backslash \; dots,\; a\_\; \{n\}),\}$

и, следовательно,

$exp\; \; (\sum \; n\; =\; 1\; \infty \; ann!\; Xn)\; =\; \sum \; n\; =\; 0\; \infty \; B\; n\; (a\; 1,\dots ,\; an)\; n!\; xn,\; \{\backslash \; displaystyle\; \backslash \; exp\; \backslash \; left\; (\backslash \; sum\; \_\; \{n\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{a\_\; \{n\}\; \backslash \; over\; n!\}\; x\; ^\; \{n\}\; \backslash \; right)\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{B\_\; \{n\}\; (a\_\; \{1\},\; \backslash \; dots,\; a\_\; \{n\})\; \backslash \; over\; n!\}\; x\; ^\; \{n\},\}$

где B n(a1,..., a n) - n-й полный многочлен Белла.

• $b\; 3\; =\; B\; 3\; (a\; 1,\; a\; 2,\; a\; 3)\; =\; a\; 3\; +\; 3\; a\; 2\; a\; 1\; +\; a\; 1\; 3,\; \{\backslash \; displaystyle\; 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.
• Если b n = 2 - это количество графов, вершины которых представляют собой заданное n-точечное множество, тогда a n - это количество связанных графов, вершины которых являются данным множеством из n точек.
• Существует множество вариантов предыдущего примера, в которых граф имеет определенные свойства: например, если b n считает графы без циклов, то a n подсчитывает деревья (связные графы без циклов).
• Если b n подсчитывает ориентированные графы, чьи ребра (а не вершины) являются заданным набором n точек, то a n подсчитывает связанные ориентированные графы с этим ребром s

В приложениях числа a n часто подсчитывают количество неких «связанных» структур на набор из n точек, а числа b n подсчитывают количество (возможно, отключенных) структур. Числа b n / n! подсчитайте количество классов изоморфизма структур в n точках, причем каждая структура будет взвешена обратной величиной своей группы автоморфизмов, и числа a n / n! таким же образом подсчитываем классы изоморфизма связных структур.

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

• Stanley, Richard P. (1999), Перечислительная комбинаторика. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, ISBN 978-0-521-56069-6, MR 1676282, ISBN 978-0-521-78987-5 Глава 5