About
Warm-ups
Problems
News
Problem 30
Posted 10/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.
----------------------
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$.
Back to top