Catalan Stack Output Permutations

Worked Example

Consider an input sequence of size n = 3: 1, 2, 3. We want to determine if the output permutation 3, 1, 2 is reachable. Because the input strictly increases, we must greedily push elements onto the stack until the next needed output element is at the top of the stack.

1. We need to output 3. The next available input is 1. Push 1.
2. The top of the stack is 1, not 3. Push 2.
3. The top of the stack is 2, not 3. Push 3.
4. The top of the stack is 3. We pop 3 to the output.
5. Next, we need to output 1. The top of the stack is 2, and there are no more input elements to push.

Input: []
Stack: [1, 2]
Output: [3]
Target next: 1

Since the top of the stack (2) does not match the target element (1) and we cannot bypass it, the target permutation 3, 1, 2 is impossible to generate. It requires avoiding the 3-1-2 pattern in stack-sortable permutations.

Experiment

The Catalan Stack Output Permutations interactive module allows varying the sequence size up to 5 and testing specific targets like "Obstructed" (e.g., 3, 1, 2 for n=3) versus "Decreasing" (3, 2, 1). The visualization shows a greedy tracing process that attempts to match the target permutation step-by-step.

1. Open the interactive visualization.
2. Set the Size control to 3 and the Target control to Obstructed.
3. Observe that the trace animation fails and the Reachability reads Blocked.
4. Change the Target control to Decreasing and observe it becomes Reachable.

It also performs an exact independent enumeration of all valid push/pop operation sequences, mapping each sequence to its resulting output permutation. By counting the unique reachable outputs, we observe that the number of reachable permutations exactly matches the Catalan number C_n = binom(2n, n) / (n + 1), which is much smaller than the total number of permutations n!.

Limitations

The greedy trace logic relies on knowing the specific target output permutation in advance to guide the push/pop decisions. Furthermore, the enumeration uses a naive recursive search over all valid operation sequences. This approach is computationally limited for large n due to exponential growth. Therefore, it is constrained to sizes n ≤ 5 in the interactive tool.

References

For a comprehensive overview of combinatorial structures counted by Catalan numbers, including stack-sortable permutations, refer to Richard P. Stanley's work: https://math.mit.edu/~rstan/ec/catalan.pdf.