About Warm-ups Problems News

Problem 32

Posted 12/01/2016
Refresh the webpage if formulas are not shown correctly.
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}$.

Back to top