卡特兰数python
时间: 2024-04-19 09:23:08 浏览: 33
卡特兰数是一种在组合数学中常见的数列,它在计数问题中有着广泛的应用。卡特兰数由比利时数学家欧仁·查理·卡特兰(Eugène Charles Catalan)在19世纪中叶引入,并以他的名字命名。
卡特兰数的计算公式如下:
C(n) = (2n)! / ((n+1)! * n!)
其中,n为非负整数。卡特兰数可以用来计算许多不同问题的解决方案数量,例如:
- 括号匹配问题:给定n对括号,求合法的括号匹配方式数量。
- 凸多边形划分问题:给定n个顶点的凸多边形,求将其划分为三角形的方式数量。
- 栈的出栈序列问题:给定n个元素的入栈序列,求所有可能的出栈序列数量。
在Python中,可以使用递归或动态规划的方法来计算卡特兰数。下面是一个使用递归方式计算卡特兰数的示例代码:
```python
def catalan_number(n):
if n <= 1:
return 1
else:
result = 0
for i in range(n):
result += catalan_number(i) * catalan_number(n-i-1)
return result
# 示例调用
n = 5
print("Catalan number for n =", n, "is", catalan_number(n))
```
这段代码中的`catalan_number`函数使用递归的方式计算卡特兰数。当n小于等于1时,返回1;否则,通过递归计算左右子问题的卡特兰数,并将结果相乘累加得到最终结果。