Permutations such that sum of adjacent elements is less than equal to k [closed]

Permutations such that sum of adjacent elements is less than equal to k [closed]

We have two integers z,k
We form a sequence now of first z natural numbers. i.e. 1, 2, 3, 4, ...z.
Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is <=k
z <=10^6, z < k < 2*z-1
Here is what I have been able to think untill now. If k=2*z-1, the answer is z!
Now if we reduce the value of k to 2*z-2, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of k=2*z-1
i.e. dp(z,k)= z! for k=2*z-1. and dp(z,k-1)=dp(z,k)-(z-1)!*2 for k=2*z-2.
I want to know if I am going in the right direction. Any help on the closed form would be good.