研究生: |
陳怡廷 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 |
論文種類: | 學術論文 |
相關次數: | 點閱:106 下載: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] 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.