# How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would have same structure. for example for n=3; we have:

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

In this 2,1,3 and 2,3,1 produce same BST. So for 3 answer is 2.

I have figured out that if I take 3 numbers, and the root is less than one number and greater than other, then the sequence produced is same. ie. for n=9

2,1,3, 5,4,6 8,7,9 and 2,3,1 5,6,4 8,9,7 produce same BST.

• Can you deduce your answer from the number of possible BSTs on $n$ elements? – Yuval Filmus Dec 31 '17 at 15:24
• Is it somehow related to Catalan number? – Rajeev Pandey Dec 31 '17 at 15:30
• This is very likely. – Yuval Filmus Dec 31 '17 at 17:17
• Why is your answer 2 (for n=3)? In that case you have five possible binary trees and six permutations? Are you looking for the trees that have a unique permutation? – Hendrik Jan Jan 1 '18 at 13:45
• No I'm looking for trees that have same structure. 2,1,3 and 3,1,2 have same structure – Rajeev Pandey Jan 1 '18 at 14:42