# Number of permutations such that adjacent elements don't differ by more than $K$

Given $N$ and $K$, I need to count number of permutations of $1, 2, 3,\ldots, N$ in which no adjacent elements differ by more than $K$. How do I approach this problem?

• Please share your thoughts so far :) – Shaun Jan 25 '15 at 10:16
• I am trying to count the number of permutations by hand, but it is too cumbersome. – xennygrimmato Jan 25 '15 at 10:20
• Here is one estimate: There are $N!$ permutations. Each has $N-1$ adjacent pairs. These must all come from $(N-1)+...+(N-K)$ of the $N(N-1)/2$ pairs, so my estimate is $N!{(N-1)+...+(N-K)\choose N-1}/{N(N-1)/2\choose N-1}$. – Empy2 Jan 25 '15 at 11:08
• This is OEIS A249631. I note there are no formulae there, only a couple routines that generate/filter/count, so I wonder if there are in fact any other methods. – HammyTheGreek Jan 26 '15 at 21:44

This is a question that appeared in a contest i.e Codecraft 2015 organised by IIITH and its editorial is available here. You can also submit your code in the gym.

Basically you require DP + Bitmask.You need to keep track of last_used element and all other elements included so far.You can do it using recursion and it will require memoization to optimize it.