Posted 12/01/2016

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

Previous Next

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

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

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

Previous Next

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

This problem is proposed by

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

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

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$

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