Parking functions, allowable pairs, and a symmetry in trees
Louis Kalikow
Brandeis University
May 14,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

We explore the connections between parking
functions and two of other sets of objects.
First, we describe a bijection between parking functions and
allowable pairs of
permutations of a priority queue, which have
been studied by Atkinson. The bijection preserves breakpoints,
which are closely related to the idea of prime parking
functions.
We then provide an interpretation of the inversion enumerator
for labeled trees using
allowable pairs; Kreweras has previously interpreted the
inversion enumerator for parking functions.
We also obtain a generalization of the inversion
enumerator using allowable pairs.
Furthermore, we define
valet functions, a variant of parking functions, and demonstrate
a bijection between them and allowable pairs of permutations
of a multiset.
We next discuss a symmetry in trees and its connection to
parking functions. Gessel showed that the number of trees on
$\{0,1,2,\ldots, n\}$ with $i$ descents and $j+1$ leaves
equals the number of trees with $j$ descents and $i+1$
leaves. We provide a new proof of this by using
recursions obtained from decompositions of trees. The method
of proof leads to a generalization of a functional equation found
by Knuth concerning trees in which every vertex is either a leaf
or a descent. We use an
analogous decomposition to show a symmetry in parking
functions between descents and ``disfavored spaces'' of the
parking function.
The results in this talk are part of the doctoral thesis of the
presenter written under the direction of Professor Ira Gessel.

Speaker's Contact Info: kalikow(atsign)binah.cc.brandeis.edu
Return to seminar home page
Page loaded on April 26, 1999 at 06:14 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

