The number of parking functions with center of a given length

• Tipo: Artigo em Revista Científica Internacional
• Data: 2019

Autores

Duarte, R (Autor) Outra; António Guedes de Oliveira (Autor) FCUP; Rui Duarte (Autor) Outra

Revista

Título: Advances in Applied Mathematics

Vol. 107

Páginas: 125-143

ISSN: 0196-8858

Editora: Elsevier

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Classificação Científica

CORDIS: Ciências Físicas > Matemática

FOS: Ciências exactas e naturais > Matemática

Outras Informações

ID Authenticus: P-00Q-AVB

DOI: 10.1016/j.aam.2019.02.004

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19