原本觉得搞OI的时候组合计数还不算太弱,但现在已经完全不会了,,稍微补救一下
卡特兰数
组合意义:n个节点二叉树的形态个数(还有很多其他的形式)
通过递推式可以列出生成函数,然后解一个二次方程,用广义二项式定理展开一下,经过化简后得到\(H(n)=\frac{C^n_{2n}}{n+1}\)
原本觉得搞OI的时候组合计数还不算太弱,但现在已经完全不会了,,稍微补救一下
组合意义:n个节点二叉树的形态个数(还有很多其他的形式)
通过递推式可以列出生成函数,然后解一个二次方程,用广义二项式定理展开一下,经过化简后得到\(H(n)=\frac{C^n_{2n}}{n+1}\)