卡特兰公式的应用

/*

假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如n=1时，()是合法的，但是)(为不合法。

给定一个整数n，请返回所求的合法排列数。保证结果在int范围内。

*/

public class Parenthesis {     /*     使用卡特兰公式：（2*n）!除以n！*n!，再除以（n+1）     注意数的范围，和该公式可以抵消一些数     */     public int countLegalWays(int n) {        int s1=factorial(2*n,n);        int s2=factorial(n,1);         int stemp=s2*(n+1);         int result=0;        if(s1%stemp==0){            result=s1/stemp;        }else{            result=s1/stemp;            result+=1;        }         return result;              }     //求阶乘n的阶乘     public int factorial(int n,int m){         int result=1;         for(int i=n;i>m;i--){             result*=i;         }         return result;     } }