Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/25846
Título: | The number of parking functions with center of a given length |
Autor: | Duarte, Rui Guedes de Oliveira, António |
Palavras-chave: | Parking functions Shi arrangement Ish arrangement |
Data: | Jun-2019 |
Editora: | Elsevier |
Resumo: | Let 1≤r≤n and suppose that, when the Depth-first Search Algorithm is applied to a given rooted labeled 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 (defined by the authors in a previous article) of size r. A second bijection maps this set onto the set of parking functions with run r, a property that we introduce here. 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. We finally count the number of length n rook words with run r, which is the answer to our initial question. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/25846 |
DOI: | 10.1016/j.aam.2019.02.004 |
ISSN: | 0196-8858 |
Aparece nas coleções: | CIDMA - Artigos AGG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Number_Parking_Functions_AAM.pdf | 406.9 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.