Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/25846
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Duarte, Rui | pt_PT |
dc.contributor.author | Guedes de Oliveira, António | pt_PT |
dc.date.accessioned | 2019-04-23T16:03:59Z | - |
dc.date.issued | 2019-06 | - |
dc.identifier.issn | 0196-8858 | pt_PT |
dc.identifier.uri | http://hdl.handle.net/10773/25846 | - |
dc.description.abstract | 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. | pt_PT |
dc.language.iso | eng | pt_PT |
dc.publisher | Elsevier | pt_PT |
dc.relation | UID/MAT/04106/2019 | pt_PT |
dc.relation | UID/MAT/00144/2019 | pt_PT |
dc.rights | openAccess | pt_PT |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | pt_PT |
dc.subject | Parking functions | pt_PT |
dc.subject | Shi arrangement | pt_PT |
dc.subject | Ish arrangement | pt_PT |
dc.title | The number of parking functions with center of a given length | pt_PT |
dc.type | article | pt_PT |
dc.description.version | published | pt_PT |
dc.peerreviewed | yes | pt_PT |
degois.publication.firstPage | 125 | pt_PT |
degois.publication.lastPage | 143 | pt_PT |
degois.publication.title | Advances in Applied Mathematics | pt_PT |
degois.publication.volume | 107 | pt_PT |
dc.date.embargo | 2020-06 | - |
dc.identifier.doi | 10.1016/j.aam.2019.02.004 | pt_PT |
dc.identifier.essn | 1090-2074 | pt_PT |
Appears in Collections: | CIDMA - Artigos AGG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Number_Parking_Functions_AAM.pdf | 406.9 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.