Suppose a stack and I want to find the permutations of numbers 1,2,3,...n. I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1. if n=4 I can only get 14 from the 24 permutations using the stack.. Does anyone know any function F(n) that could produce the number of permutations the stack (only one) can produce?

snaketao0g

snaketao0g

Answered question

2022-11-01

Suppose a stack and I want to find the permutations of numbers 1,2,3,...n.
I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1
if n=4 I can only get 14 from the 24 permutations using the stack.. Does anyone know any function F(n) that could produce the number of permutations the stack (only one) can produce?
eg f(1)=1
f(2)=2
f(4)=14

Answer & Explanation

cdtortosadn

cdtortosadn

Beginner2022-11-02Added 19 answers

The number corresponds to the Catalan Numbers which are of the form ( 2 n n ) n + 1
For a hint of proof: Number of pushes Number of pops in any prefix of the string of pushes and pops.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?