Count number of ways to construct binary search tree with n elements

I had this question asked in an interview:


In how many ways, we can construct binary search tree from \$n\$ elements?

I have written this code, but got a feedback that it could be improved. How to do it?

def count_ways(n):
    c = [0] * (n+1)
    c[0] = 1
    c[1] = 1
    for i in xrange(2, n+1):
        sum_w = 0
        for j in xrange(0, i):
            sum_w += c[j] * c[i-j-1]
        c[i] = sum_w
    return c[n]    

print count_ways(4)

The number of trees can be expressed in the closed form \$\frac{\binom{2n}{n}}{n+1}\$, and due to \$\binom{2n}{n} = \frac{4n - 6}{n} \binom{2(n-1)}{n-1}\$ the result is computed in linear time.

I would not ask such question in face-to-face interview (unless the position requires in-depth knowledge of combinatoric and graph theory).

StackExchange Code Review Q#161516, answer score: 7