2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.