Consider the cardinality $P(n,d)$ of permutations where elements can move up to distance $d$; for example, the permutation $\binom{012}{102}$ with $d = 1$ would be valid but $\binom{012}{201}$ would not.
It seems relatively straightforward to apply a rook polynomial for the cases where $d >= \lfloor{\frac{n}{2}} \rfloor - 1$, for even $n$, and $d >= \lfloor{\frac{n}{2}} \rfloor$, for odd $n$:
In the example below, B's are blocked/unavailable cells:
$n = 4, d = 1$
$\begin{matrix} 0 & 0 & B_2 & B_2 \\ 0 & 0 & 0 & B_2 \\ B_1 & 0 & 0 & 0 \\ B_1 & B_1 & 0 & 0 \end{matrix}$
To generate a polynomial for $B_1$, I use a recurrence, incrementing coefficients as the triangle grows.
$B_1 = 1 + 3x + x^2$
$B = B_1 \cdot B_2 = B_1^2 = 1 + 6x + 11x^2 + 6x^3 + x^4$
$P(4,1) = 1\cdot4! - 6\cdot(4-1)! + 11\cdot(4-2)! - 6\cdot(4-3)! + 1\cdot0! = 5$
But what if $B_1$ and $B_2$ overlap? For example,
$n = 4, d = 0$
$\begin{matrix} 0 & B_2 & B_2 & B_2 \\ B_1 & 0 & B_2 & B_2 \\ B_1 & B_1 & 0 & B_2 \\ B_1 & B_1 & B_1 & 0 \end{matrix}$
Can someone suggest or point me towards an efficient method to compute $B$ when $B_1$ and $B_2$ overlap (assuming we can compute $B_1$ easily)? I am hoping for a general case, considering $n$ and $d$ are known and $B_1$ and $B_2$ are always symmetrical.