Enumeration and Asymptotics on Restricted Growth Functions of Order 2

Abstract

本篇論⽂中，我們延伸限制成⾧函數到更高次，並找到二次限制成長函數和Ｂ型對稱分割的⼀對⼀對應關係。為了改善透過傳統⽅法得到的漸進結果，我們介紹⼀個類似⽜頓法的演算法。假設二次限制成長函數為均勻分佈，我們得到二次限制成長函數最大值的期望值和變異數的漸進公式。最後，我們驗證二次限制成⾧函數最大值的分佈收斂到常態分佈。

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.