How many kinds of output of stack with the input 1,2,…,n?
答案应该是这个((2n)!)/(n+1)n!n!
求具体的解释，详细一些，合计了好长时间也没理解，拜托啦……
[解决办法]
你搜卡特兰数
网上说的比我好，就不写了
[解决办法]
关于卡特兰数的推导，有很多种方法，lz可以这样想，设0表示入栈1表示出栈，那么n个数的入栈出栈则可以表示为一个由n个0n个1组成的2n位的数，并且取任何1位，之前0的数量都>=1的数量。由n个0n个1组成的数共有C(2n,n)个。其中不符合0的数量>=1的设为k，则c(2n,n) - k为符合条件的数量，即卡特兰数。那么k有多少呢？所有不符合条件的排列，一定可以找到1位其中1的数量比0的数量多1个，那么把这一位之前的0和1互换一下，则2n位数变为了n+1个0n-1个1。也就是说每一个不符合条件的组合都对应一个不同的n+1个0n-1个1的数。反过来所有n+1个0n-1个1的数，也可以经过同样的调换，对应一个不同的n个0n个1的数。因此不符合条件的数同n+1个0n-1个1是一一对应的。n+1个0n-1个1的数量是c(2n,n-1)，因此符合条件的数为c(2n,n) - c(2n,n-1) = c(2n,n)/n+1
[解决办法]
令h(1)=1,h(2)=1，catalan数满足递归式： h(n)= h(1)*h(n-1)+h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=3) 例如：h(3)=h(1)*h(2)+h(2)*h(1)=1*1+1*1=2 h(4)=h(1)*h(3)+h(2)*h(2)+h(3)*h(1)=1*2+1*1+2*1=5 另类递归式： h(n)=h(n-1)*(4*n-2)/(n+1); 该递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
