# Counting "deflected" permutations: Part I

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\}.$$

Question. What is the cardinality $\#\mathcal{A}_n^{(k)}$ of these sets, in terms of $n$ and $k$?
• It is past my bedtime, but isn't this just the number of compositions of $n$ into parts at most $k+1$? Jun 16, 2017 at 4:54
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}}$$
• These are the $k$-bonacci numbers, as in Fibonacci, tribonacci etc. Jun 16, 2017 at 17:25