2017 MPFG Problem 14

Problem

A $\textit{permutation}$ of a finite set $S$ is a one-to-one function from $S$ to $S$ . Given a permutation $f$ of the set ${1,2,...,100}$ , define the displacement of $f$ to be the sum $\sum_{i=1}^{100}\left|f(i)-i\right|$ How many permutations of ${1,2,...,100}$ have displacement $4$ ?

Solution 1

Displacement is basically the sum of error of each place in the permutation. Consider how to split the displacement of $4$ : $4 = 2+2 = 1+1+2 = 1+1+1+1$ .

We may have $2$ numbers with a difference of $2$ switching location, $3$ consecutive numbers rotated, and $2$ sets of $2$ consecutive numbers switching location. The first situation gives us $\{(1,3),(2,4),...,(98,100)\} = 98$ permutations, the second situation gives us $\{(1,2,3),(2,3,4),...,(98,99,100)\} = 2\cdot 98 = 196$ permutations, since the $3$ numbers can be "rotated" in two directions, and the third situation gives us ${98\choose 2} = 4753$ permutations, selecting $2$ from the $\{(1,3),...,(98,100)\}$ pile.

$98+196+4753=\boxed{5047}$

~cassphe

Page

Toolbox

Search

2017 MPFG Problem 14

Problem

Solution 1