BST permutations

[jason.s.turner]

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

 

[mlimber]

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

Off-topic
(http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.9). Try
comp.programming or similar.

Cheers! --M

 

[jason.s.turner]

Sorry...and thanks!

Jason

 

[Mark P]

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.