The problem of ranking a finite set X may be defined as follows: if $|X| = N$, define a linear order on X and find the order isomorphism $\varphi :X \to \{ 0,1, \cdots ,N - 1\} $, and its inverse $\varphi ^{ - 1} $. In this paper, X is the set of k-ary trees on n vertices, $k \geqq 2$, $n \geqq 0$; the linear order is the lexicographic order on a set of permutations used to represent the trees. The representation of k-ary trees by permutations leads to efficient computation of $\varphi $ and $\varphi ^{ - 1} $. One result of this investigation is a generalization of binomial coefficients. The problem of listing all k-ary trees on n vertices is also addressed; an algorithm which, excluding input-output, is linear in the number of such trees is presented.

We present an algorithm which finds a maximum independent set in an n-vertex graph in $O(2^{n/3})$ time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.