October 2025
In this problem, \(X_n\) will denote the set of integers \(\{1,2,3,\dots,n\}\). A permutation of \(X_n\) is an ordered list of these integers that contains each of them exactly once. For example, there are exactly \(6\) permutations of \(X_3\), and they are \[123, \quad 132, \quad 213, \quad 231, \quad 312, \quad 321\] Another way to think about a permutation is as a function from the set \(X_n\) to itself, where no two inputs to the function have the same output. For example, the permutation \(213\) of \(X_3\) represents the function that sends \(1\) to \(2\), sends \(2\) to \(1\), and sends \(3\) to itself. The permutation \(\sigma\) of \(X_5\) denoted by \(43512\) satisfies \(\sigma(1)=4\), \(\sigma(2)=3\), \(\sigma(3)=5\), \(\sigma(4)=1\), and \(\sigma(5)=2\).
In this problem, the displacement of a permutation \(\sigma\) of \(X_n\) is equal to \(\displaystyle {\bf D}(\sigma)= \sum_{i=1}^n|i-\sigma(i)|\). For example, with \(\sigma\) from the paragraph above, we have \[\begin{align*} {\bf D}(\sigma) &= |1-\sigma(1)| + |2-\sigma(2)| + |3-\sigma(3)| + |4-\sigma(4)| + |5-\sigma(5)| \\ &= |1-4| + |2-3| + |3-5| + |4-1| + |5-2| \\ &= 3+1+2+3+3 = 12\end{align*}\]
Suppose \(n\geq 2\). Determine the number of permutations \(\sigma\) of \(X_n\) that satisfy \({\bf D}(\sigma)=2\).
Suppose \(n\geq 4\). Determine the number of permutations \(\sigma\) of \(X_n\) that satisfy \({\bf D}(\sigma)=4\).
Prove for all \(n\geq 2\), if \(\sigma\) is a permutation of \(X_n\), then \({\bf D}(\sigma)\) is even.
Given an odd positive integer \(n\) and a permutation \(\sigma\) of \(X_n\), determine the maximum possible value of \({\bf D}(\sigma)\).
Given an odd positive integer \(n\), determine the number of permutations \(\sigma\) of \(X_n\) have the property that \({\bf D}(\sigma)\) is equal to the maximum from the previous question.