解析的組合せ論

解析的組合せ論は複素解析の手法を用いて列挙的組合せ論の問題を解き、特に生成関数の係数の漸近的推定値を求める。^{[ 1 ] [ 2 ] [ 3 ]}

歴史

列挙問題における解析的手法の最も初期の使用例の1つは、シュリニヴァーサ・ラマヌジャンとGHハーディによる整数分割に関する研究^{[ 4 ] [ 5 ]}に由来し、1918年に始まり、最初はタウバー定理、後に円周法が使用されました^{[ 6 ]}

ウォルター・ヘイマンの1956年の論文「スターリングの公式の一般化」は、鞍点法の最も初期の例の一つと考えられている。^{[ 7 ] [ 8 ] [ 9 ]}

1990年にフィリップ・フラジョレとアンドリュー・オドリツコは特異点解析の理論を開発した。^{[ 10 ]}

2009 年、フィリップ・フラジョレとロバート・セジウィックは、解析的組合せ論を彼らの観点と表記法で紹介した 『解析的組合せ論』という本を執筆しました。

多変数生成関数に関する最も初期の研究のいくつかは、確率的手法を用いて1970年代に始まりました。^{[ 11 ] [ 12 ]}

さらなる多変量解析技術の開発は2000年代初頭に始まった。^{[ 13 ]}

テクニック

有理型関数

が有理型関数であり、その極が原点に最も近く、位数がである場合、^{[ 14 ]} ${\displaystyle h(z)={\frac {f(z)}{g(z)}}}$ ${\displaystyle a}$ ${\displaystyle m}$

${\displaystyle [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 }$として ${\displaystyle n\to \infty }$

タウバー定理

もし

${\displaystyle f(z)\sim {\frac {1}{(1-z)^{\sigma }}}L({\frac {1}{1-z}})\quad }$として ${\displaystyle z\to 1}$

ここで、が緩やかに変化する関数であるとき、^{[ 15 ]} ${\displaystyle \sigma >0}$ ${\displaystyle L}$

${\displaystyle [z^{n}]f(z)\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)\quad }$として ${\displaystyle n\to \infty }$

ハーディ・リトルウッドのタウバー定理も参照してください。

サークルメソッド

対数や根を持つ関数を生成するため、分岐特異点を持つ関数を生成するため。^{[ 16 ]}

ダルブー法

関数 が で、収束半径がより大きい場合、およびの 1 付近でテイラー展開がである場合、^{[ 17 ]} ${\displaystyle (1-z)^{\beta }f(z)}$ ${\displaystyle \beta \notin \{0,1,2,\ldots \}}$ ${\displaystyle f(z)}$ ${\displaystyle 1}$ ${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j}}$

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

多重特異点を扱う同様の定理については Szegő (1975)を参照してください。

特異点解析

がで 特異点を持つ場合 ${\displaystyle f(z)}$ ${\displaystyle \zeta }$

${\displaystyle 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 }$として ${\displaystyle z\to \zeta }$

ここで 、^{[ 18 ]} ${\displaystyle \alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}}$

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

鞍点法

関数全体を含む関数を生成するため。^{[ 19 ] [ 20 ]}

直感的に、等高線積分への最大の寄与は鞍点付近にあり、鞍点付近を推定すると等高線全体の推定値が得られます。

が許容関数である場合、 ^{[ 21 ]}、^{[ 22 ] [ 23 ]} ${\displaystyle F(z)}$

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

どこ。 ${\displaystyle F^{'}(\zeta )=0}$

最急降下法も参照してください。

注釈

1. Melczer 2021、pp. vii and ix.
2. Pemantle and Wilson 2013、pp. xi
3. FlajoletとSedgewick 2009、p. ix。
4. メルツァー 2021、p. vii.
5. ペマントルとウィルソン、2013、62-63 ページ。
6. ペマントルとウィルソン、2013、62 ページ。
7. ペマントルとウィルソン、2013、63 ページ。
8. ウィルフ 2006年、197頁。
9. FlajoletとSedgewick 2009、607ページ。
10. FlajoletとSedgewick 2009、438ページ。
11. メルツァー 2021、13頁。
12. FlajoletとSedgewick 2009、650ページと717ページ。
13. メルツァー 2021、13-14頁。
14. セジウィック4、59ページ
15. Flajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. 私はFlajoletとSedgewickが述べた形式を使用しています。
16. ペマントルとウィルソン、2013、55-56 ページ。
17. ウィルフ 2006年、194頁。
18. FlajoletとSedgewick 2009、393ページ。
19. ウィルフ 2006年、196頁。
20. FlajoletとSedgewick 2009、542ページ。
21. Flajolet and Sedgewick 2009, pp. 565またはWilf 2006, pp. 199を参照。
22. FlajoletとSedgewick 2009、553ページ。
23. セジウィック8、25ページ。

参考文献

• フラジョレ、フィリップ、セジウィック、ロバート (2009).解析的組合せ論(PDF) . ケンブリッジ大学出版局
• ハーディ、GH（1949年）『ダイバージェント・シリーズ（第1版）』オックスフォード大学出版局。
• メルツァー、スティーブン (2021). 『解析的組合せ論への招待：一変数から多変数へ』（PDF） . Springer Texts & Monographs in Symbolic Computation.
• ペマントル、ロビン；ウィルソン、マーク・C. (2013). 『多変数解析的組合せ論』（PDF） . ケンブリッジ大学出版局.
• セジウィック、ロバート. 「4. 複素解析、有理関数および有理型漸近論」(PDF) . 2023年11月4日閲覧。
• セジウィック、ロバート. 「8. 鞍点漸近論」(PDF) . 2023年11月4日閲覧。
• Szegő, Gabor (1975).直交多項式（第4版）. アメリカ数学会.
• ウィルフ、ハーバート・S. (2006).ジェネレーティングファンクションロジー(PDF) (第3版). AKピーターズ社

2023年11月4日現在、この記事の全部または一部はWikibooksから引用されています。著作権者は、CC BY-SA 3.0およびGFDLの下での再利用を許可する形でコンテンツをライセンスしています。関連するすべての規約を遵守する必要があります。

さらに詳しい情報

• デ・ブライジン、NG (1981)。分析における漸近的手法。ドーバー出版。
• フラジョレ, フィリップ; オドリツコ, アンドリュー (1990). 「生成関数の特異点解析」(PDF) . SIAM Journal on Discrete Mathematics . 1990 (3).
• ミシュナ、マルニ (2020). 『解析的組合せ論：多次元アプローチ』 . Taylor & Francis Group, LLC.
• ペマントル, ロビン; ウィルソン, マーク C.; メルツァー, スティーブン (2024). 『多変数解析的組合せ論』（PDF）（第2版）. ケンブリッジ大学出版局.
• セジウィック、ロバート. 「6. 特異点分析」(PDF) .
• Wong, R. (2001).積分の漸近近似. 応用数学協会.

外部リンク

• 解析的組合せ論オンラインコース
• アルゴリズム解析入門オンラインコース
• 多変数解析的組合せ論プロジェクト
• 解析的組合せ論への招待

参照

• 記号的方法（組合せ論）
• 解析的組合せ論（書籍）

「 https://en.wikipedia.org/w/index.php?title=Analytic_combinatorics&oldid=1323552219」から取得