Let $\mathfrak{S}\_n$ denote the group of permutations on $\{1,2,\dots,n\}$. Now, introduce the sets
$$\mathcal{A}\_n^{(k)}:=\{\pi\in\mathfrak{S}\_n: -1\leq \pi(j)-j\leq k,\,\forall j\}.$$


I would like to ask:



> 
> **Question.** What is the cardinality $\#\mathcal{A}\_n^{(k)}$ of these sets, in terms of $n$ and $k$?
> 
> 
> 



Counting "deflected" permutations: Part I
The fact that $-1 <= \pi(j) - j$ means that an element of the permutation can
only shift one position to the right. This means that a permutation satisfying
the lower bound is composed of nonoverlapping factors of the form
$i+m,i,i+1,\dots,i+m-1$ that start at position $i$. The upper bound restricts the
size of $m \le k$. Since the size of the factor is $m+1$ the number of permutations
in $\mathfrak{S}\_n$
satisfying $-1 \le \pi(j) - j \le k$ is just the number of compositions of $n$
whose largest part is less than or equal to $k+1$.


I don't know of a nice closed form, but
$$\#\mathcal{A}\_n^{(k)}=[x^n]\frac{1-x}{1-2x+x^{k+2}}$$


