MP114
Problem for May 2012 

An arbitrary permutation $\sigma$ of the set of integers from 1 to 2012 can be represented in the plane by a set of 2012 points of the form $\left(k, \sigma(k)\right)$, where $k$ runs from 1 to 2012. The smallest square bounding this set of points with sides parallel to the coordinate axis has at least 2 and at most 4 points of the set on its boundary. Determine the number of permutations having exactly $m$ points on the boundary for $m$ equal to 2, to 3, and to 4.

To help you understand the problem, we include an example below of the corresponding figure for when $\sigma$ is a permutation of the numbers from 1 to 7 that has four points on its bounding square, namely the permutation that takes the ordered set $(1, 2, 3, 4, 5, 6, 7)$ to $(5, 3, 6, 1, 7, 2, 4)$.

Please note that in a solution to any math problem the explanation is all-important — every claim must be supported by some mathematical truth. 

Instructions for sending us your solution:

Please ensure that your solution contains your name and email or street address.

Solvers who submit their solutions by the 21^st of the month will have their names listed on the solutions page along with the best of the submitted solutions.

Solutions can be sent to us in three ways:

by email:	You must ensure that you start your subject line with [MP] otherwise our spam filter will delete your message. Send us your solution at .
or
by fax:	+1 (306) 585-4020 Mark it: Attention: Math Central
or
by post:	Math Central Department of Mathematics and Statistics University of Regina Regina, Saskatchewan S4S 0A2 Canada