隨機樹於節點的漸進估計問題
Abstract
本篇論文旨於探討由顯函數及隱函數所生成之生成函數，也找出其第n項係數之漸進行為。大體來說，方法為找出其冪級數的領導奇異點，之後使用相對應的定理來得出第n項係數。最後，本篇論文討論隨機樹(除根節點外每個頂點之分支數為m)於各個節點的行為是有界的。我們檢查當m=4的情況，並確定出其生成函數的收斂半徑約為0.355158。
This paper aims to explore generating functions which are defined by explicit functions and implicit functions, as well as to find out the asymptotic behavior of its coefficients. Roughly speaking, the method is to identify the dominating singularity power series, then to use related theories to obtain the coefficient of z^n. Finally, this paper discusses the behavior of the numbers of nodes in a random tree when the ramification number m of each vertex is bounded. We examine the case m=4 carefully and verify the radius of converegence of the generating function is 0.355158.
This paper aims to explore generating functions which are defined by explicit functions and implicit functions, as well as to find out the asymptotic behavior of its coefficients. Roughly speaking, the method is to identify the dominating singularity power series, then to use related theories to obtain the coefficient of z^n. Finally, this paper discusses the behavior of the numbers of nodes in a random tree when the ramification number m of each vertex is bounded. We examine the case m=4 carefully and verify the radius of converegence of the generating function is 0.355158.
Description
Keywords
有根且節點無編號之樹, 生成函數, 漸近公式, 奇異點, 收斂半徑, Rooted unlabelled tree, Generating function, Asymptotic formula, Singularity, Radius of convergence