The number of parking functions with center of a given length
 
 
Description:  Let 1\leq r\leq n and suppose that, when the Depth-first Search Algorithm is applied to a given rooted labelled tree on n+1 vertices, exactly r vertices are visited before backtracking. Let R be the set of trees with this property. We count the number of elements of R.

For this purpose, we first consider a bijection, due to Perkinson, Yang and Yu, that maps R onto the set of parking function with center of size r. A second bijection maps this set onto the set of parking functions with run r. We then prove that the number of length n parking functions with a given run is the number of length n rook words (defined by Leven, Rhoades and Wilson) with the same run. This is done by counting related lattice paths in a ladder-shaped region. Finally, we count the number of length n rook words with run r, which is the answer to our initial question.

This is joint work with António Guedes de Oliveira.

Date:  2017-11-29
Start Time:   15:00
Speaker:  Rui Duarte (Univ. Aveiro)
Institution:  Universidade de Aveiro
Place:  Room 5.5, Department of Mathematics, U.C.
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support