Стек внутри и снаружи

Question

Есть n различных элементов,

уже знает порядок, в который вставляется каждый элемент.

Сколько может быть различных комбинаций для порядка всплывающих окон?

EDIT

На самом деле я знаю, что есть 2n! / (N + 1) n! ^ 2 комбинаций, но почему?

Answer 1

Предположим, ваши элементы называются A, B, C, ... и помещаются в таком порядке.

Пусть P (X) означает «Push X», а O (X) означает «Pop 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.

Основываясь на этом паттерне, вы должны быть в состоянии построить и решить рекуррентное отношение, дающее нужный вам ответ.

Answer 2

Стек может быть вытянут только в одном порядке - в обратном порядке, в котором элементы были перемещены.

Answer 3

Отличный Эрик. Однако, когда я попробовал с ABC, я получил 4 возможности, ABC, BAC, BCA и CBA.

Жаль, что представленная формула не ясна, потому что я не могу сделать n = 3, чтобы дать ответ 4 из простых интерпретаций того, что было написано выше.

Казалось бы, индукция - это ответ на доказательство формулы (как это часто бывает, когда вопрос имеет форму «докажи, что ... дается формулой ...»).

И в четырех перечисленных выше возможностях есть определенная симметрия, из-за чего я думаю, что найти ответ не составит труда.

РЕДАКТИРОВАТЬ: На самом деле, мы не можем получить ACB также? AaBCcb. Где заглавные буквы - это толчок, строчные - поп. Итак, 5 возможностей, CAB определенно невозможен.