Let $D(z,k,l)$ be the number of permutations $p_1,\ldots,p_z$ of $1,\ldots,z$ in which the condition $p_i + p_{i+1} \leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z \geq 2$ and $z+1 \leq k \leq 2z-1$:
$$
D(z,k,l) = \begin{cases}
(z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\
(z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k \neq z+1.
\end{cases}
$$
I leave the proof of correctness to you.
(Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.)
The following Python program implements this recurrence:
def D(z, k, l):
if z < 2 or k < z+1 or k >= 2*z:
raise "Error"
if z == 2:
return 2 * int(l == 0)
if k == z+1:
return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l)
return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1)
A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic.
For concreteness, here is a Python implementation of the dynamic programming method:
def DP(z, k):
if not (z >= 2 and z+1 <= k <= 2*z-1):
raise "Error"
z_crit = 2*z-k+1
L = [2, 0]
for w in range(3, z_crit+1):
L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0]
for w in range(z_crit+1, z+1):
L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0]
return L[0]
