public int numTrees(int n) {
double count = 1.0;
for (double i = 1.0; i <= n; i = i + 1.0)
count *= ((i + n) / i);
return (int) Math.round(count / (n+1));
}
Not just the next smaller but all the ones smaller in size. https://en.wikipedia.org/wiki/Recurrence_relation