(E-Mail Removed) wrote:

> I have spent hours on this problem and cannot get it, any help would be

> appreciated:

>

> A binary search tree using n distinct integers 1, 2, ..., n. There

> are n! possible initial orderings of the n numbers. How many of the n!

> permutations will result in a perfectly balanced binary search tree?

> Assume that n =2^k -1 for some positive integer k.

>

> I was given a hint: 1 node = 1 permutation, 3 nodes = 2 permutations,

> 7 nodes = 80 permuations.

>

> Thanks,

>

> Jason

>
What does this mean? How do you map a permutation of the integers onto

a BST? There is only one balanced binary search tree for these n numbers.