Given a sequence$\{1,2,\dots,n\}$,you can insert the elements one by one via both ends of the deque(double-ended queue).Then you can pop elements out of the two ends until the deque is empty.At last you can obtain a permutation.How to prove that the number of different permutations is ${2(n-1)\choose n-1}$?
It seems like the number is Type B Catalan number,and we already know that the number of permutations generated by a stack is Type A Catalan number.However I'm not sure if there is any relationship between them.