关于括号式子的计数,该怎么解决

关于括号式子的计数
如果有n对括号，组成一个式子，而且括号的最深嵌套层次为k
满足这个条件的式子一共有几种？
如果n=3，k=2则有3种:
(())()
()(())
(()())

能否找到递推公式？

[解决办法]
没问题，上面的公式应该可以
[解决办法]
我的写错了 却发现这里不能编辑帖子，郁闷
[解决办法]
一个新的版本，不太好验证数据：

对于特定的 n,k;
深度为k的子式子最少有k个括号，最多有n个括号

对由i（i>=k and i<=n)个括号组成的深度为k的式子可以由dp数组得到；
其他的n-i个括号分布在深度为k的子式子的前后；

为了不重复统计，规定上面深度为k的子式子是 大式子中的第一个深度为k的子式子；

分别对前面有j(j>=0,j<=n-i,并且这k个括号组成的式子的最大深度不能大于k-1，也就是最大深度从1到k-1的总数的和)个括号，后面有n-i-j（并且这n-i-j个括号组成的式子的最大深度不能大于k）个括号的情况统计；


#include <stdio.h>

#define MAX_N 20

int dp[MAX_N+1][MAX_N+1];

void fun(int n,int k)
{
int i,j;
for (i=k;i<n;++i)
{
int tmp=0;

for (j=0;j<=n-i;++j)
{
 int tmp_i=j;
int tmp_j=n-i-j;
int tmp_k1=0,tmp_k2=0;
if (tmp_i>k-1) tmp_i=k-1;
if (tmp_j>k) tmp_j=k;

for (;tmp_i>0 ; tmp_i--)
{
tmp_k1+=dp[j][tmp_i];
}
for (;tmp_j>0 ; tmp_j--)
{
tmp_k2+=dp[n-i-j][tmp_j] ;
}

if (tmp_k1<1) tmp_k1=1;
if (tmp_k2<1) tmp_k2=1;

tmp+=tmp_k1*tmp_k2;

}
dp[n][k]+=dp[i-1][k-1]*tmp;
}
dp[n][k]+=dp[n-1][k-1];
}

int main(int argc, char* argv[])
{

//最深嵌套层次为k,那么肯定存在一个层次为k-1的式子，其外围再有一对括号；
//这对括号外再没有嵌套的括号；
int n,k;

for (n=1; n<=MAX_N; n++)
{
dp[n][1]=1;
dp[n][n]=1;
}

for (n=1; n<=MAX_N; n++)
{
for (k=1; k<=n; k++)
{
if (k!=n && k!=1) fun(n,k);

printf("n:%3d k:%3d dp:%10d\n",n,k,dp[n][k]);
}
}

fun(20,2);

printf("input n{max:%d} and k{max:%d}:",MAX_N,MAX_N);
while (scanf("%d %d",&n,&k)==2)
{
printf("%d %d : %d \n" ,n,k,dp[n][k]);
printf("input n{max:%d} and k{max:%d}:",MAX_N,MAX_N);
}

return 0;
}