There are n trains numbered 1 to n which are arranged in a stack structure. How many types of trains are possible?

Admin 1
Viewed 265

There are n trains numbered 1 to n which enter and leave a station in a stack structure as shown in the photo below. How many types of possible "pop" sequences are there?

w

For example, a possible path sequence of n=5 trains would be, 1 enters, 1 leaves, 2 enters, 2 leaves, 3 enters, 3 leaves, ..., resulting in 12345 as the possible pop sequence.

If n=6, are the following sequences possible:

  • 435612
  • 325641
  • 154623
  • 135426
data-structures stack queue algorithm
1 Answers

For n trains, the number of feasible sequences is the nth Catalan number.

We're forced to push the first train. When we pop the first train, we've pushed and popped between 0 and n−1 of the next trains. Then we push and pop the remaining trains. This results in a recurrence T(0) = 1; T(n) = sum over i from 0 to n−1 of T(i) T(n−1−i), which is the Catalan recurrence.

user_21446690
Related