Say we have the numbers from 1 to \(N\) in sequence. We will do a random sequence of pushes and pops into a stack: \(N\) pushes and \(N\) pops.
Not all of these sequences are valid (e.g. you can’t start with a pop).
What fraction of push/pop sequences are valid?
Let’s represent a push with a 1 and a pop with a 0. We have \(N\) of each. Our constraint is that at any point in the sequence, we cannot have seen more 0’s than 1’s.
This is equivalent to the Catalan numbers (with -1 instead of a 0). Hence, the number of valid sequences is:
\begin{equation*}
C_{N}=\frac{1}{N+1}\dbinom{2N}{N}
\end{equation*}
For the fraction, note that the total number of sequences with \(N\) 1’s and \(N\) 0’s is
\begin{equation*}
\dbinom{2N}{N}
\end{equation*}
So the ratio is simply \(1/(n+1)\).