## Problem 32

Posted 12/01/2016
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

----------------------

In this problem, we shall define $k$-self-avoiding permutations.

Reduction of an integer sequence $w=w_1w_2\ldots w_n$ is a sequence obtained by replacing the $i$-th smallest number in $w$ by $i$, denoted by red$(w)$. For example, red$(7~3~2~11~8)=3~2~1~5~4$.

We use one-line notation for permutations. Given some integer $k\geq 1$, we say a permutation $\sigma=\sigma_1\sigma_2\ldots\sigma_n\in S_n$ is $k$-self-avoiding if $$\text{red}(\sigma_{i-k+1}\sigma_{i-k+2}\ldots\sigma_i)\neq\text{red}(\sigma_{i}\sigma_{i+1}\ldots\sigma_{i+k-1}),$$ for any $k\leq i\leq n-k+1$.

For example, a $2$-self-avoding permutation must be an up-down permutation or a down-up permutation.

Suppose we let $a_{n,k}$ denote the number of $k$-self-avoiding permutations in $S_n$.

Find $a_{n,k}$.