Parking functions, empirical processes, and the width of rooted labeled trees (Q5928528): Difference between revisions

The width \(W_n\) of a rooted labelled tree \(T\) with \(n+1\) nodes is the maximum over \(k\) of the number of nodes at distance \(k\) from the root of \(T\). The authors give tight bounds for the moments of \(W_n\) over the \((n+1)^n\) such trees, each tree being assumed equally likely. In particular, they show that \(E(W_n)- \sqrt{\pi n/2}= O(n^{1/4}\sqrt{\log n})\). This answers a question raised by \textit{A. M. Odlyzko} and \textit{H. S. Wilf} [J. Comb. Theory, Ser. B 42, 348-370 (1987; Zbl 0588.05015)].