46.搜狐:四对括号可以有多少种匹配排列方式

时间:2021-06-02 19:27:42

四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())



HANDWRITING:

之前左括号的数量必须比右括号多,即卡特兰数

令h(0)=1,h(1)=1,catalan数满足递推式

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

h(n)=C(2n,n)/(n+1)