Number of all BSTs on n distinct keys

(1/(n+1))×Binomial[2n,n]

(1/(n+1))×((Factorial[2n])/(Factorial[n]×Factorial[n]))

Plot[{(1/(n+1))×Factorial[2n]/(Factorial[n]Factorial[n])},{n,2,20}]

Plot[{(1/(n+1))×Factorial[2n]/(Factorial[n]Factorial[n]),(2^n)},{n,2,20}]

Plot[{(1/(n+1))×Factorial[2n]/(Factorial[n]Factorial[n]),(3^n)},{n,2,20}]

Plot[{(1/(n+1))×((Factorial[2n])/(Factorial[n]Factorial[n])),(4^n)((Gamma[n+(1/2)])/(Sqrt[π]×Gamma[n+2]))},{n,2,20}]

The running time of the recursive program that builds an optimal BST

(1/2) (-1+(3^n))

Together:

Plot[{(1/(n+1))×((Factorial[2n])/(Factorial[n]Factorial[n])),(1/2) (-1+(3^n))},{n,2,20}]

Fraction of the time per tree:

Plot[{((1/2) (-1+(3^n)))((1/(n+1))×((Factorial[2n])/(Factorial[n]Factorial[n])))},{n,2,20}]

Side calculations

Plot[{((Gamma[n+(1/2)])/(Gamma[n+2]))},{n,2,20}]

Plot[{((Gamma[n+2])/(Gamma[n+(1/2)]))},{n,2,200}]