The answer should (a) n-k+1
Try to Solve T(n)=∑ T(k−1)T(n-k+1):
T(0) = 0 (no of BST with zero node)
T(1) = 1 (no of BST with one nodes)
T(2) = 2 (no of BST with two nodes)
T(3) = 5 (no of BST with three nodes)
T(4) = 14 (no of BST with four nodes)
now verify using both options (a) and (b)
Option(a) : T(n)=∑ T(k−1)T(n-k+1):
T(4) = T(0)T(4) + T(1)T(3) + T(2)T(2) + T(3)T(1)
= 0 + 5 + 4 + 5
= 14
which is correct.
now trying the option that is mentioned everywhere
option (b) T(n)=∑ T(k−1)T(n-k):
T(4) = T(0)T(3) + T(1)T(2) + T(2)T(1) + T(3)T(0)
= 0 + 2 + 2 + 0
= 4
which is wrong as no. of BST which 4 distinct keys = 14
So option (a) should be the answer.