Priority Queue Sorting and Labeled Trees |
| |
Authors: | AM Hamel |
| |
Institution: | Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo Ontario, N2L 3C5, Canada, ahamel@wlu.ca, CA
|
| |
Abstract: | We construct a bijection between labeled trees and allowable pairs of permutations sorted by a priority queue. These are also the pairs of permutations that avoid the pattern pairs (12, 21) and (321, 132). Our bijection has the additional property that it maps leaves in the tree to descents in the output permutation in the allowable pair and, more generally, preserves the edge-deletion distribution of the tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|