卡特兰数

Bertha 。 2023-10-09 23:29 47阅读 0赞

告诉你一个非常好用的方法，你学还是不学？

今天给大家分享的是在组合数学中用途非常广泛的数列，它的名字叫做**卡特兰数！！！**

下面有道力扣题，如果让你30秒给出答案，你觉得有没有可能？

![74bf55c760f04d888b2ffe32c8a10954.png][]

1 、2、3 ...、30好的，时间到，你是不是无从下手，果然不出我所料，因为你现在先有的知识还不能支持你秒给答案，但是你今天有幸刷到了我，我会交给你一个方法，只有碰到这种满足卡特兰数的simple题，我会让你在做题的过程中使你答题的速度锦上添花，我先给你结论，一会再给你一一证明结论的来源，请看结论：

![d3007d873a5d4682ab88dcfee470b09b.png][]

（Csdn的公式编译器我已经不想吐槽了，在MathType公式器中的公式也没办法复制粘贴在Csdn中，所以就粘贴在word文档中，截图给大家看了，希望谅解！！！）

好，回归主题，我们再看，想必大家都是每个高校的高材生，最基本的数学素养总是有的，这个组合公式想必大家了解，但是我还是要在这里说明（数学专业的我不用也会经常忘记！！嘿嘿）

![4476c74d66d44b24b0ced0d7c517c949.png][]

来，我们来到我们的上面那道题，将n的值直接带入（1）式，你算出的答案是不是就是正确答案呢？当n=3的时候，结果是不是5呢？请大声的告诉我！！! ,好，现在就为大家揭晓谜底，为什么这样就能算出正确答案？又有哪些题我们可以沿用这种技巧呢？

**卡特兰数**：

![77a1f69ca7c5477f897bfe9ed4c0afba.png][]

如果能把公式化成上面的这种形式的话，它就是卡特兰数

上面的公式经过几步简单的演算后化简后就能得到我们的公式（2），下面给大家介绍卡特兰数的推导过程（比较官方的推导过程）

假设有只蚂蚁要从（0,0）点爬向（n,n）点，每次向x轴或者向y轴正方向移动一个单位，但是不能到达之前不能越过第一象限的角平分线的移动方法总数

![b946ee761bb74573981f0c869e6795da.png][]

我们画一条不合法的路径（这里先不画了，电脑上不太好操作），然后把这条路沿着y=x+1对称过去，路径的终点变为（n-1,n+1）,所以所有不合法的路径都是唯一对应着一条到（n-1,n+1）的路径，所以我们总方法数是C(2n,n)，我们可以理解为在2n步里面选出n步进行向上移动，那么向下移动就是向右移动的步数，然后违规的方法数为C(2n,n-1),我们可以理解为在2n步里面选出n-1步进行向上移动，那么向下移动就是向右移动的步数,所以有效路径是不是就可以得到C(2n,n)-C(2n,n-1),然后我们将它进行通分化简得：

![f560d8c36d2148f585aca8755f85952c.jpeg][]

所以（1）式就是如此推导而来

来我们回归本题，起先我是直接向套入公式解决本题，但是java好像没有阶乘的方法，于是我自己写了一个

public long Cshilk(int m ,int n){
            long up=1;
            long down=1;
            long mid=1;
            int q=m-n;
            for (int i = 1; i<=m; i++) {
                up*=i;
            }
            for (int i = 1; i<=n; i++) {
                down*=i;
            }
            for ( q=1; q <=m-n; q++) {
                mid*=q;
            }
            return  (up/(down*mid));
        }

正当我测试成功的时候，但是提交的时候却出现了问题，找了半天终于找到了，原来是阶乘数太大，数值超过了int以及long的取值范围，然后我又想了一个方法，通过另外一个方法进行提交（换汤不换药）

public int numTrees(int n) {
         //先创建一个存储的数组
         int[] dp=new int[n+10];
         dp[0]=1;
         dp[1]=1;
            //节点可能存储的位置
            for (int i =2; i <=n; i++) {
                //左边节点可能存储的个数
                for (int j = 0; j<i; j++) {
                    //计算出当i时总共可能出现的情况
                    dp[i]+=dp[j]*dp[i-j-1];
                }
            }
         //总的可能情况
         return dp[n];
        }
    
    }

i的取值为（1，n）,i可以取这区间内的任何数，然后就是左子树和右子数的个数，假如左子树取j,是不是右子数的个数就是（n-j-1）（-1是为了减去根结点）,这里也是比较容易想的，假如你有3件衣服和三双鞋，那么它们的搭配是不是3\*3=9，这里也是如此，就是把左子树出现的各种情况个数和右子树可能出现的各种情况个数相乘相加就能得到总的类型个数。

这篇博客已经告一段落了，但是我对卡特兰数的了解远不如此，后期还会出更多有关组合数学这方面的讲解，学好数学也是一个码农基本的知识素养哦！！！

[74bf55c760f04d888b2ffe32c8a10954.png]: https://img-blog.csdnimg.cn/74bf55c760f04d888b2ffe32c8a10954.png
[d3007d873a5d4682ab88dcfee470b09b.png]: https://img-blog.csdnimg.cn/d3007d873a5d4682ab88dcfee470b09b.png
[4476c74d66d44b24b0ced0d7c517c949.png]: https://img-blog.csdnimg.cn/4476c74d66d44b24b0ced0d7c517c949.png
[77a1f69ca7c5477f897bfe9ed4c0afba.png]: https://img-blog.csdnimg.cn/77a1f69ca7c5477f897bfe9ed4c0afba.png
[b946ee761bb74573981f0c869e6795da.png]: https://img-blog.csdnimg.cn/b946ee761bb74573981f0c869e6795da.png
[f560d8c36d2148f585aca8755f85952c.jpeg]: https://img-blog.csdnimg.cn/f560d8c36d2148f585aca8755f85952c.jpeg