Find number of permutations of a given sequence of integers which yield the same binary search tree

Thanks for the explanation antti.huima! This helped me understand. Here is some C++:

#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}

You could do this backwards: Given a BST, enumerate all the arrays of integers which could yield this BST...

Couldn't you (using nondeterminism...)

1. emit root and add it to the emitted set.
2. nondeterministically choose an item from the tree which is not in the emitted set, but whose parent is, and add it to the emitted set and emit it.
3. repeat 2 until all emitted.

The nondeterminism will give you all such arrays. Then you can count them.