# Catalan numbers, 4 lines Java solution

• 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));
``````

}

• this is very smart! it is O(n) instead of the n^2 solution that I get with DP. BTW, what leads you to think of it as a catalan number? It is usually encountered in dividing polygons.

• Thank you! I found the recurrence relation for this counting and noticed it was the same as the one for Catalan numbers.

• by recurrence relation, do you mean how a bigger n-sized is divided to the next smaller?

• Not just the next smaller but all the ones smaller in size. https://en.wikipedia.org/wiki/Recurrence_relation

• Since the result is `int`: `n` cannot be bigger than 19, so `long` instead of `double` would suffice:

``````long count = 1;
for (long i = 1; i <= n; i++) {
count = count * (i + n) / i;
}
return (int)(count / (n+1));``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.