2015 Putnam B5

Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that

$$

|i-j| = 1 \text{ implies } |\pi(i) -\pi(j)| \leq 2

$$

for all $i,j$ in $\{1,2,\dots,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.

令 $P_n$ 为 $\{1,2,\dots,n\}$ 的排列 $\pi$ 数，使得

$$

|i-j| = 1 \text{ 意味着 } |\pi(i) -\pi(j)| \leq 2

$$

对于 $\{1,2,\dots,n\}$ 中的所有 $i,j$。表明对于 $n \geq 2$，数量

$$

P_{n+5} - P_{n+4} - P_{n+3} + P_n

$$

不依赖于$n$，并找到它的值。