簡易檢索 / 詳目顯示

研究生: 陳怡廷
Chen, Yi-Ting
論文名稱: Enumeration and Asymptotics on Restricted Growth Functions of Order 2
Enumeration and Asymptotics on Restricted Growth Functions of Order 2
指導教授: 林延輯
Lin, Yen-Chi
學位類別: 碩士
Master
系所名稱: 數學系
Department of Mathematics
論文出版年: 2015
畢業學年度: 103
語文別: 英文
論文頁數: 21
中文關鍵詞: 近似常態性Hayman admissible 函數機率分佈限制成⾧函數鞍點法
英文關鍵詞: asymptotic normality, Hayman admissible functions, probability distribution, restricted growth functions, saddle-point method
論文種類: 學術論文
相關次數: 點閱:123下載:48
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本篇論⽂中,我們延伸限制成⾧函數到更高次,並找到二次限制成長函數和B型對稱分割的⼀對⼀對應關係。為了改善透過傳統⽅法得到的漸進結果,我們介紹⼀個類似⽜頓法的演算法。假設二次限制成長函數為均勻分佈,我們得到二次限制成長函數最大值的期望值和變異數的漸進公式。最後,我們驗證二次限制成⾧函數最大值的分佈收斂到常態分佈。

    In this thesis, we extend the restricted growth functions to higher order and find a bijection between restricted growth functions of order 2 and symmetric partitions of type B. To improve the asymptotic results via traditional methods, we introduce an algorithm which is similar to Newton-Raphson method. Assuming that the restricted growth functions of order 2 are uniformly distributed, we obtain the asymptotic formulae for the expectation and variance of the maximum in a random restricted growth function of order 2. Finally, we verify that the distribution of maximum in restricted growth functions of order 2 will converge to a normal distribution.

    1 Introduction 1 2 Definition 4 3 The Asymptotic Estimation of the Number of Restricted Growth Functions of Order 2 6 4 The Asymptotic Estimation of the Expected Value and the Variance of Restricted Growth Functions of Order 2 11 5 The Asymptotic Normality of Restricted Growth Functions of Order 2 15 6 Conclusion and Future Work 19 References 20

    [1] E. A. Bender. Central and local limit theorems applied to asymptotic enumeration. J. Combinatorial Theory Ser. A, 15:91-111, 1973.
    [2] E. A. Bender and L. B. Richmond. Admissible functions and asymptotics for labelled structures by number of components. Electron. J. Combin.,3(1):Research Paper 34, approx. 23 pp. (electronic), 1996.
    [3] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the LambertW function. Adv. Comput. Math., 5(4):329-359,1996.
    [4] Samantha Dahlberg, Robert Dorward, Jonathan Gerhard, Thomas Grubb, Carlin Purcell, Lindsey Reppuhn, and Bruce E. Sagan. Set partition patterns and statistics, 2015.
    [5] N. G. de Bruijn. Asymptotic methods in analysis. Dover Publications,Inc., New York, third edition, 1981.
    [6] M. Drmota, B. Gittenberger, and T. Klausner. Extended admissible functions and gaussian limiting distributions. Math. Comp., 74(252):1953-1966, 2005.
    [7] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
    [8] Michael Fuchs and Helmut Prodinger. Words with a generalized restricted growth property. Indag. Math. (N.S.), 24(4):1024-1033, 2013.
    [9] L. H. Harper. Stirling behavior is asymptotically normal. Ann. Math. Statist., 38:410-414, 1967.
    [10] W. K. Hayman. A generalisation of Stirling's formula. J. Reine Angew. Math., 196:67-95, 1956.
    [11] T. Mansour. Combinatorics of set partitions. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2013.
    [12] S. Milne. Restricted growth functions and incidence relations of the lattice of partitions of an n-set. Advances in Math., 26(3):290-305, 1977.
    [13] A. M. Odlyzko. Asymptotic enumeration methods. In Handbook of combinatorics, Vol. 1, 2, pages 1063-1229. Elsevier, Amsterdam, 1995.
    [14] V. Reiner. Non-crossing partitions for classical re
    ection groups. Discrete Math., 177(1-3):195-222, 1997.
    [15] V. N. Sachkov. Probabilistic methods in combinatorial analysis, volume 56 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1997.
    [16] B. Salvy and J. Shackell. Symbolic asymptotics: Multiseries of inverse functions. J. Symbolic Computation, 27(6):543-563, 1999.
    [17] David G. L. Wang. On colored set partitions of type Bn. Cent. Eur. J. Math., 12(9):1372-1381, 2014.

    下載圖示
    QR CODE