CEMC Banner

Problem of the Month
Solution to Problem 1: Displacing Permutations

October 2025

  1. The quantity \({\bf D}(\sigma)\) is a sum of absolute values of the form \(|\sigma(i)-i|\) where \(\sigma(i)\) and \(i\) are both integers. Therefore, each term in the sum defining \({\bf D}(\sigma)\) is a non-negative integer. The only way to have a sum of non-negative integers equal to \(2\) is for one integer to be \(2\) and rest \(0\), or for two of them to be equal to \(1\) and the rest equal to \(0\).

    If the quantity \(|\sigma(i)-i|=0\), then \(\sigma(i)=i\). If \(\sigma\) satisfies \(\sigma(i)=i\) for \(n-1\) values of \(i\) from \(1\) through \(n\), then it must satisfy \(\sigma(i)=i\) for all values of \(i\) from \(1\) through \(n\). This because permutations are functions that send each input to a different output. Thus, if \(\sigma(i)=i\) for \(n-1\) values of \(i\), then there is only one place for the \(n\)th value to be sent by \(\sigma\), and that value is itself.

    Therefore, having \(|\sigma(i)-i|=2\) for one value of \(i\) and all others equal to \(0\) is not possible. Thus, if \({\bf D}(\sigma)=2\), then there must be exactly two integers \(i\) between \(1\) and \(n\) inclusive such that \(|\sigma(i)-i|=1\).

    Suppose \(a\) is the smallest integer that satisfies \(|\sigma(a)-a|=1\). Then \(\sigma(a)=a-1\) or \(\sigma(a)=a+1\). If \(\sigma(a)=a-1\), then it is impossible for \(\sigma(a-1)=a-1\) (since a permutation cannot send two inputs to the same output) contradicting our assumption that \(a\) is the smallest integer not sent to itself. Thus, we must have \(\sigma(a)=a+1\). We also have that \(\sigma(a+1)\neq a+1\) for the same reasoning as above. If \(\sigma(a+1)\neq a\), then there must be some third integer that is not fixed by \(\sigma\). Thus, we have \(\sigma(a+1)=a\).

    We conclude that if \({\bf D}(\sigma)=2\), then \(\sigma\) interchanges two adjacent integers and fixes all others. For example, \(\sigma(1)=2\) and \(\sigma(2)=1\), and \(\sigma(i)=i\) for all \(i\geq 3\) is such a permutation.

    There are \(n-1\) such permutations, so the answer to the question is \(n-1\).

  2. By similar reasoning to that which was used in the previous solution, if \({\bf D}(\sigma)=4\), then \(4\) is a sum of non-negative integers, which means "most" of the integers must be \(0\). Again, it is impossible for a permutation to have exactly one point that is not fixed, so the sum being composed of \(4\) and \((n-1)\) zeros is not possible.

    The other possibilities are \(1+3\), \(2+2\), \(1+1+2\), and \(1+1+1+1\) (and all other integers equal to \(0\)). The sum \(1+3\) is not possible since if \(|\sigma(i)-i|=1\), then \(\sigma(i)=i\pm 1\), which means \(i\pm 1\) is not fixed. If \(i-1\) is not fixed, then we must have \(|\sigma(i-1)-(i-1)|=3\), and so \(\sigma(i-1)=i-4\) or \(\sigma(i-1)=i+2\). Then either \(i-4\) or \(i+2\) would not be fixed, which means the sum defining \({\bf D}(\sigma)\) would have at least three nonzero summands, which is contrary to our assumption.

    The other sums, \(2+2\), \(1+1+2\), and \(1+1+1+1\) are all possible.

    If the sum is \(2+2\), then there are two integers that are not fixed, and each is moved to a position \(2\) away from it. The only way to do this is to exchange two integers that differ by \(2\). There are \(n-2\) such permutations.

    The only way to achieve the sum \(1+1+2\) is by "cycling" three adjacent integers. That is, there is some integer \(i\) such that \(\sigma(i)=i+1\), \(\sigma(i+1)=i+2\), and \(\sigma(i+2)=i\) or \(\sigma(i)=i-1\), \(\sigma(i-1)=i-2\), and \(\sigma(i-2)=i\). This can be shown using the same kind of reasoning that has already been used. There are \(2\times(n-2)\) such permutations.

    For \({\bf D}(\sigma)\) to occur as \(1+1+1+1\) plus \((n-4)\) zeros, there must be two pairs, \(a\) and \(b\), with \(b-a\geq 2\) such that \(\sigma(a)=a+1\), \(\sigma(a+1)=a\), \(\sigma(b)=b+1\), and \(\sigma(b+1)=b\).

    If \(a=1\), then \(b\) can be any of \(3, 4, 5, \ldots, n-1\), for a total of \(n-3\) choices for \(b\). if \(a=2\), then there are \(n-4\) choices for \(b\). If \(a=3\), then there are \(n-5\) choices for \(b\). The largest possible value of \(a\) is \(n-3\), and in this case we must have \(b=n-1\), so there is \(1\) possibility.

    There are \(1+2+3+\cdots+(n-3) = \dfrac{(n-3)(n-2)}{2}\) permutations in this case.

    Therefore, the total number of permutations with \({\bf D}(\sigma)=4\) is \[3(n-2) + \dfrac{(n-3)(n-2)}{2} = \dfrac{(n-2)(6+n-3)}{2} = \dfrac{(n-2)(n+3)}{2}\]

  3. First, we will address the question for permutations that are cycles. An example of a cycle is permutation \(462351\) since \(\sigma(1) = 4\), \(\sigma(4)=3\), \(\sigma(3)=2\), \(\sigma(2)=6\), and \(\sigma(6)=1\). Note that \(\sigma(5)=5\), so the permutation "cycles" \(1\) to \(4\) to \(3\) to \(2\) to \(6\) and back to \(1\), and fixes every other integer, which is \(5\). We can express this cycle as \[1\to 4\to 3\to 2 \to 6 \to 1\] As another example, the permutation \[5\to 1\to 7\to 2\to 4\to 5\] of \(X_7\) is equal to the permutation \(7435162\). In this permutation, we have \(\sigma(5)=1\), \(\sigma(1)=7\), \(\sigma(7)=2\), \(\sigma(2)=4\), and \(\sigma(4)=5\), as well as \(\sigma(3)=3\), and \(\sigma(6)=6\). This means \(|\sigma(3)-3|=|\sigma(6)-6|=0\), and the other summands in \({\bf D}(\sigma)\) are \[\begin{align*} |\sigma(5)-5| &= 4 \\ |\sigma(1)-1| &= 6 \\ |\sigma(7)-7| &= 5 \\ |\sigma(2)-2| &= 2 \\ |\sigma(4)-4| &= 1\end{align*}\] Therefore, \({\bf D}(\sigma)=0+0+4+6+5+2+1=18\), which is indeed even. The important thing to take away here is that the number of odd numbers in the sum is \(2\) (and of course, \(2\) is even!).

    Suppose a cycle \(\sigma\) on \(X_n\) has the form \[a_1 \to a_2 \to a_3 \to \cdots \to a_k \to a_1\] which implies that \(k\) elements are moved by \(\sigma\), and the other \(n-k\) are not. Then we have \(\sigma(a_1)=a_2\), \(\sigma(a_2)=a_3\), and so on up to \(\sigma(a_{k-1})=a_k\) and then \(\sigma(a_k)=a_1\). We then have \[\begin{align*} {\bf D}(\sigma) &= |\sigma(a_1)-a_1| + |\sigma(a_2)-a_2| + |\sigma(a_3)-a_3| +\cdots + |\sigma(a_{k-1})-a_{k-1}| + |\sigma(a_k)-a_k| \\ &= |a_2-a_1| + |a_3-a_2| + |a_4-a_3| + \cdots + |a_k-a_{k-1}| + |a_1-a_k|\end{align*}\] Each term of the form \(|a_i-a_j|\) is even if \(a_i\) and \(a_j\) have the same parity, and it is odd if they have different parity. Thus, the number of odd terms in the sum above is equal to the number of times that the list \[a_1,a_2,a_3,\dots,a_{k-1},a_1\] changes parity. However, the list above has the same first and last number, so the parity must eventually change back to its original parity. In other words, the parity must change an even number of times, so there are an even number of odd integers in the sum above.

    The sum of a list of integers, an even number of which are odd, must be an even number.

    This shows that if \(\sigma\) is a cycle, then \({\bf D}(\sigma)\) is even. We now note that every permutation is composed of several cycles. For example, the permutation \(58123764\) satisfies \[\begin{align*} 1 &\to 5 \\ 2 &\to 8 \\ 3 &\to 1 \\ 4 &\to 2 \\ 5 &\to 3 \\ 6 &\to 7 \\ 7 &\to 6 \\ 8 &\to 4\end{align*}\] So we have \(1\to 5\to 3\to 1\), and this gives all of the information about what \(\sigma\) does to \(1\), \(3\), and \(5\). We can then start with \(2\) to get \(2\to 8\to 4\to 2\), and then \(6\to 7\to 6\). Thus, \(\sigma\) breaks into two cycles consisting of three distinct integers, and one cycle consisting of two distinct integers. The sum defining \({\bf D}(\sigma)\) can likewise be decomposed into \[\Big(|\sigma(1)-1| + |\sigma(5)-5| + |\sigma(3)-3|\Big) + \Big(|\sigma(2)-2| + |\sigma(8)-8| + |\sigma(4)-4|\Big) + \Big(|\sigma(6)-6| + |\sigma(7)-7|\Big)\] which is a sum of three even numbers.

  4. Suppose \(n=2k+1\) for some positive integer \(k\) and that \(\sigma\) is a permutation of \(X_n\). We will show that the maximum value of \({\bf D}(\sigma)\) is attained for any permutation satisfying

    For example, when \(n = 5\), such a permutation must send each of \(1\) and \(2\) to \(3, 4\), or \(5\), and it must send each of \(4\) and \(5\) to \(1\), \(2\), or \(3\). Roughly, the kinds of permutations we’re after send the first half of the list to the second half, and the send half to the first half (of course, there are an odd number of integers in the list, so first and second half isn’t precisely correct here).

    Suppose there is some \(a\leq k\) such that \(\sigma(a)\leq k\). The existence of such an \(a\) implies that there is some \(c\geq k+2\) such that \(\sigma(c)\geq k+2\). Otherwise, each of the \((2k+1) - (k+1)=k\) integers that are at least \(k+2\), as well as \(a\), are all sent by \(\sigma\) to the integers \(1,2,\dots,k\). This would imply that at least two of \(a,k+2,k+3,\dots,2k+1\) are sent to the same value by \(\sigma\), but this is impossible since \(\sigma\) is a permutation.

    Thus, if there is some \(a\leq k\) with \(\sigma(a)\leq k\), then there is some \(c\geq k+2\) such that \(\sigma(c)\geq k+2\). Assume that \(a\leq k\), \(b\leq k\), \(c\geq k+2\), and \(d\geq k+2\) satisfy \(\sigma(a)=b\) and \(\sigma(c)=d\). It is possible that \(a=b\) or \(c=d\) or both.

    Let \(\tau\) be the permutation given by \[\tau(a)=d, \quad \tau(c)=b \quad \text{ and } \quad\tau(i)=\sigma(i)\] if \(i\neq a\) and \(i\neq c\). This is still a permutation. The terms in \({\bf D}(\sigma)\) and \({\bf D}(\tau)\) are identical except that the terms \(|a-b|\) and \(|c-d|\) from the displacement of \(\sigma\) are replaced by \(|a-d|\) and \(|c-b|\) respectively in the displacement of \(\tau\). In other words, \[{\bf D}(\tau)-{\bf D}(\sigma) = |d-a| + |b-c| - |b-a| - |d-c|.\] Note that \(a\) and \(b\) are at most \(k\) and \(c\) and \(d\) are at least \(k+2\), so we know that \(a<c\), \(a<d\), \(b<c\), and \(b<d\). We will consider four possible cases for how \(a\) and \(b\) compare, and how \(c\) and \(d\) compare.

    No matter which of the four possibilities are true (and one of them must be true), we get that \({\bf D}(\tau) - {\bf D}(\sigma) > 0\), or \({\bf D}(\tau) > {\bf D}(\sigma)\).

    So, what have we shown with all of these calculations? Recall the two properties from the beginning of the solution to this question:

    1. \((1)\) If \(i < k + 1\), then \(\sigma(i) \geq k+1\).

    2. \((2)\) If \(i > k+1\), then \(\sigma(i) \leq k+1\).

    We have shown that if \(\sigma\) does not satisfy Property \((1)\), then there is a permutation \(\tau\) with \({\bf D}(\sigma) < {\bf D}(\tau)\). Similarly, you can show that if \(\sigma\) does not satisfy Property \((2)\), then there is a permutation \(\tau\) with \({\bf D}(\sigma) < {\bf D}(\tau)\) (see if you can do this!).

    Therefore, a permutation \(\sigma\) that maximizes \({\bf D}(\sigma)\) must satisfy both Properties \((1)\) and \((2)\).

    We will now show that \({\bf D}(\sigma)\) is constant for all such permutations. To see this, suppose \(\sigma\) is a permutation with the property from the previous paragraph. Suppose \(a\) and \(b\) are less than \(k\), and that \(\sigma(a)=c\) and \(\sigma(b) = d\). From our assumption, we must have \(c\geq k+1\) and \(d\geq k+1\). Let \(\tau\) be the permutation with \(\tau(a)=d\), \(\tau(b)=c\), and \(\tau(i)=\sigma(i)\) for all other \(i\). By very similar reasoning that which was used earlier, \[{\bf D}(\tau)-{\bf D}(\sigma) = |d-a| + |c-b| - |c-a| - |d-b|\] Since we know that \(a\leq c\), \(a\leq d\), \(b\leq c\), and \(b\leq d\), we have \[{\bf D}(\tau) - {\bf D}(\sigma) = |d-a| + |c-b| - |c-a| - |d-b| = (d-a) + (c-b) - (c-a) - (d-b) = 0\] Similarly, if we exchange the images under \(\sigma\) of two integers that are at least \(k+2\), the displacement will not change.

    We leave it to the reader to convince themself that every permutation of \(X_n\) can be attained from every other permutation by a sequence of such interchanges (Hint: Swap the values of \(\sigma(a)\) and \(\sigma(b)\) for some \(a\) and \(b\), and leave everything else alone). Thus, we only need to compute \({\bf D}(\sigma)\) for one permutation \(\sigma\) with the property that \(\sigma(i)\geq k+1\) when \(i\leq k\) and \(\sigma(i)\geq k+1\) when \(i\geq k+2\). One such permutation is as follows: \(\sigma(k+1)=k+1\), \(\sigma(i)=i+k+1\) for \(i\leq k\), and \(\sigma(i) = i-k-1\) for \(i\geq k+2\). Note that \(|\sigma(k+1) - (k+1)|=0\), while \(|\sigma(i)-i|=k+1\) for all other \(i\). Thus, \[{\bf D}(\sigma) = 0 + 2k(k+1) = (n-1)\left(\dfrac{n-1}{2}+1\right) = \dfrac{n^2-1}{2}\]

  5. In the previous problem, we shows that \({\bf D}(\sigma)\) is maximized precisely when \(\sigma\) satisfies

    To count how many permutations satisfy the two conditions above, we will first choose the value of \(\sigma(k+1)\), and then count the number of permutations that are possible.

    Suppose \(\sigma(k+1) = k+1\). Then for each \(i < k+1\), \(\sigma(i) > k+1\). There are \(k!\) ways this can happen. Similarly, there are \(k!\) ways \(\sigma(j) < k+1\) for \(j > k+1\). Therefore, the total number of permutations so that \({\bf D}(\sigma)\) is maximized and \(\sigma(k+1) = k+1\) is \((k!)^2\).

    Suppose \(\sigma(k+1) = t < k+1\) (note that there are \(k\) possible values for \(t\)). Then for each \(j > k+1\), \(\sigma(j) \leq k+1\), but \(\sigma(j) \neq t\) (since \(\sigma\) is a permutation and \(t\) has already been taken by \(\sigma(k+1)\)). There are \(k!\) ways this can happen. For \(i < k+1\), we must have \(\sigma(i) > k+1\), which contributes another factor of \(k!\). Therefore, the total number of permutations so that \({\bf D}(\sigma)\) is maximized and \(\sigma(k+1) < k+1\) is \(k(k!)^2\).

    Finally, if \(\sigma(k+1) > k+1\), a similar argument to the previous case gives that the number of possible permutations is \(k(k!)^2\).

    Putting all of these permutations together, we get an answer of \((2k+1)(k!)^2\).