堆栈进出

有n不同的元素，堆栈进出

已经知道每个元素在推送的顺序排列。

如何组合的许多不同种类能有对空间PoPing订单？

编辑

其实我知道有2N！/（N + 1）N！^ 2点的组合，但是为什么呢？

2009-11-29 Mask

听起来像一个功课问题;也许你可以告诉我们你对这个问题的思考以及你卡在哪里？ – Amber 2009-11-29 07:57:38

作为@AttishOculus指出的答案之一..（1）指出（+1） – 2009-11-29 08:01:02

他只是问另一个问题，这似乎是来自同一个任务（如果这确实是作业）：http://stackoverflow.com/questions/1814956 /什么样的递归，可以解决，没有堆栈 – 2009-11-29 08:01:07

堆栈只能按一个顺序弹出 - 这与元素被推送的顺序相反。

2009-11-29 07:58:34 AttishOculus

是的，但OP没有指定所有的推动发生在任何弹出之前（反之亦然）。 – Amber 2009-11-29 08:00:07

@Dav我不明白推挤和流行的交错如何影响流行的顺序，如果它真的是一个堆栈，那么这些项目按它们推送的顺序弹出，故事结束。所以我们可以选择推动顺序并改变它，但这不是很有趣，这只是简单的组合。 – djna 2009-11-29 09:32:36

这个问题的主人太不好，不足以正确地描述问题，这样我们就不用猜测xe的含义了...... – AttishOculus 2009-11-29 15:45:10

假设您的元素被称为A，B，C ......并按此顺序推送。

令P（X）的平均 “推X” 和O（X）的平均 “流行X”

设N是元件的数量。

那么流行订单是什么？

当N = 1时的可能性：P（A）O（A）。（即“A”）

当N = 2时的可能性：P（A）P（B）O（B）O（A）。（“BA”）P（A）O（A）P（B）O（B）。（“AB”）

当N = 3时的可能性：ABC和BAC（从上面开始，然后是P（C）O（C）。）CBA。（来自P（A）P（B）P（C）O（C）O（B）O（A）。）但是不是 CAB，因为如果“C”首先出现，它肯定是最后一次，所以没有其他东西出来了，所以他们只能按照BA的顺序出现。

从这种模式构建，你应该能够构建和解决一个递归关系，给出你需要的答案。

2009-11-29 16:52:48 Eric

不错的一个埃里克。但是，当我尝试ABC时，我有4种可能性，ABC，BAC，BCA和CBA。

可惜提出的公式不明确，因为我不能让n = 3从上面写的内容的简单解释给出4的答案。

归纳似乎是证明公式的答案（因为当问题的形式经常是“证明......是由公式给出......”的时候）。

而且在上述四种可能性中存在一定的对称性，这使我认为提出答案可能不会太困难。

编辑：其实，我们不能得到ACB吗？ AaBCcb。大写字母是推送，小写字母是流行。所以，5种可能性，CAB绝对不可能。

2009-12-03 08:55:29

回答