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

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

Заявление [ править ]

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

${\ displaystyle f (x) = a_ {1} x + {a_ {2} \ over 2} x ^ {2} + {a_ {3} \ over 6} x ^ {3} + \ cdots + {a_ {n } \ над n!} x ^ {n} + \ cdots \,}$

у нас есть

${\ Displaystyle \ ехр е (х) = е ^ {е (х)} = \ сумма _ {n = 0} ^ {\ infty} {b_ {n} \ над n!} x ^ {n}, \, }$

куда

${\ displaystyle b_ {n} = \ sum _ {\ pi = \ left \ {\, S_ {1}, \, \ dots, \, S_ {k} \, \ right \}} a _ {\ left | S_ {1} \ right |} \ cdots a _ {\ left | S_ {k} \ right |},}$

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

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

${\ displaystyle b_ {n} = B_ {n} (a_ {1}, a_ {2}, \ dots, a_ {n}),}$

и поэтому

${\displaystyle \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 ₁ , ..., a _n ) - n- й полный полином Белла .

Примеры [ править ]

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

Приложения [ править ]

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

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

Ссылки [ править ]

• Стэнли, Ричард П. (1999), Перечислительная комбинаторика. Vol. 2 , Кембриджские исследования в области высшей математики, 62 , Cambridge University Press , ISBN 978-0-521-56069-6, MR  1676282 , ISBN 978-0-521-78987-5  Глава 5