A sequence of jumps from ~c_s~ to ~c_f~ can be mirrored and thus obtaining a valid sequence of jumps from ~c_f~ to ~c_s~. Due to this symmetry, ~c_s~ and ~c_f~ can be swapped such that ~c_s < c_f~.

We will add the following definitions:

• ~A[n][i][j] =~ the number of alternating permutations that start ascending, having the first and the last elements ~i~ and ~j~
• ~D[n][i][j] =~ the number of alternating permutations that start descending, having the first and the last elements ~i~ and ~j~
• ~X[n][i][j] = A[n][i][j] + D[n][i][j]~, (our target)
• ~Y[n][i][j] = A[n][i][j] - D[n][i][j]~, (for formal reasons)

Let's consider an alternating permutation of length ~n~ that starts with ~i~ and ends with ~j~. By removing the left extremity (~i~) and decreasing all values greater than ~i~ by ~1~, we'll obtain an alternating permutation of order ~n-1~. We can infer the following recurrences:

$$\displaystyle \begin{align*} A[n][i][j] &= \sum_{k=i}^{n-2} D[n-1][k][j-1] \\ D[n][i][j] &= \sum_{k=1}^{i-1} A[n-1][k][j-1] \end{align*}$$

In other words, the number of alternating permutations of length ~n~ starting ascending with ~i~ and ending with ~j~ is equal to the number of alternating permutations of length ~n-1~ starting descending with ~i, i+1, \dots, n-1~ and ending with ~j-1~. Similarly for ~D[][][]~.

The above recurrences can be rewritten more conveniently:

$$\displaystyle \begin{align*} A[n][i][j] &= A[n][i-1][j] - D[n-1][i-1][j-1] \\ D[n][i][j] &= D[n][i-1][j] + A[n-1][i-1][j-1] \end{align*}$$

and from here we obtain:

$$\displaystyle \begin{align*} X[n][i][j] &= X[n][i-1][j] + Y[n-1][i-1][j-1] \\ Y[n][i][j] &= Y[n][i-1][j] - X[n-1][i-1][j-1] \end{align*}$$

After a few manipulations, we can further derive:

$$\displaystyle \underset{n \ge 3, i \ge 3}{X[n][i][j]} = 2 \times X[n][i-1][j] - X[n][i-2][j] - X[n-2][i-2][j-2]$$

Let's stop for a moment to assess the complexity. The answer can be easily computed in ~\mathcal O(N^3)~ using the above recurrence, but it can be reduced to ~\mathcal O(N^2)~ as follows.

Note the following invariant that is preserved by the recurrence:

$$\displaystyle n-j = (n-2) - (j-2) = \text{constant}$$

This is a key observation that shows the first and the third index of ~X[][][]~ will not be independent of each other by repeatedly using the recurrence starting backwards from ~X[N][c_s][c_f]~. Therefore, instead of three independent variables, ~(n, i, j)~, we'll have only two (since ~N-c_f = n-j = \text{constant}~), so the complexity will be ~\mathcal O(N^2)~ for a proper implementation.

We have one more thing to do, namely handling the corner cases ~i \le 2~:

Case n mod 2 = 1
    X[n][1][j] = A[n][1][j] = A[n][j][1]
    A[n][j][1] = D[n-1][j][1] + D[n-1][j+1][1] + … + D[n-1][n-1][1]
    A[n][j][1] = A[n-1][1][j] + A[n-1][1][j+1] + … + A[n-1][1][n-1]
    A[n][1][j] = A[n][1][j-1] - A[n-1][1][j-1]
Case n mod 2 = 0
    X[n][1][j] = A[n][1][j] = D[n][j][1]
    D[n][j][1] = A[n-1][j-1][1] + A[n-1][j-2][1] + … + A[n-1][3][1]
    D[n][j][1] = A[n-1][1][j-1] + A[n-1][1][j-2] + … + A[n-1][1][3]
    A[n][1][j] = A[n][1][j-1] + A[n-1][1][j-1]
resulting in
    X[n][1][j] = X[n][1][j-1] - X[n-1][1][j-1], n mod 2 = 1
    X[n][1][j] = X[n][1][j-1] + X[n-1][1][j-1], n mod 2 = 0

We have also:

A[n][2][j] = A[n][1][j] - D[n-1][1][j-1] = A[n][1][j] = X[n][1][j]
D[n][2][j] = D[n][1][j] + A[n-1][1][j-1] = A[n-1][1][j-1] = X[n-1][1][j-1]
(there is no descending permutation starting with 1)
    X[n][2][j] = X[n][1][j] + X[n-1][1][j-1]