Putnam 2015, Problem B-5

Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\ldots,n\}$ such that
$$|i - j| = 1 \text{ implies } |\pi(i) - \pi(j)| \leq 2$$
for all $i,j$ in $\{1,2,\ldots,n\}$. Show that for $n \geq 2$, the quantity
$$P_{n+5} - P_{n+4} - P_{n+3} + P_n$$
does not depend on $n$, and find its value.

Solution:
The answer is 4. Assume \(n \geq 3\) for the moment. We write the permutations \(\pi\) counted by \(P_n\) as sequences \(\pi(1), \pi(2), \ldots, \pi(n)\). Let \(U_n\) be the number of permutations counted by \(P_n\) that end with \(n-1\); let \(V_n\) be the number ending in \(n, n-1\); let \(W_n\) be the number starting with \(n-1\) and ending in \(n-2, n\); let \(T_n\) be the number ending in \(n-2, n\) but not starting with \(n-1\); and let \(S_n\) be the number which has \(n-1, n\) consecutively in that order, but not at the beginning or end. It is clear that every permutation \(\pi\) counted by \(P_n\) either lies in exactly one of the sets counted by \(U_n, V_n, W_n, T_n, S_n\), or is the reverse of such a permutation. Therefore
\[
P_n = 2(U_n + V_n + W_n + T_n + S_n).
\]
By examining how each of the elements in the sets counted by \(U_{n+1}, V_{n+1}, W_{n+1}, T_{n+1}, S_{n+1}\) can be obtained from a (unique) element in one of the sets counted by \(U_n, V_n, W_n, T_n, S_n\) by suitably inserting the element \(n+1\), we obtain the recurrence relations
\[
\begin{align*}
U_{n+1} &= U_n + W_n + T_n, \\
V_{n+1} &= U_n, \\
W_{n+1} &= W_n, \\
T_{n+1} &= V_n, \\
S_{n+1} &= S_n + V_n.
\end{align*}
\]
Also, it is clear that \(W_n = 1\) for all \(n\).

So far we have assumed \(n \geq 3\), but it is straightforward to extrapolate the sequences \(P_n, U_n, V_n, W_n, T_n, S_n\) back to \(n = 2\) to preserve the preceding identities. Hence for all \(n \geq 2\),
\[
\begin{align*}
P_{n+5} &= 2(U_{n+5} + V_{n+5} + W_{n+5} + T_{n+5} + S_{n+5}) \\
&= 2((U_{n+4} + W_{n+4} + T_{n+4}) + U_{n+4} \\
&\quad + W_{n+4} + V_{n+4} + (S_{n+4} + V_{n+4})) \\
&= P_{n+4} + 2((U_{n+3} + W_{n+3} + T_{n+3}) + W_{n+3} + U_{n+3}) \\
&= P_{n+4} + P_{n+3} + 2((U_{n+2} + W_{n+2} + T_{n+2}) - U_{n+2} \\
&\quad + W_{n+2} - (S_{n+2} - V_{n+2})) \\
&= P_{n+4} + P_{n+3} + 2(2W_{n+2} + T_{n+2} - S_{n+2} - V_{n+2}) \\
&= P_{n+4} + P_{n+3} + 2(2W_{n+1} + V_{n+1} \\
&\quad - (S_{n+1} + V_{n+1}) - U_{n+1}) \\
&= P_{n+4} + P_{n+3} + 2(W_n + U_n - S_n - U_n) \\
&= P_{n+4} + P_{n+3} - P_n + 4,
\end{align*}
\]
as desired.

Remark: There are many possible variants of the above solution obtained by dividing the permutations up according to different features. For example, Karl Mahlburg suggests writing
\[
P_n = 2P_n', \quad P_n' = Q_n' + R_n'
\]
where \(P_n'\) counts those permutations counted by \(P_n\) for which 1 occurs before 2, and \(Q_n'\) counts those permutations counted by \(P_n'\) for which \(\pi(1) = 1\). One then has the recursion
\[
Q_n' = Q_{n-1}' + Q_{n-3}' + 1
\]
corresponding to the cases where \(\pi(1), \pi(2) = 1, 2\); where \(\pi(1), \pi(2), \pi(3) = 1, 3, 2\); and the unique case \(1, 3, 5, \ldots, 6, 4, 2\). Meanwhile, one has
\[
R_n' = R_{n-1}' + Q_{n-2}'
\]
corresponding to the cases containing 3, 1, 2, 4 (where removing 1 and reversing gives a permutation counted by \(R_{n-1}'\)); and where 4 occurs before 3, 1, 2 (where removing 1, 2 and reversing gives a permutation counted by \(Q_{n-2}'\)).

Remark: The permutations counted by \(P_n\) are known as key permutations, and have been studied by E.S. Page, Systematic generation of ordered sequences using recurrence relations, The Computer Journal 14 (1971), no. 2, 150–153. We have used the same notation for consistency with the literature. The sequence of the \(P_n\) also appears as entry A003274 in the On-line Encyclopedia of Integer Sequences (http://oeis.org).