Suppose i have an $n-$elements array. I want to count number of permutations for which element $a_i$ allowed to appear in range $i-k, \dots, i+k,$ so $2k+1$ positions available after permutation has happenned.
I got a rough bound $n$ elements at most $2k+1$ positions for every one. Thus, the bound is $n^{2k+1}.$ And this is an upper bound, but i need lower one as well. The best is exact formula.
EDIT: A lower bound is $(k!)^{n/k}.$