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)|\le 2\] for all $i,j$ in $\{1,2,\dots,n\}.$ Show that for $n\ge 2,$ the quantity \[P_{n+5}-P_{n+4}-P_{n+3}+P_n\] does not depend on $n,$ and find its value.

Consider a $(2m-1)\times(2n-1)$ rectangular region, where $m$ and $n$ are integers such that $m,n\ge 4.$ The region is to be tiled using tiles of the two types shown: \[ \begin{picture}(140,40) \put(0,0){\line(0,1){40}} \put(0,0){\line(1,0){20}} \put(0,40){\line(1,0){40}} \put(20,0){\line(0,1){20}} \put(20,20){\line(1,0){20}} \put(40,20){\line(0,1){20}} \multiput(0,20)(5,0){4}{\line(1,0){3}} \multiput(20,20)(0,5){4}{\line(0,1){3}} \put(80,0){\line(1,0){40}} \put(120,0){\line(0,1){20}} \put(120,20){\line(1,0){20}} \put(140,20){\line(0,1){20}} \put(80,0){\line(0,1){20}} \put(80,20){\line(1,0){20}} \put(100,20){\line(0,1){20}} \put(100,40){\line(1,0){40}} \multiput(100,0)(0,5){4}{\line(0,1){3}} \multiput(100,20)(5,0){4}{\line(1,0){3}} \multiput(120,20)(0,5){4}{\line(0,1){3}} \end{picture} \] (The dotted lines divide the tiles into $1\times 1$ squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping. What is the minimum number of tiles required to tile the region?