Posted 10/01/2016

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

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

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

This problem is about Spearman's footrule distance.

Given two permutation $\sigma=\sigma_1\sigma_2\cdots\sigma_n$ and $\tau=\tau_1\tau_2\cdots\tau_n$, the Spearman's footrule distance between $\sigma$ and $\tau$ is defined as $$ D(\sigma,\tau):=\sum_{i=1}^n|\sigma_i-\tau_i|. $$ For example, suppose $\sigma=(1,3,4,2)$ and $\tau=(4,3,2,1)$, then $D(\sigma,\tau)=3+0+2+1=6$.

We use $e$ to denote the identity permutation in $S_n$. In $S_3$, $e=(1,2,3)$.

Suppose we let $a_n^k$ denote the number of permutations in $S_n$ whose distance between identity permutation $e$ is $k$.

Find $a_n^k$.