Аналитическая комбинаторика

Не путать с аналитической комбинаторикой (книга) или символическим методом (комбинаторика) .

Аналитическая комбинаторика использует методы комплексного анализа для решения задач перечислительной комбинаторики , в частности для нахождения асимптотических оценок коэффициентов производящих функций .

История

Одно из первых применений аналитических методов для решения задач перечисления пришло из Шринивасы Рамануджана и Г.Х. Харди работы о целочисленных разделах . начиная с 1918 года, сначала используя тауберову теорему, а затем метод круга .

Статья Уолтера Хеймана 1956 года «Обобщение формулы Стирлинга» считается одним из самых ранних примеров метода перевала.

В 1990 году Филипп Флажоле и Эндрю Одлизко разработали теорию анализа особенностей.

В 2009 году Филипп Флажоле и Роберт Седжвик написали книгу «Аналитическая комбинаторика» .

Некоторые из самых ранних работ по многомерным производящим функциям начались в 1970-х годах с использованием вероятностных методов.

Разработка дальнейших многомерных методов началась в начале 2000-х годов.

Техники

Мероморфные функции

Если $h(z)={\frac {f(z)}{g(z)}}$ является мероморфной функцией и $a$ является ли его полюс ближайшим к началу координат с порядком $m$, затем

$[z^{n}]h(z)\sim {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}\quad$ как $n\to \infty$

Тауберова теорема

Если

$f(z)\sim {\frac {1}{(1-z)^{\sigma }}}L({\frac {1}{1-z}})\quad$ как $z\to 1$

где $\sigma >0$ и $L$ — медленно меняющаяся функция , то

$[z^{n}]f(z)\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)\quad$ как $n\to \infty$

См. также тауберову теорему Харди–Литтлвуда .

Метод круга

Для создания функций с логарифмами или корнями , имеющими особенности ветвей .

Метод Дарбу

Если у нас есть функция $(1-z)^{\beta }f(z)$ где $\beta \notin \{0,1,2,\ldots \}$ и $f(z)$ имеет радиус сходимости больше, чем $1$ и расширение Тейлора около 1 из $\sum _{j\geq 0}f_{j}(1-z)^{j}$, затем

$[z^{n}](1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}+O(n^{-m-\beta -2})$

См. Сегё (1975) для получения аналогичной теоремы, касающейся множественных особенностей.

Анализ особенностей

Если $f(z)$ имеет особенность в $\zeta$ и

$f(z)\sim \left(1-{\frac {z}{\zeta }}\right)^{\alpha }\left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)^{\gamma }\left({\frac {1}{\frac {z}{\zeta }}}\log \left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)\right)^{\delta }\quad$ как $z\to \zeta$

где $\alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}$ затем

$[z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad$ как $n\to \infty$

Метод седловой точки

Для генерации функций, в том числе целых , не имеющих особенностей.

Интуитивно понятно, что наибольший вклад в контурный интеграл приходится на область седла , и оценка вблизи седла дает нам оценку для всего контура.

Если $F(z)$ – допустимая функция, затем

$[z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}\quad$ как $n\to \infty$

где $F^{'}(\zeta )=0$.

См. также метод наискорейшего спуска .

Ссылки

• Флажоле, Филипп; Седжвик, Роберт (2009). Аналитическая комбинаторика (PDF) . Издательство Кембриджского университета.
• Харди, GH (1949). Дивергентная серия (1-е изд.). Издательство Оксфордского университета.
• Мельцер, Стивен (2021). Приглашение к аналитической комбинаторике: от одной к нескольким переменным (PDF) . Тексты и монографии Springer по символьным вычислениям.
• Пемантл, Робин; Уилсон, Марк К. (2013). Аналитическая комбинаторика с несколькими переменными (PDF) . Издательство Кембриджского университета.
• Седжвик, Роберт. «4. Комплексный анализ, рациональная и мероморфная асимптотика» (PDF) . Проверено 4 ноября 2023 г.
• Седжвик, Роберт. «8. Асимптотика седловой точки» (PDF) . Проверено 4 ноября 2023 г.
• Сегё, Габор (1975). Ортогональные полиномы (4-е изд.). Американское математическое общество.
• Уилф, Герберт С. (2006). Генерирующая функционалология (PDF) (3-е изд.). АК Питерс, ООО

По состоянию на 4 ноября 2023 г. эта статья полностью или частично взята из Wikibooks . Владелец авторских прав лицензировал контент таким образом, чтобы его можно было повторно использовать в соответствии с CC BY-SA 3.0 и GFDL . Все соответствующие условия должны быть соблюдены.

Дальнейшее чтение

• Де Брейн, Н.Г. (1981). Асимптотические методы анализа . Дуврские публикации.
• Флажоле, Филипп; Одлыжко, Андрей (1990). «Анализ особенностей производящих функций» (PDF) . SIAM Journal по дискретной математике . 1990 (3).
• Мишна, Марни (2020). Аналитическая комбинаторика: многомерный подход . Тейлор и Фрэнсис Групп, ООО.
• Пемантл, Робин; Уилсон, Марк С.; Мельцер, Стивен (2024). Аналитическая комбинаторика с несколькими переменными (PDF) (2-е изд.). Издательство Кембриджского университета.
• Седжвик, Роберт. «6. Анализ особенностей» (PDF) .

Внешние ссылки

• Онлайн-курс «Аналитическая комбинаторика»
• Онлайн-курс «Введение в анализ алгоритмов»
• Аналитическая комбинаторика в проектах с несколькими переменными
• Приглашение к аналитической комбинаторике

См. также

• Символьный метод (комбинаторика)
• Аналитическая комбинаторика (книга)