Valid stack permutations; Catalan numbers

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• In postfix evaluation, which operand is popped first? from Lesson 3.2.2
• What does row-major order mean? from Lesson 3.1
• How many ways can 3 of 7 books be chosen (order not mattering)? from Lesson 0.2.2

1 · The Hook

🎣

Railway coaches numbered 1, 2, 3, 4 arrive in order on a track that leads into a dead-end siding. A coach can be pushed into the siding or sent straight out to the exit, and the siding releases its last-entered coach first. Which orders of coaches can leave? Some cannot be produced at all, and counting the possible ones leads to a famous sequence.

2 · Predict First

🤔

Input 1, 2, 3 (in that order) passes through a stack. Of the 6 orders of 1, 2, 3, which one cannot be produced? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

3 1 2. To output 3 first, 1 and 2 must already be in the stack with 2 on top, so 2 must come out before 1. The other five orders (1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 2 1) are all possible.

Stack permutations

Items 1, 2, …, n arrive in order. At each step you may push the next input or pop the top to the output. Every output order you can produce this way is a stack permutation (a valid output sequence).

Testing a sequence

Simulate: for each wanted output value, push inputs until that value is on top, then pop it. If the wanted value is already inside the stack but not on top, the sequence is impossible.

Shortcut: the output is impossible exactly when it contains a pattern “big, small, middle”: some value x followed later by a smaller y and then by a value z with y < z < x (like 3 … 1 … 2).

Catalan numbers

The number of stack permutations of n items is the n-th Catalan number:

C(n) = (2n)! / ((n + 1)! · n!) = (2n choose n) / (n + 1)

Checked by brute force: of the 24 orders of 4 items, exactly 14 are stack permutations; of 120 orders of 5, exactly 42.

Where else Catalan numbers appear

• Balanced strings of n pairs of brackets: n = 3 gives 5 (((())), (()()), (())(), ()(()), ()()()).
• Ways to fully bracket a product of n + 1 factors (Lesson 3.2.2’s expressions).
• Sequences of n pushes and n pops that never pop an empty stack (exactly the same counting problem).
• Later, the number of differently shaped structures built from n linked items.

4 · Visual

Producing 2 4 3 1 from input 1 2 3 4:

action        stack       output
push 1        1
push 2        1 2
pop           1           2
push 3        1 3
push 4        1 3 4
pop           1 3         2 4
pop           1           2 4 3
pop           (empty)     2 4 3 1      valid

Trying 3 1 2:  push 1, push 2, push 3, pop -> 3 ; want 1 but top is 2  -> impossible

Simulation decides any sequence in one pass.

The moment before 4 is popped while producing 2 4 3 1.

5 · Worked Examples

Example 1 Easy

Input 1, 2, 3, 4. Is 3 2 4 1 a valid stack permutation?

Solution

push 1, 2, 3; pop 3; pop 2; push 4; pop 4; pop 1 → valid.

Example 2 Medium

Input 1, 2, 3, 4. Which of these are impossible: 4 1 3 2, 2 4 3 1, 3 1 2 4, 1 4 2 3?

Solution

4 1 3 2: after popping 4, the top is 3, not 1 → impossible. 2 4 3 1: valid (trace above). 3 1 2 4: after 3, top is 2 → impossible. 1 4 2 3: after 4, top is 3 → impossible. Simulation agrees: 4132 invalid; 2431 valid; 3124 invalid; 1423 invalid.

Example 3 GATE

How many different output sequences can 6 distinct items produce when they enter a stack in a fixed order? How many balanced bracket strings use 4 pairs?

Solution

C(6) = (12 choose 6)/7 = 924/7 = 132. C(4) = 14.

6 · GATE Traps

⚠️

• The input order is fixed; only the timing of pushes and pops is chosen.
• An item already buried in the stack can only come out after everything above it.
• Catalan C(n) = (2n choose n)/(n + 1), not (2n choose n).
• Count stack permutations of n items, not 2n: n = 4 gives 14, not 70.
• Pattern test: x … y … z with y < z < x is impossible.

8 · Memory Hook

🧠

“A train cannot overtake inside a dead-end siding.” Once 3 has left, 1 and 2 must leave in the order 2, 1. Count the legal timetables with Catalan: 1, 1, 2, 5, 14, 42, 132.

9 · Connect the Dots

Lessons 3.2.1–3.2.3 studied the stack, where the newest item leaves first. Many real systems serve the oldest item first instead: a ticket counter, a printer, packets on a network. Next lesson answers: what is the structure that adds at one end and removes at the other, and what goes wrong when it is built naively on an array?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markValidity

Input 1, 2, 3, 4, 5. Which output is impossible with one stack?

• (A) 4 2 3 1 5
• (B) 3 4 2 1 5
• (C) 1 2 3 4 5
• (D) 5 4 3 2 1

Q2NAT1 markCatalan

What is the 5th Catalan number C(5)?

Numerical answer: ________

Q3NAT2 marksCounting

How many valid stack permutations do 4 items have?

Numerical answer: ________

Q4MSQ2 marksSequences

Input 1, 2, 3, 4. Which outputs are valid?

• (A) 3 2 4 1
• (B) 2 4 3 1
• (C) 4 1 3 2
• (D) 1 3 2 4

Q5NAT1 markBrackets

How many balanced strings of 3 pairs of brackets are there?

Numerical answer: ________

11 · Rule Card

• Stack permutation: fixed input order, choose when to push/pop.
• Test by simulation, or forbid x … y … z with y z x.
• Catalan C(n) = (2n)!/((n + 1)!·n!) = (2n choose n)/(n + 1).
• C(0…7) = 1, 1, 2, 5, 14, 42, 132, 429.
• Also counts balanced bracket strings and push/pop sequences.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

stack permutationvalid output sequenceCatalan numbersbalanced bracket strings

13 · Answer Vault