Geodesic
Parking functions, empirical processes, and the width of rooted labeled trees
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

This paper provides tight bounds for the moments of the width of rooted labeled trees with $n$ nodes, answering an open question of Odlyzko and Wilf (1987). To this aim, we use one of the many one-to-one correspondences between trees and parking functions, and also a precise coupling between parking functions and the empirical processes of mathematical statistics. Our result turns out to be a consequence of the strong convergence of empirical processes to the Brownian bridge (Komlós, Major and Tusnády, 1975).
DOI : 10.37236/1558
Classification : 05C05, 60J65, 60J80
Mots-clés : moment, Brownian excursion, empirical processes, hashing with linear probing, parking, width, rooted labelled tree 
@article{10_37236_1558,
     author = {Philippe Chassaing and Jean-Fran\c{c}ois Marckert},
     title = {Parking functions, empirical processes, and the width of rooted labeled trees},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1558},
     zbl = {0974.05025},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1558/}
}
TY  - JOUR
AU  - Philippe Chassaing
AU  - Jean-François Marckert
TI  - Parking functions, empirical processes, and the width of rooted labeled trees
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1558/
DO  - 10.37236/1558
ID  - 10_37236_1558
ER  - 
%0 Journal Article
%A Philippe Chassaing
%A Jean-François Marckert
%T Parking functions, empirical processes, and the width of rooted labeled trees
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1558/
%R 10.37236/1558
%F 10_37236_1558
Philippe Chassaing; Jean-François Marckert. Parking functions, empirical processes, and the width of rooted labeled trees. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1558

Cité par Sources :