Catalan Stack Output Permutations
Count the permutations one stack can emit and expose the first impossible pattern.
Free theory articleCount the permutations one stack can emit and expose the first impossible pattern.
Concept & interpretation
In computer science, a stack is a fundamental data structure with last-in, first-out (LIFO) semantics. When an increasing sequence of elements is fed into a stack, only certain output permutations can be generated using a sequence of push and pop operations. These reachable permutations are closely tied to Catalan numbers.
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.
- Open the interactive visualization.
- Set the Size control to
3and the Target control toObstructed. - Observe that the trace animation fails and the Reachability reads
Blocked. - Change the Target control to
Decreasingand observe it becomesReachable.
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!.