Penn Arts & Sciences Logo

Probability and Combinatorics

Thursday, September 16, 2004 - 4:30pm

Jeff Remmel

UC San Diego

Location

University of Pennsylvania

DRL 3C4

In this talk, we will describe some recent algorithms due to Remmel and Williamson to rank and unrank certain degree-restricted classes of Cayley trees. Specifically, we consider classes of trees that (i) have a given set of leaves, (ii) have a fixed number k of leaves, (iii) have a given degree sequence or (iv) have a given multiset of degrees. Using special properties of a bijection due to Eugeciouglu and Remmel, we show that one can reduce the problem of ranking and unranking these restricted classes of trees to corresponding problems of ranking and unranking certain classes of set partitions. We can then use known techniques to rank and unrank the various classes of set partitions that arise in each case. Since the ranks involved in each our cases are of the order of n!,it takes O(nlog(n)) bits just to write down the largest ranks. Our ranking and unranking algorithms are as efficient as can be expected in that they require at most O(n^2) comparisons of numbers y \leq n plus O(n) operations of multiplication, division, addition, substraction and comparision of numbers of length at most O(nlog(n)). Hence, in each case, our ranking and unranking algorithms require at most O(n^2log(n)) bit operations.