Q:

Count number of unique node sequences producing the same BST

The problem:

Given a particular sequence of up to 50 integers, which represent
  nodes of a certain binary search tree (BST), how many permutations of
  this sequence are there, which will also give rise to exactly the same
  BST? Include the original sequence in your total count as 1 sequence.
For instance, answer = 6 for such a sequence [5,2,1,9,8]: [5,2,1,9,8]
  (itself, the original sequence given), [5,9,8,2,1], [5,2,9,1,8],
  [5,9,2,1,8], [5,2,9,8,1], [5,9,2,8,1]

A:

Suppose you have your example sequence [5,2,1,9,8].  The first node will become the root of the binary tree, so we know the first node must be 5.
From then on, all the nodes smaller than 5 will go to the left child, and all the nodes greater than 5 will go to the right child.
So you can solve this recursively, count the number of ways of making the left subtree (consisting of [2,1]) multiply by the number of ways of making the right subtree (consisting of [9,8]) and multiply by the number of ways of ordering the arrival of integers on opposite sides.
Sample code
def nCr(n,r):
   """Return number of ways of choosing r objects from n"""

   top, bottom = 1, 1
   for i in xrange(r):
      top *= n
      n = n - 1
      bottom *= r
      r = r- 1
   return top / bottom

def count_ways_to_make_bst(seq):
    if len(seq)<=1:
        return 1
    num_remaining = len(seq) - 1
    left = [r for r in seq[1:] if r>seq[0]]
    right = [r for r in seq[1:] if r<seq[0]]
    return count_ways_to_make_bst(left) * count_ways_to_make_bst(right) * nCr(num_remaining,len(left))

