4
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ It is past my bedtime, but isn't this just the number of compositions of $n$ into parts at most $k+1$? $\endgroup$
    – Deinst
    Jun 16, 2017 at 4:54

1 Answer 1

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ These are the $k$-bonacci numbers, as in Fibonacci, tribonacci etc. $\endgroup$ Jun 16, 2017 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.