n个元素按顺序入栈，求合法的出栈序列的个数_n个元素的出栈个数怎么算_qq_37370294的博客-程序员秘密

方法一

n = 1时，记出栈序列的个数f(1) = 1;
n = 2时，易知f(2) = f(1) + f(1) = 2; //12, 21
n = 3时，f(3) = f(2) + f(1) * f(1) + f(2); //123, 132, 213, 231, 321
…
n = k时，记f(0) = 1,则f(k) = f(0) *f(k-1) + … + f(k-1) *f(0)

方法二

若一次入栈操作记为‘1’，一次出栈操作记为‘0’，则每一个出栈序列对应一个由n个’1’和n个‘0’组成的组合数，且对该组合数从左至右进行扫描时，‘1’的个数始终不少于‘0’的个数。
对于一个非法的组合数，从左至右进行扫描时，一定存在m = 0,1,2,…，使得在第2m+1个元素时，有m个‘1’和m+1个‘0’；故后2(n-m)-1个元素一定由n-m个‘1’和n-m-1个‘0’组成，若将后2(n-m)-1个元素的‘1’和‘0’互换，则该组合数由n-1个‘1’和n+1个‘0’组成。相反，若该组合数由n-1个‘1’和n+1个‘0’组成，那么一定存在m = 0,1,2,…，使得第2m+1位之前的‘1’的个数少于‘0’的个数。
综上，n个元素顺序入栈，出栈序列的个数f(n) = C(2n,n) - C(2n, n-1) = C(2n,n)/(n+1)

方法三（卡特兰数）

满足h(0) = 1, h(1) = 1, h(n) = h(0) *h(n-1) + h(1) *h(n-2)… + h(n-1) *h(0)的数成为卡特兰数。
递推式的解为 C(2n, n) / (n + 1)或 C(2n, n) - C(2n, n - 1).

相似问题

1.买票找零
2n个人排队买票，其中n个人只有5元纸币，另n个人只有10元货币，票价5元。求有多少种方法使得每个10元顾客都能被找零。

2.n个1和n个-1组成一个数字串，求任意前k个数的和均不少于零的字串的个数。

结果：C(2n, n) / (n+1)

本文链接：https://blog.csdn.net/qq_37370294/article/details/108493630

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

OpenCV-Python官方示例文档_opencv-python官方文档_骚火棍的博客-程序员秘密

链接：https://docs.opencv.org/4.0.1/d6/d00/tutorial_py_root.html

Locust 安装教程_菜狗瑞的博客-程序员秘密

Locust 安装1、安装依赖包1、gevent 微线程库（Coroutine）2、flask 轻量级Web 开发框架。3、Requests 用来做 HTTP 接口测试。4、msgpack-python 二进制序列化格式，适用于类似JSON的数据。2、安装locustpip install locust...

〖Python 数据库开发实战 - MySQL篇㉗〗- MySQL 数字函数_pymysql数据库函数_哈哥撩编程的博客-程序员秘密

该章节开始我们将要学习 MySQL 的函数，在前面的章节我们使用过几个函数；比如 "四舍五入" 的 "ROUND" 函数，进行 "日期计算" 的 "DATEDIFF" 函数等等。接下来，我们就来系统的学习一下这些内置函数吧。.........

利用java格里高利公式求圆周率_C语言用下列公式求pi的近似值,直到最后一项的绝对值小于1e-4为止:..._Cold flowers的博客-程序员秘密

C语言输入精度e 和实数x,用下列公式求cos x 的近似值,精确到最后一项的绝对值小于e｡#include//头文件置顶#includedoublefact(intn){\用下面的近似公式求Pi的近似值,直到第n项绝对值小于10~5为止.Pi/4=1-1/3+1/5-PrivateSubCommand1_Click()a=1Don=n+1m=2*n-1s=s+a*1/ma=-aLoo...

java中的参数传递_yubofighting的博客-程序员秘密

Parameter passing in Java - Java中的参数传递本文摘抄自国外的一个Java论坛，并由博主Shane依据原文对照翻译，如有问题或指教请与邮箱john[email protected]联系，谢谢！IntroductionThis page is gradually growing

一千行MySQL学习笔记（十一）_dingluan5041的博客-程序员秘密

--// 存储函数，自定义函数 ------------ 新建 CREATE FUNCTION function_name (参数列表) RETURNS 返回值类型函数体 - 函数名，应该合法的标识符，并且不应该与已有的关键字冲突。 - 一个函数应该属于某个数据库，可以使用db_name.funciton_name的形式执行当前函数所属数据库，否则为...