簡易檢索 / 詳目顯示
| 研究生： |
陳怡廷 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 |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：122 下載：48 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本篇論⽂中，我們延伸限制成⾧函數到更高次，並找到二次限制成長函數和Ｂ型對稱分割的⼀對⼀對應關係。為了改善透過傳統⽅法得到的漸進結果，我們介紹⼀個類似⽜頓法的演算法。假設二次限制成長函數為均勻分佈，我們得到二次限制成長函數最大值的期望值和變異數的漸進公式。最後，我們驗證二次限制成⾧函數最大值的分佈收斂到常態分佈。
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.
