有n个不同元素的序列经过一个栈产生的出栈序列个数是多少？

这个问题可以用卡特兰数来求解。卡特兰数是一个非常有用的数列，它出现在许多计数问题中，如括号匹配、出栈序列、二叉树等等。卡特兰数的递推公式为：

C(n) = C(0)C(n-1) + C(1)C(n-2) + … + C(n-1)C(0)

其中C(n)表示n个元素的序列所能产生的不同出栈序列的个数，C(0)=1。这个递推公式的意思是，假设第一个元素出栈，那么剩下的n-1个元素可以组成一个任意的出栈序列，所以有C(0)C(n-1)种情况；假设第一个元素不出栈，那么第二个元素就会成为第一个出栈的元素，剩下的n-2个元素可以组成一个任意的出栈序列，所以有C(1)C(n-2)种情况；依此类推，直到假设第一个元素到第n-1个元素都不出栈，此时剩下的最后一个元素必须出栈，所以有C(n-1)C(0)种情况。将这些情况相加即可得到C(n)的值。

下面是一个Python的实现：

def catalan(n): if n == 0: return 1 else: c = 0 for i in range(n): c += catalan(i) * catalan(n-i-1) return c

n = int(input()) print(catalan(n)