RECURRENCE RELATIONS ON HEAPS

We examine three quantities related to heaps: the number of heaps with n nodes, the number of permutations generating the same heap, and the average number of exchange operations necessary for generating a heap from a given permutation. We find recurrence relations for these quan tities, and are thus able to compute them in time O(ln n). We also obt ain the asymptotic values for n = 2(r) - 1. We determine an upper and a lower bound for the number of exchange operations involved (a well-k nown quantity in computer science), and study its behavior when n rang es between two consecutive powers of 2.