I used dynamic programming to solve it. My DP state is (i, left, okay). Basically I start from N and go downwards. I need to select k elements from N to 2, and partition them into 2 decreasing sequences (which represent the two ends of the deque surrounding the element 1 after all elements are inserted into the deque).

i denotes the integer I will consider next. left denotes the number of integers > i, which are not used till now, and can be added to the second sequence when needed.

I have 2 choices for i. If I add it to the first sequence, I go to state (i-1, left, true), and if I skip it (and maybe add it later to second sequence), I go to state (i-1, left+1, false). The boolean variable takes care of overcounting. Basically I add some element to the first sequence, then some (maybe 0) elements to the second sequence and the process repeats.

After 1 has been put in kth position, the remaining n-k elements can be fixed in ways[n-k] ways. This is based on the recurrence, T(1)=1, T(n)=2*T(n-1). If you have some z elements to assign, you can choose either the right or left end of the deque and repeat the process for z-1 values.

Maybe this explanation is not quite clear. You can look at the code for hopefully understanding it better. :)