簡易檢索 / 詳目顯示

回結果列表
研究生： 盧彥霖
論文名稱： 隨機樹於節點的漸進估計問題
Asymptotic Enumeration Problem on Nodes in Random Trees
指導教授： 林延輯
學位類別： 碩士
Master
系所名稱： 數學系
Department of Mathematics
論文出版年： 2013
畢業學年度： 101
語文別： 英文
論文頁數： 22
中文關鍵詞： 有根且節點無編號之樹 、生成函數 、漸近公式 、奇異點 、收斂半徑
英文關鍵詞： Rooted unlabelled tree, Generating function, Asymptotic formula, Singularity, Radius of convergence
論文種類： 學術論文
相關次數： 點閱：98  下載：8 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本篇論文旨於探討由顯函數及隱函數所生成之生成函數，也找出其第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.

    1 Introduction . . . . . . . . . . . . . . . . . . . . . . 1 2 Explicit function . . . . . . . . . . . . . . . . . . . 1 2.1 Pole . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Branched point . . . . . . . . . . . . . . . . . . . . 3 2.3 Further approximation: higher-order terms .. . . . . . 5 3 Implicit function . . . . . . . . . . . . . . . . . . . 8 4 Enumeration Problem on Nodes in Random Trees . . . . . 11 4.1 Detailed discussion. . . . . . . . . . . . . . . . . 14 4.2 The case m = ∞ . . . . . . . . . . . . . . . . . . . 18 4.3 The case m = 4 . . . . . . . . . . . . . . . . . . . 20 Reference . . . . . . . . . . . . . . . . . . . . . . . 21

    [1] Herbert S. Wilf, generatingfunctionology, 169–181.
    [2] Philippr Flajolet and Robert Sedgewick, Analytic Combinatorics, 402–
    406.
    [3] Frank Harary and Edgar M.Palmer, Graphical Enumeration, 208–214.
    [4] A.Meir and J.W.Moon, On the Altitude of Nodes in Random Trees, Canad.
    J. Math. 30(1978), 997–1015.
    [5] Richard Otter, The Number of Trees, Annals of Mathematics, Second
    Series, Vol. 49, No. 3, Jul. (1948) 583–599.
    [6] Cayley, The collected mathematical papers of Arthur Cayley, V.3, 242;
    V.9, 202, 427; V.11, 365; V.13, 26.
    [7] Henze and Blair, The number of isomeric hydrocarbons of the methane
    series, J. Am. Chem. Soc. Volume 53 (1931), 3077–3085.
    [8] Steven R. Finch, Mathemical Constants, 295–301.
    [9] Carlos A. Berenstein and Roger Gay, Complex Variables An Introduction,
    499–505.
    [10] Martin Aigner, A Course in Enumeration.
    [11] James Ward Brown and Ruel V. Churchill, Complex Variables and Appli-
    cations.
    [12] Jerrold E. Marsden and Michael J. Hoffman, Basic Complex Analysis.
    [13] The On-Line Encyclopedia of Integer Sequences, A000081, A000598.

    QR CODE