MathDB

B5

Part of 2015 Putnam

Problems(1)

Putnam 2015 B5

Source:

12/6/2015
Let PnP_n be the number of permutations π\pi of {1,2,…,n}\{1,2,\dots,n\} such that ∣i−j∣=1 implies ∣π(i)−π(j)∣≤2|i-j|=1\text{ implies }|\pi(i)-\pi(j)|\le 2 for all i,ji,j in {1,2,…,n}.\{1,2,\dots,n\}. Show that for n≥2,n\ge 2, the quantity Pn+5−Pn+4−Pn+3+PnP_{n+5}-P_{n+4}-P_{n+3}+P_n does not depend on n,n, and find its value.
PutnamPutnam 2015Putnam combinatorics