Posted 12/01/2016

----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

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

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